レインボーテーブル攻撃の解説

レインボーテーブルは、ハッシュ値を元の入力にマッピングする事前計算済みルックアップテーブルで、パスワードハッシュの解読に特化しています。攻撃中にハッシュを計算する代わりに、攻撃者はテーブルでターゲットハッシュを検索し、対応するパスワードを即座に取得します。

レインボーテーブルの仕組み:

基本的なアプローチはすべてのパスワード-ハッシュペアを保存しますが、膨大なストレージが必要です。レインボーテーブルは2003年にPhilippe Oechslinが発明した時間-メモリトレードオフを使用します。テーブルはハッシュ操作とリダクション操作を交互に行うチェーンを保存します。各チェーンの開始と終了のみが保存されます。ハッシュを解読するには、攻撃者はリダクションとハッシュ操作を適用してチェーンの終端に一致するか確認し、そのチェーンを再生成して一致する平文を見つけます。

規模と有効性:

8文字以下の全英数字パスワードをカバーするMD5レインボーテーブルは約100GBに収まり、一致するハッシュを数秒で解読できます。CrackStationなどのオンラインサービスは複数のハッシュアルゴリズムの数十億の一般的パスワードをカバーするレインボーテーブルを維持していました。

ソルトがレインボーテーブルを無効化する理由:

ソルトはハッシュ前にパスワードに付加されるランダムな値です：hash(salt + password)。ソルトはユーザーごとに異なるため、攻撃者はソルト値ごとに別のレインボーテーブルが必要です。128ビットのソルトでは2^128個のレインボーテーブルが必要であり、完全に実行不可能です。bcrypt、scrypt、Argon2はすべてソルトを自動的に組み込みます。

最新の防御:

ソルトだけではレインボーテーブルを防げますが、高速ハッシュ関数によるブルートフォース攻撃は防げません。完全な防御スタックには、(1) bcrypt/Argon2のような低速ハッシュ関数、(2) パスワードごとの固有ランダムソルト、(3) 各ハッシュ計算を高コストにする十分なワークファクター、(4) ログイン試行のレート制限が含まれます。