事前計算攻撃の仕組みと防御策—レインボーテーブルとパスワード保護の実践ガイド
エバープレイ編集部事前計算攻撃とは — 概要
事前計算攻撃（precomputation attack）とは、攻撃者が大量の計算を事前に行い、その結果を保存しておくことで、攻撃対象に対する後続の攻撃を著しく高速化する手法の総称です。代表的な例としてパスワードハッシュに対する「レインボーテーブル攻撃」や、暗号解析における時間-メモリトレードオフ（Hellman の手法など）が挙げられます。攻撃の基本アイデアは「一度多大なコストを払って結果を作っておけば、あとは検索や照合で短時間に答えが得られる」というものです。
どのように機能するか — 基本原理
一般に事前計算攻撃は次の2段階で行われます。
- 事前計算フェーズ：攻撃対象となる関数（例：パスワード→ハッシュ）の入力空間全体、またはその一部を列挙し、入力と出力の対応表（もしくは圧縮したチェイン）を作成・保存する。
- 照合フェーズ：実際の攻撃（漏洩ハッシュの入手など）が発生した際、そのハッシュを事前に作った表と突き合わせ、元の入力（パスワード）を高速に復元する。
事前計算には大量の計算時間と大容量の保存領域が必要ですが、照合は高速です。これが「時間（攻撃時の計算）をメモリ（事前保存）で置き換える」典型的な例です。
主要な手法と歴史的背景
Hellman の時間-メモリトレードオフ（1980）：攻撃時の計算量を減らすためにテーブルを作る基本的な考え方を示した論文です。全探索のコストを保存テーブルで下げる枠組みを与えました。
レインボーテーブル（Oechslin, 2003）：単純なハッシュ照合テーブルは衝突や多量の保存容量の問題があります。レインボーテーブルは連鎖（チェイン）と再帰的な還元関数を使って保存容量を削減し、かつ衝突の影響を低減する改良手法です。パスワードハッシュ破りで広く知られる手法になりました。
GPU/ASIC を使った大規模事前計算：近年ではGPUファームやASICを用いて高速にハッシュを生成し、大規模な事前計算を実現する例が増えています。特に単純で高速なハッシュ関数（MD5、SHA-1 等）は事前計算の標的になりやすいです。
パスワードハッシュとレインボーテーブルの具体例
パスワード管理において多くのシステムはパスワードのハッシュを保存します。攻撃者がそのハッシュデータベースを入手した場合、事前計算済みのテーブルを使えば平文パスワードを迅速に復元できます。
例：小文字の英字のみで長さ6のパスワード空間は 26^6 = 308,915,776 通りです。MD5 のような高速ハッシュであれば、308M 個のハッシュを計算してテーブル化するのは現実的で、保存容量も概算で 32 バイト/エントリとして約 9.9 GB 程度で済みます。対して、英大小文字＋数字（62文字）で長さ8の空間は 62^8 ≈ 2.18×10^14 通りになり、同じく 32 バイトで保存しようとすると約 7 PB（ペタバイト）に達します。従って、パスワードの長さ・文字種・エントロピーが事前計算の実行可能性を大きく左右します。
ソルト（salt）はなぜ有効か
ソルトとは各パスワードに付与するランダム値で、同じパスワードでも異なるハッシュを生むためのものです。ソルトが適切に用いられていると、「全ユーザー共通のハッシュ表」を一度作るだけでは意味をなさず、各ソルトごとに別個の事前計算が必要になります。ソルトの長さが十分（例：16 バイト以上）でランダムならば、事前計算のコストは事実上ユーザー数倍になり、実用性を失わせることができます。
事前計算攻撃の限界と現実的コスト
ストレージ容量：空間が指数関数的に増えるため、エントロピーが高いパスワード空間を完全にテーブル化するのはすぐに現実的でなくなります。先述のように、8 文字の強いパスワード空間は PB 級の保存が必要になる場合があります。
計算コスト：事前計算には大量の電力と時間が必要です。GPU ファームやクラウドを大量に使えば可能性は広がりますがコストは増えます。国家的資源や大規模な犯罪組織でないと難しい領域もあります。
ハッシュ関数の性質：MD5 や SHA-1 のような高速なハッシュは事前計算に向いていますが、bcrypt/scrypt/Argon2 のように意図的に遅く・メモリを使う関数は事前計算を困難にします（特にメモリハード関数は大規模並列化の効率を下げます）。
暗号プロトコルにおける事前計算
事前計算はパスワード以外の分野でも使われます。たとえば離散対数問題や楕円曲線離散対数（ECDLP）において、固定された群パラメータに対して大規模な事前計算を行い、後から個別の鍵を速やかに破るという考え方があります。現実的には楕円曲線や RSA のような大きな鍵長に対しては、空間と計算の膨大さから実行は非常に困難ですが、「同じパラメータが何度も使われる」場合には、投資に見合うリスクが生じる可能性があります。
防御対策（実践的な推奨）
ユニークなソルトを付与する：各パスワードにランダムで十分長いソルト（例：16 バイト以上）を付け、ハッシュと共に保存する。これにより共通テーブル型の事前計算を無効化できます。
鍵導出関数（KDF）を使う：bcrypt、scrypt、Argon2 のような遅延・メモリハードな関数を利用して、ハッシュ計算を意図的にコスト高にします。これにより事前計算・総当たりのコストを上げられます。
ペッパー（秘密値）の利用：サーバ全体で共有する秘密値（ペッパー）を別途保管（例：HSM）し、ハッシュに混ぜることで漏洩ハッシュだけからの復元を困難にする方法。ただし運用とバックアップに注意が必要です。
多要素認証（MFA）を導入する：パスワードが破られても追加要素があれば被害を防げる場合があります。
ログイン試行のレート制限と検知：ブルートフォースや辞書攻撃を含む試行的攻撃を検知し、IP 制限やアカウントロックを行う。
パスワードポリシーとパスワードマネージャの推奨：十分長・ランダムなパスフレーズを利用させ、使いまわしを避ける運用を促す。
運用的注意点と現場でよくある誤解
「ハッシュ化してあるから安全」は誤りです。ハッシュ関数が速い、ソルトがない、あるいは弱い KDF を使っていると事前計算や総当たりで破られます。
長いソルトや強い KDF を導入しても、ユーザーが弱いパスワード（短く推測されやすい文字列）を使っていると突破される可能性は残ります。
暗号パラメータの再利用（特にプロトコルや曲線の固定）は、攻撃者に事前投資のインセンティブを与える場合があります。同じパラメータが広く使われていると、攻撃コストを多数のターゲットで分散して回収できるからです。
まとめ・実務への示唆
事前計算攻撃は「時を前倒ししてコストを払う」ことで後続の攻撃を劇的に楽にする手法です。防御側はこれに対して、ユニークなソルト、メモリハードな KDF、ペッパー、MFA、レート制限などの複合的対策を取る必要があります。特にパスワード管理では「ソルト＋適切な KDF」が基本中の基本であり、これを怠るとレインボーテーブルや現代の GPU ファームによる大量ハッシュ計算に対して脆弱になります。
参考文献
- Time–memory trade-off — Wikipedia
- P. Oechslin, "Making a Faster Cryptanalytic Time-Memory Trade-Off", 2003 (レインボーテーブル論文)
- Rainbow table — Wikipedia
- OWASP Password Storage Cheat Sheet
- NIST Special Publication 800-63B — Digital Identity Guidelines (Authentication and Lifecycle Management)
- Project RainbowCrack
- LinkedIn data breach — Wikipedia（参考：過去のハッシュ漏洩事例）
- Argon2 — Wikipedia（メモリハード KDF の一例）
投稿者プロフィール
