3 サブセット中間者攻撃

3サブセット meet-in-the-middle (以下、MITMと略す)攻撃は、一般的なmeet-in-the-middle 攻撃のバリエーションであり、暗号学におけるハッシュ暗号およびブロック暗号の暗号解読に使用されます。3 サブセット バリエーションは、MITM 攻撃で要求されるようにキービットを 2 つの独立したキー空間に分割することが簡単ではない暗号に MITM 攻撃を適用する可能性を開きます。

3 サブセットバリアントは、キー空間の交差部分をサブセットに移動することで、キー空間が独立しているという制限を緩和します。サブセットには、2 つのキー空間に共通するキービットが含まれます。

元々の MITM 攻撃は、1977 年にDiffieとHellmanがDES の暗号解析特性について議論した記事で初めて提案されました。 ^[1]彼らは、DES のキー サイズが小さすぎるため、異なるキーを使用して DES を複数回再適用することがキー サイズの問題の解決策になり得ると主張しました。ただし、MITM 攻撃 (DES は互いに独立したキーを持つ 2つのサブ暗号(最初の DES 暗号化と 2 番目の DES 暗号化) に簡単に分割できるため、ダブル DES は MITM 攻撃に対して非常に脆弱であり、基本的な MITM 攻撃によって計算の複雑さが から に削減されるため)を 考慮して、ダブル DES の使用は推奨しませんでした。${\displaystyle 2^{112}(=2^{2\times 56})}$${\displaystyle 2^{57}(=2\times 2^{56})}$

ディフィーとヘルマンが MITM 攻撃を提案して以来、多くのバリエーションが登場しています。これらのバリエーションは MITM 攻撃をより効果的にするか、基本的なバリエーションが使用できない状況で使用できるようにします。3 サブセット バリエーションは 2011 年にボグダノフとレヒバーガーによって示され、^[2]軽量ブロック暗号ファミリ KTANTAN などの暗号の暗号解読で使用されています。

一般的な MITM 攻撃と同様に、攻撃は 2 つのフェーズに分かれています。キー削減フェーズとキー検証フェーズです。最初のフェーズでは、MITM 攻撃を適用してキー候補のドメインが削減されます。2 番目のフェーズでは、見つかったキー候補が別のプレーンテキスト/暗号テキストのペアでテストされ、間違ったキーが除去されます。

キー削減フェーズでは、MITM 攻撃で通常行われるように、攻撃対象の暗号は 2 つのサブ暗号 と に分割され、それぞれに独立したキービットが与えられます。2 つのサブ暗号のキービットが独立している必要があるという制限に従う代わりに、3 サブセット攻撃では、暗号を 2 つのサブ暗号に分割し、一部のビットを両方のサブ暗号で使用することができます。 ${\displaystyle f}$${\displaystyle g}$

これは、キーを次の 3 つのサブセットに分割することによって行われます。

• ${\displaystyle A_{0}}$= 2 つのサブ暗号に共通するキービット。
• ${\displaystyle A_{1}}$= 最初のサブ暗号とは異なるキービット、${\displaystyle f.}$
• ${\displaystyle A_{2}}$= 2番目のサブ暗号に固有のキービット、${\displaystyle g}$

MITM 攻撃を実行するには、以下の手順に従って、3 つのサブセットを個別にブルートフォース攻撃します。

1. それぞれの推測について: ${\displaystyle A_{0}}$
   1. 平文から中間値を計算し、すべてのキービットの組み合わせについて${\displaystyle i}$${\displaystyle A_{1}}$
   2. すべてのキービットの組み合わせについて中間値を計算する。${\displaystyle j}$${\displaystyle A_{2}}$
   3. と を比較します。一致した場合は、それをキー候補として保存します。${\displaystyle i}$${\displaystyle j}$

キー削減フェーズで見つかった各キー候補は、別のプレーンテキスト/暗号文のペアでテストされます。これは、プレーンテキスト P の暗号化によって既知の暗号文 C が生成されるかどうかを確認するだけで行われます。通常、ここで必要なのは他のいくつかのペアのみであるため、3 サブセット MITM 攻撃のデータの複雑さは非常に小さくなります。

次の例は、Rechberger と Bogdanov が KTANTAN 暗号ファミリに対して行った攻撃に基づいています。この例では、彼らの論文で使用されている命名規則も使用されています。この攻撃により、KTANTAN32 の計算複雑度は、総当たり攻撃と比較すると から に削減されます。 の計算複雑度は2014 ですが、解読するのはまだ現実的ではないため、この攻撃は現時点では計算上実行可能ではありません。同じことが KTANTAN48 と KTANTAN64 にも当てはまり、その複雑度は例の最後で確認できます。 ${\displaystyle 2^{75.170}}$${\displaystyle 2^{80}}$${\displaystyle 2^{75.170}}$

