Rainbow Table

レインボーテーブルは、ハッシュ関数の逆写像のためにMartin Hellmanの方式を改良した事前計算テーブルである。時間と空間のトレードオフでパスワードハッシュを解析する。

目的

事前計算したハッシュチェーンでストレージを大幅に削減し、ソルトなしのパスワードハッシュを効率的に解析する。

メカニズム

ハッシュチェーンを事前計算する：始点から終点までハッシュとリダクションを繰り返し、終点のみを保存する。検索時はターゲットハッシュからリダクションとハッシュを繰り返して終点と一致させ、始点からチェーンを再構築して原像を見つける。ソルトはユーザーごとに独立したテーブルを強制し、事前計算を不可能にする。

ユースケース

ソルトなしLM/NTLMハッシュの解析
パスワードハッシュのセキュリティ教育
Ophcrackツールでの利用
セキュリティ監査での活用

例

入力

MD5 without salt

Output

8-character alphabetic password cracked in seconds

Salt defeats rainbow tables

よくあるエラー

Storing password hashes without salt: Unique per-user salt + slow hash

関連用語

MD5 は Ronald Rivest が設計した 128 ビットの暗号学的ハッシュ関数である。衝突攻撃により安全性が崩れており、現在はチェックサムなどセキュリティを要しない用途に限られる。

SHA-256 は SHA-2 ファミリーの 256 ビット出力版である。TLS、ブロックチェーン、暗号応用で広く使われ、現実的な攻撃は知られていない。

ソルトとは、パスワードのハッシュ化時に加えるランダムな値のことで、同一パスワードでも異なるハッシュを生成させ、レインボーテーブルやパスワードの一致検出を無効化する。

ハッシュソルティング（Hash Salting）は、ハッシュ入力にランダムなソルトを追加して、同じ入力でも異なるハッシュを生成させる手法である。レインボーテーブルと衝突検出を無効化する。

関連ツール

ハッシュ計算ツール

Compute MD5, SHA-1, SHA-256, or SHA-512 hashes with hex or Base64 output。無料、プライベート、100%クライアントサイド。

ハッシュ比較ツール

Compare MD5, SHA-1, SHA-256, SHA-384, SHA-512 of the same input。無料、プライベート、100%クライアントサイド。

References