中間者攻撃

Generic space–time tradeoff cryptographic attack

中間者攻撃（MITM ）は既知平文攻撃であり^[1]、複数の暗号化演算を連続して実行することに依存する暗号化方式に対する、一般的な空間と時間のトレードオフを特徴とする暗号攻撃である。MITM攻撃は、ダブルDESが使用されない主な理由であり、トリプルDES鍵（168ビット）が攻撃者によって2 ^{56 の}空間と2 ^{112 の}演算で総当たり攻撃^{（ブルートフォース攻撃）される可能性がある[2]}。

説明

ブロック暗号のセキュリティを向上させようとする場合、複数の鍵を用いてデータを複数回暗号化するという魅力的なアイデアが考えられます。データの暗号化回数によっては、多重暗号化方式のセキュリティが2倍、あるいはn倍になると考える人もいるかもしれません。なぜなら、 kビットの鍵を用いてデータをn回暗号化した場合、すべての鍵の組み合わせを網羅的に探索する（単純なブルートフォース攻撃）には2 ^{n · k回の}試行が必要になるからです。

MITM攻撃は、複数の暗号化方式を用いることによるセキュリティ上の利点を弱める一般的な攻撃です。暗号化または復号の中間値を保存し、それらを用いて復号鍵の総当たり攻撃^{（[説明が必要]）}にかかる時間を短縮します。このため、中間者攻撃（MITM）は、空間と時間のトレードオフに基づく一般的な暗号攻撃となります。

MITM攻撃は、複数の関数（またはブロック暗号）の組み合わせにおける値域（暗号文）と定義域（平文）の両方を用いて鍵を見つけ出そうとします。最初の関数を通る順方向マッピングと最後の関数を通る逆方向マッピング（逆写像）が、文字通り合成された関数の真ん中で合流するようになります。例えば、Double DESは2つの異なる56ビット鍵でデータを暗号化しますが、Double DESは2 ^57回の暗号化と復号化の操作で解読可能です。

多次元 MITM (MD-MITM) は、上記で説明したように、複数の同時 MITM 攻撃の組み合わせを使用します。この場合、会議は合成関数内の複数の位置で発生します。

歴史

ディフィーとヘルマンは1977年に、仮想的なブロック暗号の拡張に対するミート・イン・ザ・ミドル攻撃を初めて提案しました。^[3]彼らの攻撃は、空間と時間のトレードオフを利用して、単一の暗号化方式を破るのに必要な時間のわずか2倍で、二重暗号化方式を破りました。

2011年、Bo ZhuとGuang Gongは多次元ミート・イン・ザ・ミドル攻撃を調査し、ブロック暗号GOST、KTANTAN、ハミングバード2に対する新しい攻撃を提示した。^[4]

ミート・イン・ザ・ミドル（1D-MITM）

与えられた平文Pと暗号文Cに対して、次の特性を持つ暗号化方式を攻撃したいとします。

${\displaystyle {\begin{aligned}C&={\mathit {ENC}}_{k_{2}}({\mathit {ENC}}_{k_{1}}(P))\\P&={\mathit {DEC}}_{k_{1}}({\mathit {DEC}}_{k_{2}}(C))\\\end{aligned}}}$

ここで、ENCは暗号化関数、DEC はENC ⁻¹ (逆マッピング)として定義された復号化関数、 k ₁とk ₂は 2 つのキーです。

この暗号化方式をブルートフォース攻撃する単純な方法は、暗号文をあらゆる可能なk ₂で復号化し、中間出力のそれぞれをあらゆる可能なk ₁で復号化して、合計 2 ^{| k ₁ |} × 2 ^{| k ₂ |} (または 2 ^{| k ₁ |+| k ₂ |} ) 回の演算を実行することです。

中間者攻撃はより効率的なアプローチを用いる。Cをk 2_で復号すると、以下の等価性が得られる。

