レインボーテーブル入門：パスワード逆引きを加速する事前計算攻撃
レインボーテーブルとは、ハッシュ値から元の平文候補を高速に逆引きするための事前計算と圧縮の手法である。
まず全体像：なぜ脅威なのか
パスワードを平文で持たず、ハッシュ（例：SHA‑1, SHA‑256）で保存していても、攻撃者はハッシュ値だけを入手できればオフラインでいくらでも試行できる。レインボーテーブルは、あらかじめ巨大なパスワード空間の「平文→ハッシュ→縮約（リダクション）」連鎖を作っておき、漏えい後は連鎖終端だけを手掛かりに高速照合する。これは時間と記憶領域をトレードオフして、総当たりを劇的に短縮する発想だ。
仕組みの要点（Hellman表からの進化）
- 連鎖（チェーン）を作る：平文をハッシュし、ハッシュを縮約関数で別の平文候補に戻す操作を繰り返す。チェーンの先頭と終端だけを保存することでストレージを節約する。
- 同じ縮約関数のみだとチェーンの合流（衝突）が多く成功率が落ちる。レインボーテーブルは段ごとに異なる縮約関数を使い、合流を減らし成功率を高める（虹色の段に見立てた命名）。
- 復元時は、目標ハッシュを終端側から各段で逆追跡し、対応するチェーンが見つかれば先頭から再生して一致する平文を探す。
- 成功率はチェーン長tとチェーン本数m、対象文字集合・長さの設計に依存する。十分に広い空間やソルト付きでは現実的でなくなる。
攻撃手法の比較
同じ目的（ハッシュから平文候補を得る）でよく並ぶ手法を整理する。
| 手法 | 事前計算 | 必要ストレージ | オンライン試行 | 復号速度 | 典型的な弱点 |
|---|---|---|---|---|---|
| 総当たり（ブルートフォース） | 不要 | 小 | 不要 | 遅い | 空間が広いと現実的でない |
| 辞書攻撃（ルール付き含む） | 小 | 小〜中 | 不要 | 中 | 人間の作る語の偏りに依存 |
| プレーンな事前計算表 | 大 | 非常に大 | 不要 | 速い | 合流と保存量がボトルネック |
| レインボーテーブル | 大 | 大（圧縮） | 不要 | 速い | ソルトや遅延KDFに弱い |
どんなときに効く／効かない
| 保管形式 | 効き目 | 理由 |
|---|---|---|
| MD5やSHA‑1等の高速ハッシュでソルト無し | 強い | 同一ハッシュに同じテーブルが流用できる |
| ソルト有り（ユーザー毎にランダム） | ほぼ無力 | ソルトごとにテーブルが必要になり現実的でない |
| bcrypt/scrypt/Argon2等の遅延KDF | ほぼ無力 | 1回の計算が重く事前計算と探索が破綻 |
| ぺッパー（サーバ秘密鍵）併用 | ほぼ無力 | 秘密値なしでは探索不可能 |
実務の防御設計（優先度順）
- 唯一無二のソルトをユーザー毎にランダム生成し、ハッシュと一緒に保存する（ソルト長は16バイト以上を目安）。
- 遅延KDFを使う。現行推奨はArgon2id。次点でscrypt、bcrypt。PBKDF2は互換性は高いがGPU耐性が弱い。
- ぺッパー（アプリ設定やHSMで保持する秘密）を追加して二要素化。データベースが流出しても秘密が漏れない限り逆引き困難。
- パスワードポリシーは長さ重視（例：12〜16文字以上、可能ならパスフレーズ）。
- レート制限・MFA・侵害検知はオンライン攻撃の抑止として必須（オフライン対策の代替にはならない）。
KDFの比較
| KDF | 並列耐性 | メモリ耐性 | 主な調整パラメータ | 推奨度 |
|---|---|---|---|---|
| Argon2id | 高 | 高 | メモリ量、時間、並列度 | 最優先 |
| scrypt | 中 | 高 | N, r, p | 高 |
| bcrypt | 中 | 低 | cost | 中 |
| PBKDF2 | 低 | 低 | iteration | 互換性重視時のみ |
ソルト／ぺッパー／ストレッチングの違い
| 手法 | 目的 | 保存場所 | 効果範囲 | 注意点 |
|---|---|---|---|---|
| ソルト | 同一ハッシュの再利用を阻止 | DB（公開可） | ユーザー毎 | 乱数で長く一意に |
| ぺッパー | 攻撃者に未知の秘密を足す | アプリ側秘密（HSM等） | 全ユーザー | ローテーション計画が必要 |
| ストレッチング（KDF） | 計算を重くする | ハッシュのみ | 全ユーザー | 適正パラメータの再評価が必要 |
よくある誤解と落とし穴
- ハッシュ化していれば安全という誤解：高速ハッシュは守りではなく圧縮関数。ソルトと遅延KDFが前提。
- ソルトを非公開にすれば良い？：ソルトは秘匿前提ではない。むしろ公開を前提に十分なランダム性を確保する。
- bcrypt等でも固定のソルトを共通利用：意味がない。必ずユーザー毎に一意。
- パスワード強度を複雑さで縛る：ユーザー体験を壊しがち。長さ重視のパスフレーズが実用的。
- データベースだけ守れば良い：アプリサーバやログからぺッパーが漏れる設計は台無し。鍵管理を分離する。
すぐに使えるチェックリスト
- ハッシュはArgon2id等のKDFを採用し、パラメータは現行のハードウェアで1回あたり数十〜数百msに調整
- ユーザー毎のランダムソルト（>=16B）を保存
- アプリ側にぺッパーを安全保管（HSMやKMSを利用）
- 監査ログに平文やハッシュの再利用が出ていないか確認
- パスワード長中心のポリシーとMFAを併用
- 侵害時のローテーション手順（ぺッパー更新、強制リセット）を用意
まとめ
レインボーテーブルは、ソルト無しの高速ハッシュに対して時間と記憶領域のトレードオフで逆引きを加速する古典的だが現役の手法だ。正しい防御（ユーザー毎ソルト＋遅延KDF＋ぺッパー）を採れば、その優位性はほぼ失われる。攻撃モデルを常にオフライン前提で設計し、パラメータの再評価と鍵管理を運用で回すことが、最良の防御線になる。