中間一致攻撃：複合暗号に対する計算量とメモリのトレードオフ

典型的なアルゴリズム上の手順

• 既知の平文 P と、それに対応する暗号文 C を定める。これらは、選択平文または既知平文の状況で得られることが多い。平文および暗号文の用語が役立つ。
• 第1の鍵空間にあるすべての鍵値 K について、X = EK(P) を計算し、高速な検索用に構成された表（例えばハッシュ表またはソート済みリスト）に組 (X, K) を格納する。
• 第2の鍵空間にあるすべての鍵値 K' について、Y = DK'(C) を計算し、Y が表に存在するか照会する。一致ごとに、候補の組 (K, K') が得られる。
• 偽陽性を除外するため、追加の一つ以上の平文・暗号文対を用いて候補鍵対を検証する。必要であれば、さらにデータを用いて手順を詳細化または繰り返す。

計算量と資源。独立した二つの n ビット鍵に対し、結合された鍵空間を素朴に総当たり探索すると、およそ 22n 回の暗号化が必要となる。これに対し、中間一致戦略では、必要な暗号化回数をおよそ 2n+1 のオーダーまで減らせる一方、中間値を保持するために O(2n) の記憶領域を要する。言い換えれば、指数的なメモリを代償として、時間は単一の n ビット鍵を破る場合のおよそ2倍であり、二乗にはならない。実装では、メモリ量と追加計算量の間で調整が行われる。実用的な攻撃では、大規模ハッシュ表や外部ソートなど、効率的なインメモリ検索および保存技術が使用される。実装の詳細と検索戦略については、ルックアップテーブルに関する資料を参照できる。

歴史と影響。この手法は、鍵長を増加させることを意図した単純な二重暗号化方式を分析したホイットフィールド・ディフィーとマーティン・ヘルマンによって、1977年に記述された。彼らの研究は、二つの独立した鍵で暗号を単純に二回適用する方式、時に二重暗号化と呼ばれる構成が、中間一致攻撃のために期待された二乗の安全性をもたらさないことを示した。この知見は後の標準規格の設計に影響を及ぼし、三重暗号化モードや、単純な中間値照合を意図的に防ぐ動作モードなど、より慎重な構成の採用を促した。初期のブロック暗号拡張や、ブロック暗号設計に関する学術的議論では、この攻撃が注意を促す指針となる例としてしばしば言及される。

防御、制限および注目すべき事実。この攻撃には実行可能な規模の記憶領域と、多数の暗号化・復号を計算する能力が必要であり、利用可能なメモリと処理能力によって制約される。対策には、中間状態が独立した鍵による逆算の対象にならないよう鍵とラウンドを結び付ける暗号方式の使用、O(2n) のメモリが現実的でなくなるよう鍵長を大きくすること、あるいは合成上の弱点を避ける証明や設計の採用が含まれる。三重暗号化方式、非可逆な混合を伴う鍵付きモード、鍵依存の変換を持つ設計は、典型的な対応策である。実装では、サイドチャネルにも注意し、複数の既知平文・暗号文対が攻撃者に容易に取得されないようにしなければならない。実用的な背景資料や実演については、鍵と鍵管理に関する資料、および暗号文解析の一般的な入門資料を参照できる。