${\displaystyle {\begin{aligned}C&={\mathit {ENC}}_{k_{2}}({\mathit {ENC}}_{k_{1}}(P))\\{\mathit {DEC}}_{k_{2}}(C)&={\mathit {DEC}}_{k_{2}}({\mathit {ENC}}_{k_{2}}[{\mathit {ENC}}_{k_{1}}(P)])\\{\mathit {DEC}}_{k_{2}}(C)&={\mathit {ENC}}_{k_{1}}(P)\\\end{aligned}}}$

攻撃者は、 k ₁のすべての値に対してENC _{k 1} ( P ) を、 k ₂のすべての可能な値に対してDEC _{k 2} ( C ) を計算できます。合計 2 ^{| k ₁ |} + 2 ^{| k ₂ |} (または、k ₁とk ₂のサイズが同じ場合は2 ^{| k ₁ |+1 ) 回の演算を実行します。} ENC _{k 1} ( P ) 演算のいずれかの結果がDEC _{k 2} ( C ) 演算の結果と一致する場合、 k ₁とk ₂のペアは正しい鍵である可能性があります。この正しい可能性のある鍵は候補鍵と呼ばれます。攻撃者は、平文と暗号文の2番目のテストセットを使用して候補鍵をテストすることにより、どの候補鍵が正しいかを判断できます。

MITM攻撃は、データ暗号化規格（DES）がダブルDESではなくトリプルDESに置き換えられた理由の一つです。攻撃者は、2 ^57回の演算と2 ^56回の空間でダブルDESをブルートフォース攻撃することができ、DESと比べてわずかな改良点にしかなりません。^{[4]トリプルDESは「3倍長」（168ビット）の鍵を使用し、2 56回の}空間と2 ^112回の演算で中間者攻撃に対して脆弱ですが、鍵空間のサイズが大きいため安全であると考えられています。^{[2] [5]}

1D-MITM攻撃の図解

MITMアルゴリズム

以下を計算します。

• ${\displaystyle {\mathit {SubCipher}}_{1}={\mathit {ENC}}_{f_{1}}(k_{f_{1}},P),\;\forall k_{f_{1}}\in K}$:

  それぞれを対応するセットAに保存する ${\displaystyle {\mathit {SubCipher}}_{1}}$ ${\displaystyle k_{f_{1}}}$

• ${\displaystyle {\mathit {SubCipher}}_{1}={\mathit {DEC}}_{b_{1}}(k_{b_{1}},C),\;\forall k_{b_{1}}\in K}$:

  そして、それぞれの新しいものをセットAと比較する ${\displaystyle {\mathit {SubCipher}}_{1}}$

一致が見つかった場合、候補となる鍵ペアをテーブルTに保存します。T 内の鍵ペアを新しい⁠ ⁠のペアでテストし、有効性を確認します。この新しいペアで鍵ペアが機能しない場合は、新しい⁠ ⁠のペアで再度 MITM を実行します。 ${\displaystyle k_{f_{1}},k_{b_{1}}}$ ${\displaystyle (P,C)}$ ${\displaystyle (P,C)}$

MITMの複雑さ

キーサイズがkの場合、この攻撃では、2 ^{k +1回の}暗号化（および復号化）と、ルックアップテーブルへの順方向計算の結果を格納するためのO（2 ^{k ）のメモリのみが使用されます。これは、2 2· k}回の暗号化とO （1）のメモリを必要とするナイーブな攻撃とは対照的です。

多次元MITM（MD-MITM）

1D-MITM攻撃は効果的ですが、より洗練された攻撃手法が開発されています。多次元中間者攻撃（ MD-MITMとも略されます）です。これは、データが2つ以上の異なる鍵を用いた暗号化で暗号化されている場合に適しています。中間者攻撃（シーケンス内の1箇所）ではなく、MD-MITM攻撃では、暗号内の複数の位置で順方向および逆方向の計算を行い、複数の特定の中間状態に到達しようとします。^[4]

暗号化と復号化が前と同じように定義されているブロック暗号に対して攻撃を実行する必要があると仮定します。

