二派閥攻撃

バイクリーク攻撃は、暗号解読法の中間者攻撃(MITM)の変形です。バイクリーク構造を利用して、MITM 攻撃による攻撃の可能性のあるラウンドの数を増やします。バイクリーク暗号解読は MITM 攻撃に基づいているため、ブロック暗号と(反復)ハッシュ関数の両方に適用できます。バイクリーク攻撃は、完全なAES ^[1]と完全なIDEA ^[2]の両方を弱体化させたことで知られていますが、ブルートフォース攻撃よりもわずかに優れているだけです。また、 KASUMI暗号や、 Skein-512およびSHA-2ハッシュ関数の原像解読耐性にも適用されています。 ^[3]

バイクリーク攻撃は、今でも（2019年4月現在^{[アップデート]}）AESに対する最も優れた公開された単一鍵攻撃です。この攻撃の計算量は、 AES128、AES192、AES256 の場合それぞれ 、です。これは、AES に対する公開された単一鍵攻撃の中で、全ラウンド数を攻撃する唯一のものです。^[1]これまでの攻撃では、ラウンド数を減らしたバリアント（通常は 7 または 8 ラウンドに減らしたバリアント）を攻撃していました。 ${\displaystyle 2^{126.1}}$${\displaystyle 2^{189.7}}$${\displaystyle 2^{254.4}}$

この攻撃の計算複雑度は であるため、これは理論的な攻撃であり、AES のセキュリティは破られておらず、AES の使用は比較的安全です。それでも、バイクリーク攻撃は興味深い攻撃であり、ブロック暗号の暗号解読を実行するための新しいアプローチを示唆しています。この攻撃により、AES で使用されるラウンド数の安全マージンに疑問が投げかけられたため、AES に関するより多くの情報も得られました。 ${\displaystyle 2^{126.1}}$

元々の MITM 攻撃は、 1977 年にDiffieとHellmanがDES の暗号解析特性について議論した際に初めて提案されました。^[4]彼らは、キー サイズが小さすぎるため、異なるキーを使用して DES を複数回再適用することがキー サイズの解決策になり得ると主張しました。ただし、MITM 攻撃があるため、ダブル DES の使用には反対し、最低でもトリプル DES を提案しました (MITM 攻撃はダブル DES に簡単に適用でき、セキュリティを から に低下させることができます。これは、平文と暗号文があれば、最初の DES 暗号化と 2 番目の DES 暗号化を個別にブルート フォース攻撃できるためです)。 ${\displaystyle 2^{56*2}}$${\displaystyle 2*2^{56}}$

ディフィーとヘルマンが MITM 攻撃を提案して以来、基本的な MITM 攻撃が適用できない状況で有用な多くのバリエーションが登場しました。バイクリーク攻撃のバリエーションは、ハッシュ関数暗号解読で使用するために、ドミトリー・ホヴラトビッチ、レヒバーガー、サヴェリーバによって最初に提案されました。 ^[5]しかし、ブロック暗号解読を含む秘密鍵設定にバイクリークの概念を適用する方法を示したのは、AES に対する攻撃を発表したボグダノフ、ホヴラトビッチ、レヒバーガーでした。これ以前は、AES や他の多くのブロック暗号に対する MITM 攻撃はほとんど注目されていませんでした。これは主に、MITM 攻撃を容易にするために 2 つの「MITM サブ暗号」間に独立した鍵ビットが必要であるためであり、これは AES などの多くの最新の鍵スケジュールでは実現が困難です。

ビクリーク構造の一般的な説明については、ビクリークの記事を参照してください。

MITM 攻撃では、第 1 および第 2 サブ暗号に属するキービットとが独立している必要があります。つまり、それらは互いに独立している必要があります。そうでないと、MITM 攻撃で平文と暗号文の一致する中間値を独立して計算できません (ブロックがキービットを共有できる MITM 攻撃のバリエーションがあります。3サブセット MITM 攻撃を参照してください)。この特性は、攻撃対象の暗号が拡散するため、多数のラウンドで悪用することが難しいことがよくあります。 ${\displaystyle K_{1}}$${\displaystyle K_{2}}$

簡単に言うと、攻撃するラウンド数が増えるほど、サブ暗号が大きくなります。サブ暗号が大きくなるほど、個別にブルートフォース攻撃しなければならないサブ暗号間の独立したキービットが少なくなります。もちろん、各サブ暗号の実際の独立したキービットの数は、キースケジュールの拡散特性によって異なります。

バイクリークが上記の問題に対処するのに役立つ方法は、たとえば、MITM 攻撃を使用して AES の 7 ラウンドを攻撃し、長さ 3 のバイクリーク構造 (つまり、暗号の 3 ラウンドをカバー) を利用することで、ラウンド 7 の開始時の中間状態を最後のラウンドの終了、たとえば 10 (AES128 の場合) にマッピングできるため、基本的な MITM 攻撃でその数のラウンドを攻撃できなかった場合でも、暗号の全ラウンド数を攻撃できるという点です。

