TMTO攻撃とは何か：時間と記憶のトレードオフとレインボーテーブルの仕組みと防御策
エバープレイ編集部TMTO攻撃とは — 概要
TMTO攻撃（Time–Memory Trade-Off、時間と記憶領域のトレードオフ攻撃）は、暗号解析やパスワード破りでよく使われる手法で、事前計算（とその保存）によりオンラインでの総計算時間を大幅に減らす考え方です。膨大な総探索空間（鍵空間やパスワード空間）を「オンラインでフル探索する代わり」に、あらかじめ計算して結果を保存しておき、攻撃時には保存した情報を検索して短時間で候補を得る、という戦略です。
歴史的背景と代表的な手法
TMTOの基本概念は1980年のHellmanによる論文で広く知られるようになりました。Hellmanはブロック暗号の鍵探索において、前処理（precomputation）と格納（記憶）を使うことでオンライン探索時間を短縮する方法を示しました。その後、2003年にOechslinが提案した「レインボーテーブル（Rainbow tables）」がパスワードクラッキングで実用的な成功を収め、TMTO手法の代表例として広く用いられるようになりました。
基本原理 — どうやって時間と記憶を交換するのか
- 全探索（Brute-force）のコスト：鍵空間やパスワード空間の大きさをNとすると、オンラインで全てチェックするコストはO(N)です。
- 事前計算とテーブル化：例えば、ハッシュ関数の入力と出力を事前に多数計算してテーブルに保存しておくと、攻撃時はハッシュ値からテーブルを検索するだけで元の入力候補を得られます（ハッシュ逆算）。ただし保存コストは大きくなります。
- チェイン化（Hellmanテーブル）：全ての個別ペアを保存する代わりに、入力→ハッシュ→還元関数→次の入力という操作を連鎖（チェイン）にして、チェインの端点のみを保存することでメモリを削減します。検索時にはチェインを逆方向に辿って候補を復元します。
- レインボーテーブル：同じ還元関数を使うとチェインの衝突で情報が失われるため、各列で異なる還元関数を用いることで衝突を減らし、成功率を上げたのがレインボーテーブルです（Oechslinの改良）。
技術的なポイント（チェイン、還元関数、衝突）
チェインは「開始値→（ハッシュ→還元）×t→終端値」という形で作られ、終端のみを保存します。検索時にはターゲットのハッシュを還元関数で変換し、終端と一致するチェインを見つけたら、チェイン開始値から該当の位置まで再計算して元の平文候補を取り出します。
この方式には「チェイン同士の衝突（merge）」や「ループ化」による損失があり、十分な成功率を得るにはチェイン長やチェイン本数、テーブル数、還元関数設計などのパラメータ調整が必要です。レインボーテーブルは還元関数を列ごとに変えることで衝突を大幅に減らし、同じメモリ量で成功率を高めています。
例：パスワードクラッキングへの応用
パスワードハッシュ（例：MD5, NTLMなど）に対するTMTOは非常に有名です。攻撃者はパスワード候補をハッシュしてレインボーテーブルを作成しておき、漏洩したハッシュが与えられるとテーブル検索で迅速に元パスワード候補を得ます。過去にはLMハッシュやNTLMハッシュ向けのレインボーテーブルが配布され、多くの短く単純なパスワードが瞬時に復元されました。
「データ」も考慮する拡張：TMDTO（Time–Memory–Data Trade-Off）
攻撃者が複数の暗号出力（平文と対応する暗号文のペアや多くのハッシュ）を入手できる場合、時間とメモリに加えて利用可能なデータ量も利用して効率を上げる手法があり、これをTime–Memory–Data Trade-Off（TMDTO）と呼びます。ストリーム暗号や一部のブロック暗号に対して有効な場合があります（研究例：Biryukov/ Shamirら）。
現実的な効果と限界
- TMTOは「オフライン攻撃」に強力：攻撃者がハッシュや暗号文を持っていればネットワーク制約なしに大量のテーブル検索が可能。
- 必要なメモリ量は依然として大きい：事前計算や保存が実用的である範囲か否かが現実的な制約。
- パラメータ調整（チェイン長、テーブル数、還元関数など）に不備があると成功率が低下。
- ソルトや個別化、遅延ハッシュ関数はTMTOの効果を根本的に下げる。
主な防御策（対策）
- ソルト（salt）の導入：各ユーザごとにランダムなソルトを付与しハッシュ化すると、事前計算テーブルを各ソルトに対して作る必要があり、攻撃コスト（メモリ・時間）が爆発的に増えます。
- 遅延ハッシュ（key stretching）：bcrypt, scrypt, Argon2 などの遅延ハッシュ関数を使い、ハッシュ計算を意図的に重くすることで、事前計算や大規模検索のコストを上げます。特にArgon2はメモリ消費をパラメータ化でき、TMTOに効果的です。
- pepper（サーバ側シークレット）の併用：ソルトとは別にサーバ保管のシークレットをハッシュに混ぜると、データベース漏洩だけではTMTOが成立しにくくなります（ただし運用リスクあり）。
- レート制限や多要素認証：オンライン攻撃はレート制限やMFAで大幅に制御できます（TMTOは主にオフラインに効力を持つため、MFAは有効）。
- 長く複雑なパスワード方針と秘密保持教育：単純なパスワードはどれだけ対策をしても事前計算テーブルで破られやすい。
実務上の評価 — いつTMTOが脅威になるか
TMTOが実際の脅威となるのは、攻撃者が対象ハッシュ（または暗号文）を取得しており、かつソルトや遅延ハッシュが適切に使われていない場合です。例えば、古いシステムで平文ソルトなしのMD5やNTLMハッシュが使われていると、公開されたレインボーテーブルで瞬時に復元される危険があります。一方、各ユーザにユニークなソルトとArgon2等の設定が施されている場合、現実的なTMTOは非常に高コストになります。
まとめ
TMTO攻撃は「時間」と「記憶」を交換する古典的で強力な戦略です。レインボーテーブルなどの具体的手法により、ソルト無きハッシュや軽いハッシュ関数は容易に破られます。防御にはソルトの厳格な採用、bcrypt/scrypt/Argon2などの遅延ハッシュ、運用面の対策（MFA、レート制限、良好なパスワードポリシー）が重要です。セキュリティ設計では、TMTOの存在を前提に「オフラインでの事前計算耐性」を持つ選択を行うべきです。
参考文献
- M. Hellman, "A Cryptanalytic Time-Memory Trade-Off", IEEE Transactions on Information Theory, 1980.
- P. Oechslin, "Making a Faster Cryptanalytic Time-Memory Trade-Off" (Rainbow Tables), CRYPTO 2003. (PDF)
- Wikipedia: Time–memory trade-off
- Wikipedia: Rainbow table
- Project RainbowCrack（ツール／解説）
- NIST SP 800-63B: Digital Identity Guidelines (Authentication and Lifecycle)
- Niels Provos & David Mazières, "A Future-Adaptable Password Scheme" (bcrypt)、USENIX 1999. (PDF)
- Colin Percival, "scrypt"（設計・実装情報）
- Password Hashing Competition / Argon2（仕様と資料）
投稿者プロフィール