${\displaystyle C={\mathit {ENC}}_{k_{n}}({\mathit {ENC}}_{k_{n-1}}(...({\mathit {ENC}}_{k_{1}}(P))...))}$

${\displaystyle P={\mathit {DEC}}_{k_{1}}({\mathit {DEC}}_{k_{2}}(...({\mathit {DEC}}_{k_{n}}(C))...))}$

つまり、平文Pは同じブロック暗号の繰り返しを使用して複数回暗号化される。

MD-MITM攻撃の図解

MD-MITMは、GOSTブロック暗号をはじめ多くの暗号の解読に使用されており、3D-MITMによって攻撃にかかる時間が大幅に短縮されることが示されています。^[4]

MD-MITMアルゴリズム

以下を計算します。

${\displaystyle {\mathit {SubCipher}}_{1}={\mathit {ENC}}_{f_{1}}(k_{f_{1}},P)\qquad \forall k_{f_{1}}\in K}$

それぞれを対応するものとセットで保存します。 ${\displaystyle {\mathit {SubCipher}}_{1}}$ ${\displaystyle k_{f_{1}}}$ ${\displaystyle H_{1}}$

${\displaystyle {\mathit {SubCipher}}_{n+1}={\mathit {DEC}}_{b_{n+1}}(k_{b_{n+1}},C)\qquad \forall k_{b_{n+1}}\in K}$

それぞれを対応するものとセットで保存します。 ${\displaystyle {\mathit {SubCipher}}_{n+1}}$ ${\displaystyle k_{b_{n+1}}}$ ${\displaystyle H_{n+1}}$

中間状態に関する可能性のある推測ごとに、以下を計算します。 ${\displaystyle s_{1}}$

${\displaystyle {\mathit {SubCipher}}_{1}={\mathit {DEC}}_{b_{1}}(k_{b_{1}},s_{1})\qquad \forall k_{b_{1}}\in K}$

そして、これとセットの間の各一致について、新しいセット にと を保存します。 ${\displaystyle {\mathit {SubCipher}}_{1}}$ ${\displaystyle H_{1}}$ ${\displaystyle k_{b_{1}}}$ ${\displaystyle k_{f_{1}}}$ ${\displaystyle T_{1}}$

${\displaystyle {\mathit {SubCipher}}_{2}={\mathit {ENC}}_{f_{2}}(k_{f_{2}},s_{1})\qquad \forall k_{f_{2}}\in K}$^{[確認が必要です]}

それぞれを対応するものとセットで保存します。 ${\displaystyle {\mathit {SubCipher}}_{2}}$ ${\displaystyle k_{f_{2}}}$ ${\displaystyle H_{2}}$

中間状態の各可能な推測に対して、以下を計算します。 ${\displaystyle s_{2}}$

• ${\displaystyle {\mathit {SubCipher}}_{2}={\mathit {DEC}}_{b_{2}}(k_{b_{2}},s_{2})\qquad \forall k_{b_{2}}\in K}$

  そして、これと集合の間の各一致について、 ${\displaystyle {\mathit {SubCipher}}_{2}}$ ${\displaystyle H_{2}}$

  一致したら、サブキーの組み合わせを新しいセットにまとめて保存します。 ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

• 中間状態の各可能な推測に対して、以下を計算します。 ${\displaystyle s_{n}}$

1. ${\displaystyle {\mathit {SubCipher}}_{n}={\mathit {DEC}}_{b_{n}}(k_{b_{n}},s_{n})\qquad \forall k_{b_{n}}\in K}$そして、これとセットの間の各一致について、 と一致するかどうかも確認し、と を新しいセット に保存します。 ${\displaystyle {\mathit {SubCipher}}_{n}}$ ${\displaystyle H_{n}}$ ${\displaystyle T_{n-1}}$ ${\displaystyle k_{b_{n}}}$ ${\displaystyle k_{f_{n}}}$ ${\displaystyle T_{n}}$
2. ${\displaystyle {\mathit {SubCipher}}_{n+1}={\mathit {ENC}}_{f_{n}+1}(k_{f_{n}+1},s_{n})\qquad \forall k_{f_{n+1}}\in K}$そして、これと集合との間の各一致について、それが とも一致するかどうかを確認します。一致する場合、次のようになります。 ${\displaystyle {\mathit {SubCipher}}_{n+1}}$ ${\displaystyle H_{n+1}}$ ${\displaystyle T_{n}}$