したがって、バイクリークの意味は、MITM 攻撃の終了時の中間値を暗号文の終了時にマッピングできる構造を効果的に構築することです。中間状態が最後にどの暗号文にマッピングされるかは、もちろん暗号化に使用されるキーによって異なります。バイクリークで状態を暗号文にマッピングするために使用されるキーは、MITM 攻撃の 1 番目と 2 番目のサブ暗号でブルートフォースされたキービットに基づいています。

したがって、バイクリーク攻撃の本質は、MITM 攻撃に加えて、キービットに応じてバイクリーク構造を効果的に構築し、特定の中間状態を対応する暗号文にマッピングできることです。 ${\displaystyle K_{1}}$${\displaystyle K_{2}}$

中間状態と暗号文を取得し、それらの間をマッピングするキーを計算します。各中間状態はすべての暗号文にリンクされる必要があるため、キー回復が必要です。 ${\displaystyle 2^{d}}$${\displaystyle 2^{d}}$${\displaystyle 2^{2d}}$

（この方法は、ボグダノフ、ホヴラトビッチ、レッヒバーガーの論文「完全なAESの二クリーク暗号解析^[1]」で提案されました）

予備知識:
バイクリークの機能は、次のキーに基づいて中間値 を暗号文値 にマッピングすることであることを覚えておいてください。${\displaystyle S}$${\displaystyle C}$${\displaystyle K[i,j]}$
${\displaystyle \forall i,j:S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$

手順:
ステップ 1:中間状態 ( )、暗号文 ( )、およびキー ( ) が次のように選択されます。ここで、 は、指定されたキーを使用して中間状態を暗号文にマッピングする関数です。これは基本計算と呼ばれます。 ${\displaystyle S_{0}}$${\displaystyle C_{0}}$${\displaystyle K[0,0]}$${\displaystyle S_{0}{\xrightarrow[{f}]{K[0,0]}}C_{o}}$${\displaystyle f}$

ステップ 2:サイズの関連するキーの 2 セットが選択されます。キーは次のように選択されます。 ${\displaystyle 2^{d}}$

• 最初のキーセットは、基本計算に関して次の微分要件を満たすキーです。${\displaystyle f}$${\displaystyle 0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}}$
• 2 番目のキー セットは、基本計算に関して次の微分要件を満たすキーです。${\displaystyle f}$${\displaystyle \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0}$
• キーは、 - 微分と- 微分のトレイルが独立しているように、つまりアクティブな非線形コンポーネントを共有しないように選択されます。${\displaystyle \Delta _{i}}$${\displaystyle \nabla _{j}}$

言い換えると、
の入力差 0 は、のキー差の下での出力差にマップされる必要があります。すべての差は、基本計算に関してです。 の入力差 0 は、 のキー差の下で の出力差 0 にマップされる必要があります。すべての差は、基本計算に関してです。 ${\displaystyle \Delta _{i}}$${\displaystyle \Delta _{i}^{K}}$
${\displaystyle \nabla _{j}}$${\displaystyle \nabla _{J}^{K}}$

ステップ 3:トレイルは非線形コンポーネント (S ボックスなど) を共有しないため、トレイルを組み合わせて を取得できます。これは、 ステップ 2 の両方の微分の定義に準拠しています。基本計算からの タプル も、定義により両方の微分に準拠していることは明らかです。これは、微分が基本計算に関するものであるためです。2 つの定義のいずれかに を代入すると、およびであるためが生成されます。 つまり、基本計算のタプル も、組み合わせたトレイルに XOR 演算できます。
${\displaystyle 0{\xrightarrow[{f}]{\Delta _{i}^{K}}}\Delta _{i}\oplus \nabla _{j}{\xrightarrow[{f}]{\nabla _{j}^{K}}}0=\nabla _{j}{\xrightarrow[{f}]{\Delta _{i}^{K}\oplus \nabla _{j}^{K}}}\Delta _{i}}$

${\displaystyle (S_{0},C_{0},K[0,0])}$${\displaystyle S_{0},C_{0}}$ ${\displaystyle K[0,0]}$${\displaystyle 0{\xrightarrow[{f}]{0}}0}$${\displaystyle \Delta _{0}=0,\nabla _{0}=0}$${\displaystyle \Delta _{0}^{K}=0}$
${\displaystyle S_{0}\oplus \nabla _{j}{\xrightarrow[{f}]{K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}}C_{0}\oplus \Delta _{i}}$

