リバウンド攻撃

リバウンド攻撃は、暗号ハッシュ関数の暗号解読に使用されるツールです。この攻撃は、2009 年に Florian Mendel、Christian Rechberger、Martin Schläffer、Søren Thomsen によって初めて公開されました。これは、WhirlpoolやGrøstlなどのAESのような関数を攻撃するために考案されましたが、後にKeccak、JH、Skeinなどの他の設計にも適用できることが示されました。

リバウンド攻撃はハッシュ関数に対する統計的攻撃の一種であり、回転暗号解析や差分暗号解析などの技術を使用して衝突やその他の興味深い特性を見つけます。

攻撃の基本的な考え方は、ブロック暗号（またはその一部）、順列、または別の種類のプリミティブにおける特定の差分特性を観察することです。特性を満たす値を見つけるには、プリミティブを3 つの部分に分割します。はインバウンド フェーズと呼ばれ、とを合わせてアウトバウンド フェーズと呼ばれます。次に、攻撃者は、インバウンド フェーズで差分特性の一部を決定論的に実現し、特性の残りを確率的に満たす値を選択します。 ${\displaystyle E}$${\displaystyle E=E_{\text{fw}}\circ E_{\text{in}}\circ E_{\text{bw}}}$${\displaystyle E_{\text{in}}}$${\displaystyle E_{\text{fw}}}$${\displaystyle E_{\text{bw}}}$

したがって、リバウンド攻撃は次の 2 つのフェーズで構成されます。

1. インバウンド（または中間一致）フェーズでは、確率的に満たすのが難しい微分特性の部分が扱われます。ここでの目標は、平均複雑度が低い特性のこの部分に対する多くの解を見つけることです。これを達成するには、このフェーズで特性を記述する対応する方程式系が不確定である必要があります。したがって、解を探すときには多くの自由度があり、多くの解が考えられます。インバウンドフェーズは、アウトバウンドフェーズが成功する可能性が高くなるように十分な数の開始点を得るために、複数回繰り返すことができます。
2. アウトバウンド フェーズでは、インバウンド フェーズの各ソリューションが両方向に伝播され、このフェーズでも特性が保持されるかどうかが確認されます。アウトバウンド フェーズでの特性の確率は可能な限り高くする必要があります。

インバウンドフェーズと 2 つのアウトバウンドフェーズを使用する利点は、インバウンドフェーズで微分特性の難しい部分を効率的に計算できることです。さらに、アウトバウンドフェーズでの高い確率が保証されます。したがって、微分特性を見つける全体的な確率は、標準的な微分手法を使用する場合よりも高くなります。

AESのような置換順列ブロック暗号を圧縮関数として使用するハッシュ関数を考えてみましょう。この圧縮関数は、S ボックスと線形変換で構成される複数のラウンドで構成されています。攻撃の一般的な考え方は、最も計算コストの高い部分が中央にある差分特性を構築することです。この部分はインバウンド フェーズでカバーされ、特性の達成が容易な部分はアウトバウンド フェーズでカバーされます。インバウンド フェーズで特性を記述する方程式のシステムは、アウトバウンド フェーズの開始点を多数生成できるように、不確定である必要があります。特性のより困難な部分はインバウンド フェーズに含まれているため、ここでは標準の差分を使用できますが、アウトバウンド フェーズでは、より高い確率を達成するために切り捨て差分が使用されます。

インバウンドフェーズでは通常、最初に少数のアクティブ状態バイト（ゼロ以外の差異を持つバイト）があり、ラウンドの途中でそれが多数のアクティブバイトに伝播し、フェーズの終わりに少数のアクティブバイトに戻ります。アイデアは、フェーズの途中でS-boxの入力と出力に多数のアクティブバイトを持たせることです。その後、インバウンドフェーズの開始時と終了時の差異の値を選択し、これを中間に向かって伝播させ、S-boxの入力と出力で一致を探すことで、特性を効率的に計算できます。AES のような暗号の場合、これは通常、行方向または列方向に実行できるため、手順が比較的効率的になります。異なる開始値と終了値を選択すると、インバウンドフェーズで多くの異なる差分特性が得られます。