見つかったサブキーの組み合わせを 別のプレーンテキスト/暗号文のペアで使用して、キーの正確性を検証します。 ${\displaystyle (k_{f_{1}},k_{b_{1}},k_{f_{2}},k_{b_{2}},...,k_{f_{n+1}},k_{b_{n+1}})}$

_{アルゴリズムのネストされた要素に注目してください。s j}のあらゆる可能な値の推測は、前のs j _-1の推測ごとに行われます。これは_、このMD-MITM攻撃の全体的な時間計算量に対して指数関数的な複雑さをもたらす要素です。

MD-MITMの複雑さ

ブルートフォースを使わないこの攻撃の時間計算量は⋅ ⋅ ${\displaystyle 2^{|k_{f_{1}}|}+2^{|k_{b_{n+1}}|}+2^{|s_{1}|}}$ ${\displaystyle (2^{|k_{b_{1}}|}+2^{|k_{f_{2}}|}+2^{|s_{2}|}}$ ${\displaystyle (2^{|k_{b_{2}}|}+2^{|k_{f_{3}}|}+\cdots ))}$

メモリの複雑さに関しては、が最初に構築された候補値のテーブルよりもはるかに小さいことが簡単にわかります 。iが増加すると、 に含まれる候補値が満たす必要がある条件が増えるため、最終宛先に渡される候補の数は少なくなります。 ${\displaystyle T_{2},T_{3},...,T_{n}}$ ${\displaystyle T_{1}}$ ${\displaystyle T_{i}}$ ${\displaystyle T_{n}}$

MD-MITMのメモリ複雑度の上限は

${\displaystyle 2^{|k_{f_{1}}|}+2^{|k_{b_{n+1}}|}+2^{|k|-|s_{n}|}\cdots }$

ここで、k はキー全体の長さ（結合後）を表します。

データの複雑さは、誤ったキーが通過する確率（偽陽性となる確率）に依存します。これは です。ここで、lは最初の MITM フェーズにおける中間状態です。中間状態のサイズとブロックサイズは多くの場合同じです。また、最初の MITM フェーズ後にテスト用に残されるキーの数も考慮すると、 となります。 ${\displaystyle 1/2^{|l|}}$ ${\displaystyle 2^{|k|}/2^{|l|}}$

したがって、最初の MITM フェーズの後には、（ブロック サイズ）が存在します。 ${\displaystyle 2^{|k|-b}\cdot 2^{-b}=2^{|k|-2b}}$ ${\displaystyle |b|}$

キーの最終候補値が新しい平文/暗号文のペアでテストされるたびに、合格するキーの数に、キーが合格する確率が掛けられます。 ${\displaystyle 1/2^{|b|}}$

ブルートフォーステストの部分 (新しい⁠ ⁠ ${\displaystyle (P,C)}$ペアに対する候補キーのテスト) には時間計算量があり 、明らかに指数の b の倍数が増えると、数はゼロに近づきます。 ${\displaystyle 2^{|k|-b}+2^{|k|-2b}+2^{|k|-3b}+2^{|k|-4b}\cdots }$

データの複雑さに関する結論は、同様の推論により、⁠ ⁠ペアに関する推論によって制限されます。 ${\displaystyle \lceil |k|/n\rceil }$ ${\displaystyle (P,C)}$

以下は 2D-MITM の取り付け方法の具体的な例です。

2D-MITMの一般的な例

2D-MITM がブロック暗号にどのように実装されるかについての一般的な説明です。

2次元MITM（2D-MITM）では、平文を多重暗号化することで2つの中間状態に到達します。下の図をご覧ください。

