ハッシュとパスワードのオフライン攻撃(レインボーテーブル・GPU)

オフライン攻撃という前提：レート制限が消える世界

パスワードの安全な保存 では「ハッシュ化して保存せよ」を扱いました。本稿はその裏側、ハッシュが流出した後に攻撃者が何をするかを経済の視点で詰めます。

鍵になるのはオンライン攻撃とオフライン攻撃の断絶です。ログインフォーム越しの試行（オンライン）は、レート制限 とアカウントロックで毎秒数回に縛れます。ところが users テーブルのハッシュ列が漏れた瞬間、攻撃者は自分の手元のハードで照合を回せる――サーバーは一切関与しないため、レートリミットもロックも認証ログも完全に無効になります。

オンライン攻撃: 候補 -> ネットワーク -> サーバー認証(レート制限あり) -> 可否
オフライン攻撃: 候補 -> 攻撃者ローカルでハッシュ計算 -> 流出ハッシュと比較  ← 制限なし

この瞬間、守りに残る変数は一つだけです。1回のハッシュ計算をどれだけ重くできるか。攻撃者が単位時間に試せる候補数は「実効スループット ÷ 1回のコスト」で決まり、防御側が触れるのは分母だけになります。以降、レインボーテーブル（空間で殴る）と GPU/ASIC（速度で殴る）という二つの増幅手段を見ていきます。

事前計算とレインボーテーブル：空間を時間に交換する

総当たりの素朴な高速化は事前計算です。よくある候補を片端からハッシュし、ハッシュ -> 平文 の巨大な辞書を作っておけば、流出ハッシュは表引き一発で平文に落ちます。問題は容量で、全候補を保存するのは非現実的です。ここで時間と空間のトレードオフを突くのがレインボーテーブルです。

中核は還元関数（reduction function）Rです。R はハッシュ値を「別のもっともらしい平文」へ写す関数で、ハッシュ H と交互に適用して**鎖（chain）**を作ります。

鎖の生成（長さ t の例）:
  p0 --H--> h0 --R1--> p1 --H--> h1 --R2--> p2 ... --H--> h(t-1)
保存するのは各鎖の「先頭 p0」と「末尾 h(t-1)」だけ（途中は捨てる）

照合: 流出ハッシュ y から R/H を適用しながら末尾集合と一致するまで前進
  -> 一致した鎖を先頭から再生成し、y の直前の平文を特定

途中を捨てて両端だけ持つので、保存量は鎖の本数に比例し、長さ t 分は計算で取り戻します。つまり空間を t 分の1に圧縮する代わりに、照合時に最大 t 回の再計算を払う。各段で異なる還元関数 R1, R2, ... を使うのが「レインボー」の名の由来で、これにより異なる鎖が同じ値で合流して途中で潰れるチェーン衝突を大幅に減らし、被覆率（カバレッジ）を高めます。

要点は、レインボーテーブルが効くのは**「同じ入力は常に同じハッシュになる」から事前計算が使い回せる**という一点にかかっていることです。ここを壊すのが次のソルトです。

salt が無効化する仕組み：事前計算の使い回しを断つ

ソルト（salt）は、ユーザーごとに違うランダム値をパスワードへ連結してからハッシュする手法です。保存するのは salt と H(salt || password) の組で、ソルト自体は秘密にしません（CSPRNG で生成し、ハッシュ文字列に同梱するのが通例）。

ソルトが攻撃を壊すのは事前計算の前提を破壊するからです。レインボーテーブルは特定のハッシュ関数に対して一度作れば全員に使い回せました。しかしソルトが入ると、攻撃者はソルト値ごとに別のテーブルを作り直さねばならず、事前計算のコストが攻撃対象の人数分に膨れ上がります。16バイトのランダムソルトなら取りうる値は天文学的で、事前計算は経済的に完全に破綻します。

ソルトなし: H("password123") は誰でも同じ -> 1つの表で全員ヒット
ソルトあり: H(salt_A || "password123") と H(salt_B || "password123") は別物
           -> 表を使い回せず、ユーザーごとに最初から計算し直し