アウトバウンドフェーズの目標は、インバウンドフェーズで見つかった特性を前後に伝播し、目的の特性が従われているかどうかを確認することです。ここでは、通常は切り捨てられた差分が使用されます。これは、より高い確率を与えるためであり、差分の特定の値は衝突を見つけるという目標とは無関係です。特性がアウトバウンドフェーズの目的のパターンに従う確率は、アクティブバイトの数と、これらが特性内でどのように配置されているかによって異なります。衝突を実現するには、アウトバウンドフェーズの差分が特定のタイプであるだけでは不十分です。特性の開始時と終了時のアクティブバイトも、フィードフォワード操作がキャンセルされるような値を持っている必要があります。したがって、特性を設計するときは、アウトバウンドフェーズの開始時と終了時の任意の数のアクティブバイトが同じ位置にある必要があります。これらのバイトがキャンセルされる確率は、アウトバウンド特性の確率に加算されます。

全体的に、アウトバウンド フェーズで予想される正しい特性の数を 1 つより多くするには、インバウンド フェーズで十分な数の特性を生成する必要があります。さらに、キャンセルされない いくつかのアクティブバイトでアウトバウンド フェーズを開始および終了することにより、より多くのラウンドでニア コリジョンを実現できます。

リバウンド攻撃は、圧縮関数( AESのようなブロック暗号、W) が 4.5 ラウンドまたは 5.5 ラウンドに削減されたバリアントでの衝突を見つけるために、ハッシュ関数 Whirlpoolに対して使用できます。衝突に近い状態は、6.5 ラウンドと 7.5 ラウンドで見つかります。以下は、4.5 ラウンド攻撃の説明です。

リバウンド攻撃を効果的にするために、攻撃前にSボックスの差のルックアップテーブルを計算します。Sボックスを表すとします。次に、各ペアについて、方程式の 解（存在する場合） を見つけます。${\displaystyle S:\{0,1\}^{8}\to \{0,1\}^{8}}$${\displaystyle (a,b)\in \{0,1\}^{8}}$${\displaystyle x}$

${\displaystyle S(x)\oplus S(x\oplus a)=b}$、

ここで、 はS ボックスの入力差を表し、 は出力差を表します。この 256 x 256 の表 (差分布表、DDT と呼ばれる) により、S ボックスを通過する特定の入力/出力ペアの特性に従う値を見つけることができます。右側の表は、方程式の可能な解の数とその発生頻度を示しています。最初の行は不可能な微分を表し、最後の行はゼロ微分を表します。 ${\displaystyle a}$${\displaystyle b}$

Whirlpoolの 4.5 ラウンドで衝突を見つけるには、下の表に示すタイプの差分特性を見つける必要があります。この特性には、赤でマークされたアクティブ バイト (ゼロ以外の差を持つバイト) の最小値があります。特性は、各ラウンドのアクティブ バイトの数で説明できます (例: 1 → 8 → 64 → 8 → 1 → 1)。

インバウンド フェーズの目標は、アクティブ バイト 8 → 64 → 8 のシーケンスによって記述される特性の一部を満たす差異を見つけることです。これは、次の 3 つの手順で実行できます。