この攻撃は、KTANTAN のビット単位のキースケジュールの弱点を悪用することで可能になります。すべてのバリエーションで同じキースケジュールが使用されるため、KTANTAN32、KTANTAN48、KTANTAN64 のいずれにも適用できます。KTANTAN と KANTAN のキースケジュールが異なるため、関連するブロック暗号の KANTAN ファミリには適用できません。

KTANTAN は軽量のブロック暗号で、RFIDタグなどの制約のあるプラットフォーム向けです。このようなプラットフォームでは、 AESなどの暗号化プリミティブは(ハードウェアを考えると) 不可能か、実装にコストがかかりすぎます。2009 年に Canniere、Dunkelman、Knezevic によって発明されました。^[3]ブロック サイズは 32、48、64 ビットのいずれかで、80 ビットのキーを使用して 254 ラウンドで暗号化します。各ラウンドでは、キーの 2 ビット (キー スケジュールによって選択) をラウンド キーとして使用します。

攻撃の準備として、3 サブセット MITM 攻撃を可能にする KTANTAN のキー スケジュールの弱点が特定されました。各ラウンドで使用されるキー ビットは 2 つだけなので、ラウンドごとのキーの拡散は小さく、安全性はラウンドの数にあります。キー スケジュールのこの構造により、特定のキー ビットをまったく使用しない連続ラウンドを多数見つけることができました。

より正確に言えば、攻撃の実行者は次のことを発見しました。

• ラウンド 1 から 111 ではキー ビットは使用されません。${\displaystyle k_{32},k_{39},k_{44},k_{61},k_{66},k_{75}}$
• 131 から 254 までのラウンドではキー ビットは使用されません。${\displaystyle k_{3},k_{20},k_{41},k_{47},k_{63},k_{74}}$

キースケジュールのこの特性は、3 サブセット MITM 攻撃をステージングするために使用されます。これにより、暗号を独立したキービットを持つ 2 つのブロックに分割できるようになります。攻撃のパラメータは次のようになります。

• ${\displaystyle A_{0}}$= 両方のブロックで使用されるキービット（つまり、上記に記載されていない残りの68ビット）
• ${\displaystyle A_{1}}$= 最初のブロックでのみ使用されるキービット（ラウンド1-111で定義）
• ${\displaystyle A_{2}}$= 2番目のブロックでのみ使用されるキービット（ラウンド131-254で定義）

キー削減フェーズのステップ 1.3 に問題があることに気付くかもしれません。はラウンド 111 の終わりに計算され、 はラウンド 131 の開始時に計算されるため、との値を直接比較することはできません。 これは、部分一致と呼ばれる別の MITM 手法によって緩和されます。著者らは、中間値 から順方向に計算し、中間値 から逆方向に計算することで、ラウンド 127 の時点で、確率 1 でと の両方で 8 ビットがまだ変更されていないことを発見しました。したがって、著者らは、それらの 8 ビットを比較することによって、状態の一部のみを比較しました (ラウンド 127 では KTANTAN32 では 8 ビットでした。ラウンド 123 では KTANTAN48 で 10 ビット、ラウンド 131 では KTANTAN64 で 47 ビットでした)。これを行うと、誤検知は増えますが、攻撃の複雑さが著しく増加することはありません。 ${\displaystyle i}$${\displaystyle j}$${\displaystyle i}$${\displaystyle j}$${\displaystyle i}$${\displaystyle j}$${\displaystyle i}$${\displaystyle j}$

KTANTAN32 では、中間値の状態の一部のみを照合することによる誤検知のため、キー候補を見つけるために平均 2 組のペアが必要になりました。KTANTAN48 と KTANTAN64 では、平均して、正しいキー候補をテストして見つけるために、プレーンテキストと暗号文のペアが 1 組だけ必要です。

のために：

• KTANTAN32 では、網羅的なキー検索と比較すると、上記の攻撃の計算量は です。データの複雑さは、平文/暗号文のペア 3 組です。${\displaystyle 2^{75.170}}$${\displaystyle 2^{80}}$
• KTANTAN48 では、計算量は であり、2 つの平文/暗号文のペアが必要です。${\displaystyle 2^{75.044}}$
• KTANTAN64 の場合、プレーンテキストと暗号テキストのペアが 2 つ必要です。${\displaystyle 2^{75.584}}$

結果はRechbergerとBogdanovによる論文から引用したものです。

これはもはやKTANTANに対する最良の攻撃ではありません。2011年時点で最良の攻撃は、Wei、Rechberger、Guo、Wu、Wang、Lingによるもので、KTANTANファミリーに対するMITM攻撃を改良したものです。^[4]彼らは、間接部分マッチングとスプライス＆カットMITM技術を使用して、選択された4つの平文/暗号文のペアで計算複雑度に到達しました。 ${\displaystyle 2^{72.9}}$