2D-MITM攻撃の図解

2D-MITMアルゴリズム

以下を計算します。

${\displaystyle {\mathit {SubCipher}}_{1}={\mathit {ENC}}_{f_{1}}(k_{f_{1}},P)\qquad \forall k_{f_{1}}\in K}$

それぞれを対応するセットAに保存する ${\displaystyle {\mathit {SubCipher}}_{1}}$ ${\displaystyle k_{f_{1}}}$

${\displaystyle {\mathit {SubCipher}}_{2}={\mathit {DEC}}_{b_{2}}(k_{b_{2}},C)\qquad \forall k_{b_{2}}\in K}$

それぞれを対応するものとまとめてセット B に保存します。 ${\displaystyle {\mathit {SubCipher}}_{2}}$ ${\displaystyle k_{b_{2}}}$

と の間の中間状態sに関する可能な推測ごとに、 以下を計算します。 ${\displaystyle {\mathit {SubCipher}}_{1}}$ ${\displaystyle {\mathit {SubCipher}}_{2}}$

• ${\displaystyle {\mathit {SubCipher}}_{1}={\mathit {DEC}}_{b_{1}}(k_{b_{1}},s)\qquad \forall k_{b_{1}}\in K}$

  そして、これとセット A の間の各一致について、新しいセット T に保存します。 ${\displaystyle {\mathit {SubCipher}}_{1}}$ ${\displaystyle k_{b_{1}}}$ ${\displaystyle k_{f_{1}}}$

• ${\displaystyle {\mathit {SubCipher}}_{2}={\mathit {ENC}}_{f_{2}}(k_{f_{2}},s)\qquad \forall k_{f_{2}}\in K}$

  そして、これと集合Bの間の各一致について、それがTと一致するかどうかも確認する。 ${\displaystyle {\mathit {SubCipher}}_{2}}$

  この場合は次のようになります。

見つかったサブキーの組み合わせを別のプレーンテキスト/暗号文のペアで使用して、キーの正確性を検証します。 ${\displaystyle (k_{f_{1}},k_{b_{1}},k_{f_{2}},k_{b_{2}})}$

2D-MITMの複雑さ

ブルートフォースを使わないこの攻撃の時間計算量は

${\displaystyle 2^{|k_{f_{1}}|}+2^{|k_{b_{2}}|}+2^{|s|}\cdot \left(2^{|k_{b_{1}}|}+2^{|k_{f_{2}}|}\right)}$

ここで |⋅| は長さを表します。

メインメモリの消費量は、 Tが他のものよりはるかに小さいセットAとBの構成によって制限されます。

データの複雑さについては、MD-MITM の複雑さに関するサブセクションを参照してください。

参照

• 誕生日攻撃
• ワイヤレスセキュリティ
• 暗号化
• 3サブセットミートインザミドル攻撃
• 部分一致ミート・イン・ザ・ミドル攻撃

参考文献

1. 「Crypto-IT」.
2. Moore, Stephane (2010年11月16日). 「Meet-in-the-Middle攻撃」(PDF) : 2. {{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要です
3. ^ Diffie, Whitfield; Hellman, Martin E. (1977年6月). 「NBSデータ暗号化規格の徹底的な暗号解析」(PDF) . Computer . 10 (6): 74– 84. doi :10.1109/CM.1977.217750. S2CID  2412454.
4. Zhu, Bo; Gong, Guang (2014). 「多次元ミート・イン・ザ・ミドル攻撃とKATAN32/48/64への応用」 .暗号と通信. 6 (4): 313– 333. doi :10.1007/s12095-014-0102-9 – Springer Link経由.
5. Blondeau, Céline. 「講義3：ブロック暗号」（PDF） . CS-E4320 暗号化とデータセキュリティ. 2018年2月23日時点のオリジナル（PDF）からアーカイブ。 2018年2月22日閲覧。

Retrieved from "https://en.wikipedia.org/w/index.php?title=Meet-in-the-middle_attack&oldid=1307954643"