1. ラウンド 3 のMixRows操作の出力で、8 つのアクティブ バイトに対して任意の非ゼロの差を選択します。これらの差は、ラウンド 3 のSubBytes操作の出力に逆方向に伝播されます。MixRows操作の特性により、完全にアクティブな状態が得られます。これは、各行に対して個別に実行できることに注意してください。
2. ラウンド 2 の MixRows 操作の入力で各アクティブ バイトの差を選択し、これらの差をラウンド 3 の SubBytes 操作の入力に伝播します。各バイトの 255 個のゼロ以外の差すべてに対してこれを実行します。これも、行ごとに個別に実行できます。
3. 中間一致ステップでは、DDT テーブルを使用して、ステップ 1 と 2 で見つかった入力/出力の差を、第 3 ラウンドの SubBytes 操作に一致させます。各行は独立してチェックでき、予想されるソリューションの数はS ボックスあたり 2 です。合計で、差分特性に従う値の予想数は 2 ⁶⁴です。

^{これらのステップは、ステップ 1 で 2 64 個}の異なる開始値を使用して繰り返すことができ、その結果、インバウンド フェーズで微分特性に従う合計 2 ^{128 個の実際の値が生成されます。2 64}個の値の各セットは、事前計算ステップにより、 2 ⁸ラウンドの変換の複雑さで見つけることができます。

アウトバウンドフェーズは、確率的な方法で微分特性を完成させます。アウトバウンドフェーズでは、インバウンドフェーズとは対照的に、切り捨て微分を使用します。インバウンドフェーズで見つかった各開始点は、前方と後方に伝播されます。目的の特性に従うためには、8 つのアクティブバイトが両方向に 1 つのアクティブバイトに伝播する必要があります。このような 8 から 1 への遷移は 2 ⁻⁵⁶の確率で発生するため、^{[1]特性が満たされる確率は 2 −112}です。衝突を確実に起こすには、フィードフォワード操作中に特性の開始時と終了時の値がキャンセルされる必要があります。これは約 2 ⁻⁸の確率で発生するため、アウトバウンドフェーズの全体的な確率は 2 ⁻¹²⁰になります。

衝突を見つけるには、インバウンドフェーズで2 ^{120 個}の開始点を生成する必要があります。これは開始点あたり平均1の複雑度で実行できるため、 ^[2]攻撃の全体的な複雑度は2 ¹²⁰です。

基本的な4.5ラウンド攻撃は、インバウンドフェーズで2つの完全にアクティブな状態を使用することで5.5ラウンド攻撃に拡張できます。これにより、複雑さは約2 ¹⁸⁴に増加します。^[3]

アウトバウンドフェーズを8つのアクティブバイトで開始および終了するように拡張すると、 Whirlpoolでは52バイトで衝突に近い状態になり、^{複雑さは2192}で7.5ラウンドに減少します。^[4]

攻撃者が連鎖値、つまりWhirlpoolの鍵スケジュールへの入力を制御していると仮定すると、攻撃は52バイトのセミフリースタートニアコリジョンで9.5ラウンドまで拡張され、複雑さは2128になる^。 [ ^5]

• リバウンド攻撃: 縮小された渦巻きとグロストルの暗号解読、Florian Mendel、Christian Rechberger、Martin Schlaffer、Soren S. Thomsen 著 (Fast Software Encryption 2009: 260-276)
• Florian Mendel、Christian Rechberger、Martin Schlaffer、Soren S. Thomsen による「縮小グロストル ハッシュ関数に対するリバウンド攻撃」(RSA カンファレンス 2010 の暗号学者トラック: 350-365)
• 非整列リバウンド攻撃 - Keccak への応用、Alexandre Duc、Jian Guo、Thomas Peyrin、Lei Wei (IACR Cryptology ePrint Archive Year 2011 / 420)
• リバウンド攻撃を改善する方法、María Naya-Plasencia FHNW、Windisch、スイス (CRYPTO'11 Proceedings of the 31st annual conference on Advances in cryptology、188-205 ページ)
• Mario Lamberger、Florian Mendel、Christian Rechberger、Vincent Rijmen、Martin Schläffer による「リバウンド攻撃とサブスペース識別子: Whirlpool への応用」(IACR Cryptology ePrint Archive、2010 年 /198 ページ)。
• AES ベースのハッシュ関数の暗号解析 Martin Schläffer 博士論文