差分暗号解析の基礎

差分解読（BihamとShamir、1990年）は、平文ペアの差分が暗号を通じてどのように伝播するかを分析する選択平文攻撃です。高い確率で予測可能な出力差分を生じる入力差分を見つけることで、攻撃者は統計的に鍵のビットを復元します。

XORベースの暗号では、差分 ΔX = X XOR X' です。加算ベースの暗号では、差分 ΔX = X - X' mod 2^n です。XOR差分は、XORによる鍵付けと可換であり、差分ペアでは鍵スケジュールの影響が相殺されるため、最も一般的です。

差分ペア (P, P') は、入力差分 ΔP = P XOR P' を持ちます。暗号化後は (C, C') となり、出力差分 ΔC = C XOR C' を持ちます。有用な差分特性とは、高い確率 p で成立する ΔP → ΔC です。これは、差分ΔPを持つ多くの (P, P') ペアが出力差分ΔCを生じることを意味します。

DDT（Differential Distribution Table）は、各入力差分Δxと出力差分Δyについて、S(x) XOR S(x XOR Δx) = Δy を満たす入力xの個数を数えます。2^nで割ると確率になります。優れたSボックスのDDT最大値は2（確率1/2^{n-1}）であり、強い差分特性を持ちません。

rラウンドのブロック暗号では、各ラウンドの遷移確率が既知である系列 ΔP → ΔU1 → ΔU2 → ... → ΔU_{r-1} を見つけます。ラウンド間の確率を掛け合わせると、全体の確率は p = p1 * p2 * ... * p_{r-1} です。攻撃では2/p個のペアを使って最終ラウンド鍵を復元します。

確率の高いr-1ラウンド差分特性を使い、N = 2/p個の平文ペアを収集します。最終ラウンド鍵の各候補K'について、2つの暗号文を1ラウンド復号し、結果をXORして、差分がΔU_{r-1}と一致するかを確認します。正しいK'は約N/2回一致し、誤った鍵は約N/2^{bit_size}回一致します。

AESのSボックスは、GF(2^8)上の乗法逆元にアフィン変換を適用したものです。そのDDT最大値は256中4であり、Sボックスあたりの差分確率は4/256 = 1/64以下です。AESにはラウンドごとに4つのSボックスがありますが、Wide Trail設計により、完全な差分トレイルの確率は2^{-100}未満になります。

Joan DaemenのWide Trail設計（AES/Rijndaelで使用）では、MixColumnsの分岐数Bを定義します。1ラウンドを通る非自明な差分トレイルでは、少なくともB個のアクティブなSボックスが有効になります。4ラウンド × 1ラウンドあたり4個のSボックスにより、少なくとも25個のアクティブなSボックスが保証され、確率は2^{-100}未満になります。

切り捨て差分では、差分の一部だけを指定します。たとえば、正確な差分値ではなく、どの列がアクティブかだけを指定します。完全な差分が弱すぎる、より多くのラウンドに対する攻撃が可能になります。縮小ラウンド版のAES、SERPENT、その他のSPN暗号への攻撃に使用されます。

不可能差分とは、どの鍵を使っても発生しない差分ペア (ΔP, ΔC) です。この差分を持つ観測ペア (P, P') を写像する鍵はすべて排除できます。十分な数のペアを収集すると、誤った鍵がすべて排除され、正しい鍵だけが残ります。

ブーメラン攻撃（Wagner、1999年）は、2つの短い差分特性を組み合わせた適応的な選択平文・暗号文攻撃です。暗号を2つの部分に分解し、それぞれに確率の高い短い差分特性を適用することで、単一の差分特性だけでは攻撃できない長さの暗号を攻撃できます。

暗号解析における差分分布表（DDT）の目的は何ですか？

差分解読は、入力差分から出力差分への高確率な伝播を利用します。AESは、DDTに関して最適化されたSボックスとWide Trail設計によってこれに耐性を持ちます。次は線形解読と近似表です。