副次効果として、同じパスワードを使う二人のハッシュが一致しないため、流出DBを眺めて「同一ハッシュ＝同一パスワード」を一網打尽にする攻撃も防げます。ただし注意すべきは、ソルトはオフラインの総当たりそのものを遅くはしない点です。攻撃者が一人のユーザーに狙いを絞れば、そのソルトを使って候補を順に試すコストは1回のハッシュ計算と変わりません。ソルトが潰すのはあくまで「事前計算と複数ユーザーへの償却」であり、ここから先の単独総当たりの速度勝負を決めるのが次の GPU/ASIC です。

pepper の位置づけ：DB外に置く共通の秘密

ペッパー（pepper）は全ユーザー共通の秘密値で、ソルトと対になる概念です。違いは秘匿性にあります。ソルトは公開前提でDBに同梱しますが、ペッパーはDBとは別の場所（環境変数や シークレット管理 のKMS/HSM）に保管し、漏らしません。

狙いはDBだけが漏れたケースの最後の防壁です。攻撃者がハッシュとソルトを手にしても、未知のペッパーが連結されている限り、正しいパスワード候補を入れてもハッシュが一致しません。ペッパーの値そのものを総当たりする必要が生じ、十分長ければ事実上不可能になります。実装は連結よりも HMAC(pepper, password) の形が安全で、後段の専用ハッシュへ渡します。

GPU/ASIC の経済：なぜ高速ハッシュは“ほぼ平文”なのか

事前計算をソルトで潰しても、攻撃者には生の計算力で殴る道が残ります。ここで効くのが、汎用ハッシュ（MD5, SHA-1, SHA-256 など）の設計目標が「高速・小状態」だという事実です。1回の計算が分岐もメモリ参照もほぼ無い純算術の連なりなので、超並列ハードに完璧に適合します。

• GPU：数千の演算コアが異なる候補を同時にハッシュする。単純な算術の塊である高速ハッシュは、GPUのスループットをほぼ100%引き出せる。汎用CPUの毎秒数百万回に対し、ハイエンドGPUは MD5/SHA-1 を毎秒数百億回回せる。
• ASIC/FPGA：ハッシュ専用回路を焼き、1チップに大量のパイプラインを並べる。汎用性を捨てた分、面積・電力あたりの試行数でGPUをさらに上回る。仮想通貨マイニングが実証したとおり、量産で単価は劇的に下がる。

攻撃者の試行レート ≈ 実効ハッシュスループット ÷ 1候補あたりの計算コスト

高速ハッシュ:  数百億 hash/s（GPU）  -> 一般的な弱パスワードは秒〜分で陥落
専用ハッシュ:  1回が0.2〜0.5秒相当  -> 同じGPUでも試行レートが桁違いに落ちる

候補の選び方も総当たりの全数列挙だけではありません。実際の攻撃は辞書攻撃（流出済みパスワード集や単語リスト）とルールベース変換（password -> P@ssw0rd! のような人間の癖の自動適用）、漏洩パスワードを別サービスへ流用するクレデンシャルスタッフィングが主力です。人間が選ぶパスワードの分布は極端に偏っているため、高速ハッシュなら多数のアカウントが現実的な時間で割れます。

決定打は、攻撃者の実効スループットを下げること――すなわち分母の「1回のコスト」を意図的に膨らませる専用ハッシュです。bcrypt は計算時間を、scrypt/Argon2 は時間に加えてメモリを人質に取り、GPUのコアあたり少メモリやASICの面積優位を相殺します。その内部は パスワードハッシュの内部 で詳説しています。

まとめ：攻撃の経済を一段ずつ潰す

オフライン攻撃の本質は、レート制限という外側の守りが消え、勝負が1回のハッシュコスト対攻撃者の実効スループットに純化することです。レインボーテーブルは空間を時間に換えて事前計算を圧縮し、ソルトはその前提（使い回し）を壊して無効化する。だがソルトは速度を下げないため、GPU/ASICの桁違いのスループットには別の手当てが要る。

したがって正しい積み上げは、**ユーザー単位のソルト（事前計算と償却の遮断）＋ DB外のペッパー（単独漏洩の保険）＋ メモリ困難な専用ハッシュ（実効スループットの直撃）**の三段重ねです。どれか一つでは穴が残り、三つ揃って初めて「ハッシュが漏れても割られにくい」状態に到達します。