中間一致攻撃

「中間者攻撃」とは異なります。

中間一致攻撃（ちゅうかんいっちこうげき、英：Meet-in-the-middle attack）とは、暗号理論において誕生日攻撃と同様に時間と空間のトレードオフを利用した攻撃方法の一種である。

概要[編集]

誕生日攻撃では、ある関数${\displaystyle f(x)}$について${\displaystyle f(x_{1})=f(x_{2})}$となるような値${\displaystyle x_{1},x_{2}}$を定義域中から見つけるのが目的であった。一方、中間一致攻撃では、ある合成関数${\displaystyle g(f(x))}$について${\displaystyle f(x_{1})=g^{-1}(x_{2})}$となるような${\displaystyle x_{1},x_{2}}$を探すのが目的である。中間一致攻撃という名前は、合成関数${\displaystyle g(f(x))}$の中間で作られる値が一致するものを探索することから付けられている。

この攻撃手法はブロック暗号に対する攻撃方法として、ディフィーとヘルマンにより1977年に開発された。ブロック暗号の安全性を高める方法として、二つの異なる暗号鍵で2回暗号化を行う（鍵の異なる2つの暗号化関数の合成関数を使用して暗号化を行う）という手段が考えられる。単純に考えると、2回の暗号化により暗号の安全性は2乗になるものと予想される。事実、全ての暗号鍵を試そうとすると、暗号鍵を一つだけ使用した場合は${\displaystyle 2^{n}}$回の試行で済むのに対し、二つの鍵の組み合わせでは${\displaystyle 2^{2n}}$回の試行が必要となる（鍵長が${\displaystyle n}$ビットの場合）。

これに対しディフィーとヘルマンは、時間と空間のトレードオフを利用することで、2つの鍵を使用した場合でも、1つの鍵を使用した場合と比較して試行回数を高々2倍で済ませる方法を開発した。^[1] この攻撃方法では、平文に対して片方の鍵で暗号化を行い、暗号に対してもう片方の鍵で復号を行って、2つの暗号化処理の中間で突き合わせ（meet-in-the-middle）を行う。

攻撃方法[編集]

攻撃者は平文${\displaystyle P}$とそれに対応する暗号文${\displaystyle C}$を知っているものとする。ここで、${\displaystyle E}$を暗号化関数、${\displaystyle K_{1}}$と${\displaystyle K_{2}}$をそれぞれ異なる鍵とすると、暗号化処理は以下のように記述できる。

${\displaystyle C=E_{K_{2}}(E_{K_{1}}(P))}$

まず、攻撃者は全ての鍵候補${\displaystyle K_{1}}$に対して${\displaystyle E_{K_{1}}(P)}$を計算しておき、その結果をメモリ上に保存しておく。次に、攻撃者は全ての鍵候補${\displaystyle K_{2}}$を使って暗号文の復号を行い（${\displaystyle D}$を復号関数とすると、${\displaystyle D_{K_{2}}(C)}$を計算する）、その結果をメモリに保存しておく。この2つの計算結果の中に合致するものがあれば、その計算に使用した2つの鍵${\displaystyle (K_{1},K_{2})}$がおそらく正しい鍵であると言える。この処理を高速化する方法としては、まず${\displaystyle E_{K_{1}}(P)}$の結果と暗号化に使用した鍵${\displaystyle K_{1}}$のペアをインメモリのルックアップテーブルに保存しておき、次に${\displaystyle D_{K_{2}}(C)}$の結果を使用してルックアップテーブルから鍵候補を検索する方法が考えられる。計算結果から合致するものが見つかったら、別の暗号文と平文を使用すれば検証が行える。

鍵のサイズを${\displaystyle n}$ビットとしたとき、この攻撃方法では${\displaystyle 2^{n+1}}$の試行回数で攻撃が行える（ただし、${\displaystyle O(2^{n})}$の記憶領域を必要とする）。一方、単純な攻撃方法では${\displaystyle 2^{2n}}$回の試行を必要とする（記憶領域は${\displaystyle O(1)}$で済む）。

参考文献[編集]

1. ^ W. Diffie and M. E. Hellman (June 1977). “Exhaustive Cryptanalysis of the NBS Data Encryption Standard”. Computer 10 (6): 74-84. doi:10.1109/C-M.1977.217750. 

関連項目[編集]

• 誕生日攻撃
• トリプルDES

表 話 編 歴 ブロック暗号 アルゴリズム AES ARIA Blowfish Camellia CAST-128 CAST-256 DES DES-X 3DES FEAL IDEA KASUMI Lucifer MISTY1 MULTI2 RC2 RC5 RC6 SEED Serpent Square Twofish スキップジャック 設計 Feistel構造 S-box SPN構造 攻撃 （暗号解読） 総当たり攻撃 レインボーテーブル 中間一致攻撃 線形解読法 差分解読法 切詰 高階 関連鍵攻撃 標準化 AES公募 CRYPTREC NESSIE 用語 初期化ベクトル 暗号利用モード カテゴリ

表 話 編 歴 暗号 暗号史 暗号解読 Cryptography portal en:Outline of cryptography 共通鍵暗号 ブロック暗号 ストリーム暗号 暗号利用モード 公開鍵暗号 暗号学的ハッシュ関数 メッセージ認証コード 認証付き暗号 乱数生成器 ステガノグラフィー

カテゴリ