中間一致攻撃

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

概要[編集]

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

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

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

攻撃方法[編集]

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


  C=E_{K_2}(E_{K_1}(P))

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

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

関連項目[編集]

参考文献[編集]