ステップ 4: 次のことは簡単にわかります。 これを上記の複合微分トレイルに代入すると、結果は次のようになります。 これは、以前にバイクリークに対して上記で示した定義と同じです。
${\displaystyle S_{j}=S_{0}\oplus \nabla _{j}}$
${\displaystyle K[i,j]=K[0,0]\oplus \Delta _{i}^{K}\oplus \nabla _{j}^{K}}$
${\displaystyle C_{i}=C_{0}\oplus \Delta _{i}}$

${\displaystyle S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$

${\displaystyle \forall i,j:S_{j}{\xrightarrow[{f}]{K[i,j]}}C_{i}}$

したがって、サイズ(のバイクリークを作成できます。これは、最初のキー セットのすべてのキーを2 番目のキー セットのキーと組み合わせることができるためです。つまり、と上の微分値の計算のみを使用して、サイズ のバイクリークを作成できます。 の場合、バイクリーク内のすべてのキーも異なります。 ${\displaystyle 2^{2d}}$${\displaystyle 2^{2d}}$${\displaystyle 2^{d}}$${\displaystyle 2^{d}}$${\displaystyle 2^{2d}}$${\displaystyle 2*2^{d}}$${\displaystyle \Delta _{i}}$${\displaystyle \nabla _{j}}$${\displaystyle f}$${\displaystyle \Delta _{i}\neq \nabla _{j}}$${\displaystyle i+j>0}$${\displaystyle K[i,j]}$

この方法は、AES に対する主要なバイクリーク攻撃でバイクリークを構築する方法です。この手法でバイクリークを構築する場合、実際的な制限がいくつかあります。バイクリークが長くなるほど、差分トレイルがカバーするラウンド数が多くなります。したがって、暗号の拡散特性は、バイクリーク構築の有効性において重要な役割を果たします。

Bogdanov、Khovratovich、Rechbergerは、論文「完全なAESのBiclique暗号解析^[1]」の中で、「インターリーブ関連キー差分トレイル」と呼ばれるBicliqueを構築する別の方法についても説明しています。

ステップ 1:攻撃者は、すべての可能なキーを何らかの についてサイズの のキー サブセットにグループ化します。ここで、グループ内のキーは、サイズ の行列で のようにインデックス付けされます。攻撃者は、通常の MITM 攻撃と同様に、暗号を と( となる) の 2 つのサブ暗号に分割します。各サブ暗号のキー セットの基数は で、および と呼ばれます。サブ暗号の結合キーは、前述の行列 で表されます。 ${\displaystyle 2^{2d}}$${\displaystyle d}$${\displaystyle K[i,j]}$${\displaystyle 2^{d}\times 2^{d}}$${\displaystyle f}$${\displaystyle g}$${\displaystyle E=f\circ g}$${\displaystyle 2^{d}}$${\displaystyle K[i,0]}$${\displaystyle K[0,j]}$${\displaystyle K[i,j]}$

ステップ 2:攻撃者は、キーの各グループに対してバイクリークを構築します。バイクリークは、キーを使用して内部状態を暗号文にマッピングするため、次元が d です。「バイクリークの構築方法」のセクションでは、「独立した関連キー差分」を使用してバイクリークを構築する方法が示されています。その場合、バイクリークは、サブ暗号に属する キー セットおよびの差分を使用して構築されます。${\displaystyle 2^{2d}}$${\displaystyle 2^{d}}$${\displaystyle S_{j}}$${\displaystyle 2^{d}}$${\displaystyle C_{i}}$${\displaystyle 2^{2d}}$${\displaystyle K[i,0]}$${\displaystyle K[0,j]}$

ステップ 3:攻撃者は可能性のある暗号文を受け取り、復号化オラクルに対して一致する平文 を提供するように要求します。 ${\displaystyle 2^{d}}$${\displaystyle C_{i}}$${\displaystyle P_{i}}$

ステップ 4:攻撃者は内部状態と対応する平文を選択し、内部状態と平文から攻撃することで 、およびに対して通常の MITM 攻撃を実行します。${\displaystyle S_{j}}$${\displaystyle P_{i}}$${\displaystyle f}$${\displaystyle g}$

ステップ 5:と一致するキー候補が見つかった場合は、そのキーが別のプレーンテキスト/暗号テキストのペアでテストされます。キーが他のペアで検証された場合、正しいキーである可能性が高くなります。 ${\displaystyle S_{j}}$${\displaystyle P_{i}}$

^{以下の例は、論文「完全な AES の Biclique 暗号解析[1]}」の AES に対する biclique 攻撃に基づいています。
例の説明では、攻撃の作成者が使用したのと同じ用語 (変数名など) を使用しています。
簡単にするために、以下では AES128 バリアントに対する攻撃について説明します。
攻撃は 7 ラウンドの MITM 攻撃で構成され、最後の 3 ラウンドは biclique でカバーされます。

キー空間はキーのグループに分割され、各グループはキーで構成されます。 各グループに対して、基本計算用の一意のベースキーが選択されます。 ベースキーには、以下の表に示すように、ゼロに設定された特定の 2 つのバイトがあります (これは、AES128 の 4x4 マトリックスで AES が行うのと同じ方法でキーを表します)。${\displaystyle 2^{112}}$${\displaystyle 2^{16}}$
${\displaystyle 2^{112}}$${\displaystyle K[0,0]}$

${\displaystyle {\begin{bmatrix}-&-&-&0\\0&-&-&-\\-&-&-&-\\-&-&-&-\end{bmatrix}}}$

次に、キーの残りの 14 バイト (112 ビット) が列挙されます。これにより、キーのグループごとに 1 つずつ、一意のベース キーが生成されます。次に、各グループの 通常のキーが、そのベース キーに基づいて選択されます。これらは、ベース キーとほぼ同じになるように選択されます。以下に示す 4 バイトのうち、 2 バイト ( 's または's のいずれか) のみが異なります。${\displaystyle 2^{112}}$
${\displaystyle 2^{16}}$${\displaystyle i}$${\displaystyle j}$

${\displaystyle {\begin{bmatrix}-&-&i&i\\j&-&j&-\\-&-&-&-\\-&-&-&-\end{bmatrix}}}$

これにより、およびが生成され、これらを組み合わせると異なるキーが生成されます。これらのキーは、それぞれの基本キーのグループ内のキーを構成します。 ${\displaystyle 2^{8}K[i,0]}$${\displaystyle 2^{8}K[0,j]}$${\displaystyle 2^{16}}$${\displaystyle K[i,j]}$${\displaystyle 2^{16}}$

${\displaystyle 2^{112}}$バイクリークは、「バイクリークの構築方法」セクションで説明されているように、「独立した関連キー差分」手法を使用して構築されます。
この手法を使用するための要件は、組み合わせる必要のある前方差分トレイルと後方差分トレイルが、アクティブな非線形要素を共有しないことです。これが当てはまることはどのようにしてわかるのでしょうか。
ステップ 1 のキーが基本キーに関連して選択される方法により、キーを使用する差分トレイルは、キーを使用する差分トレイルとアクティブな S ボックス (AES で唯一の非線形コンポーネント) を共有することはありません。したがって、差分トレイルを XOR してバイクリークを作成できます。 ${\displaystyle \Delta _{i}}$${\displaystyle K[i,0]}$${\displaystyle \nabla _{j}}$${\displaystyle K[0,j]}$

バイクリークが作成されると、MITM 攻撃がほぼ開始されます。ただし、MITM 攻撃を実行する前に、平文からの中間値: 、暗号文からの中間値: 、および 対応する中間状態とサブキーまたは が事前に計算され、保存されます。 ${\displaystyle 2^{d}}$
${\displaystyle P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}}$
${\displaystyle 2^{d}}$
${\displaystyle {\xleftarrow[{v_{j}}]{}}{\xleftarrow[{}]{K[0,j]}}S_{j}}$
${\displaystyle K[i,0]}$${\displaystyle K[0,j]}$

これで MITM 攻撃を実行できます。キー をテストするには、暗号の部分を再計算するだけで済みます。この部分は、 と の間で変化することが分かっています。 からへの逆方向の計算では、再計算が必要な S ボックスは 4 個です。 からへの順方向の計算では、再計算が必要な S ボックスは 3 個だけです (必要な再計算の量に関する詳細な説明は、この例が引用されている「完全な AES の Biclique 暗号解析^[1]」論文に記載されています)。 ${\displaystyle K[i,j]}$${\displaystyle P_{i}{\xrightarrow[{}]{K[i,0]}}{\xrightarrow[{v_{i}}]{}}}$${\displaystyle P_{i}{\xrightarrow[{}]{K[i,j]}}{\xrightarrow[{v_{i}}]{}}}$${\displaystyle S_{j}}$${\displaystyle {\xleftarrow[{v_{j}}]{}}}$${\displaystyle P_{i}}$${\displaystyle {\xrightarrow[{v_{i}}]{}}}$

中間値が一致すると、と の間にキー候補が見つかります。次に、キー候補は別の平文/暗号文のペアでテストされます。 ${\displaystyle K[i,j]}$${\displaystyle P_{i}}$${\displaystyle S_{j}}$

この攻撃は、AES128 の計算の複雑さを に下げ、ブルートフォース攻撃よりも 3～5 倍高速化します。攻撃のデータ複雑さは で、メモリ複雑さは です。 ${\displaystyle 2^{126.18}}$${\displaystyle 2^{88}}$${\displaystyle 2^{8}}$