Loading article…
差分暗号解読は、主にブロック暗号に適用できる暗号解読の一般的な形式ですが、ストリーム暗号や暗号学的ハッシュ関数にも適用できます。最も広い意味では、入力情報の違いが出力結果の違いにどのように影響するかを研究するものです。ブロック暗号の場合、変換ネットワークを通して違いを追跡し、暗号が非ランダムな動作を示す箇所を発見し、そのような特性を利用して秘密鍵（暗号鍵）を復元する一連の手法を指します。
差分暗号解読の発見と公表は、一般的に1980年代後半のエリ・ビハムとアディ・シャミアによるものとされている。彼らは、データ暗号化標準（DES）の理論的な脆弱性を含む、様々なブロック暗号とハッシュ関数に対する多数の攻撃を発表した。ビハムとシャミアは、DESは差分暗号解読に対して驚くほど耐性があるが、アルゴリズムにわずかな変更を加えるだけで、はるかに脆弱になることを指摘した。[ 1 ]： 8-9
1994年、IBM DESのオリジナルチームのメンバーであるドン・コッパースミスは、差分暗号解読は1974年にはすでにIBMに知られており、差分暗号解読への対策が設計目標であったと述べる論文を発表した。[ 2 ]著者のスティーブン・レヴィによれば、IBMは独自に差分暗号解読を発見しており、NSAもこの技術をよく知っていたようだ。[ 3 ]コッパースミスが説明するように、IBMはいくつかの秘密を隠していた。「NSAとの議論の後、設計上の考慮事項を開示すると、多くの暗号に対して使用できる強力な技術である差分暗号解読の技術が明らかになり、その結果、米国が暗号分野で他国に対して享受していた競争上の優位性が弱まることになると判断された。」[ 2 ] IBM内部では、差分暗号解読は「T攻撃」[ 2 ]または「ティックル攻撃」[ 4 ]として知られていた。
DESは差分暗号解読への耐性を念頭に置いて設計されたが、他の同時代の暗号は脆弱であることが判明した。攻撃の初期の標的となったのはFEALブロック暗号である。当初提案された4ラウンド版（FEAL-4）は、わずか8つの選択平文で解読でき、31ラウンド版のFEALでさえも攻撃を受ける可能性がある。対照的に、この方式では、約2⁴⁷個の選択平文でDESを暗号解読できる。
差分暗号解読は通常、選択平文攻撃であり、攻撃者は選択した平文の集合から暗号文を取得できなければなりません。ただし、既知の平文攻撃や暗号文のみの攻撃を可能にする拡張機能も存在します。基本的な方法は、一定の差で関連付けられた平文のペアを使用します。差はいくつかの方法で定義できますが、排他的論理和（XOR）演算が一般的です。次に、攻撃者は対応する暗号文の差を計算し、その分布における統計的パターンを検出することを期待します。結果として得られる差のペアは差分と呼ばれます。その統計的特性は暗号化に使用されるSボックスの性質に依存するため、攻撃者は差分を分析します。どこ （⊕は排他的論理和を表す）このようなSボックスSごとに。基本攻撃では、特定の暗号文の違いが特に頻繁に現れることが期待される。このようにして、暗号文をランダムな暗号文と区別することができる。より高度なバリエーションでは、総当たり探索よりも速く鍵を復元することができる。
差分暗号解読による鍵復元の最も基本的な形式では、攻撃者は多数の平文ペアの暗号文を要求し、差分が少なくともr − 1 ラウンド（rはラウンドの総数）にわたって維持されると仮定します。次に、攻撃者は、最終ラウンド前のブロック間の差分が固定されていると仮定して、どのラウンド鍵（最終ラウンド用）が使用可能かを推測します。ラウンド鍵が短い場合は、各ラウンド鍵で暗号文ペアを 1 ラウンドずつ網羅的に復号することで、これを実行できます。あるラウンド鍵が他のどの鍵よりもかなり頻繁に潜在的なラウンド鍵として認識された場合、その鍵が正しいラウンド鍵であるとみなされます。
特定の暗号方式では、攻撃を成功させるためには入力差分を慎重に選択する必要があります。アルゴリズムの内部構造の分析が行われ、標準的な方法は、暗号化のさまざまな段階を通して、高い確率で発生する差分の経路をたどることです。この差分は差分特性と呼ばれます。
差分暗号解読が一般に知られるようになって以来、それは暗号設計者の基本的な懸念事項となっている。新しい設計には、アルゴリズムがこの攻撃に対して耐性があるという証拠が伴うことが期待されており、Advanced Encryption Standardを含む多くの暗号がこの攻撃に対して安全であることが証明されている。[ 5 ]
この攻撃は、特定の入力値に対してのみ特定の入出力差パターンが発生するという事実に主眼を置いています。通常、この攻撃は非線形コンポーネントに対して、あたかもそれらが固体コンポーネントであるかのように適用されます（実際には、それらはルックアップテーブルまたはSボックスであることが多い）。選択された、または既知の2つの平文入力間の目的の出力差を観察することで、考えられる鍵の値が示唆されます。
例えば、1 => 1 の差分 (入力の最下位ビット(LSB) の差が出力の LSB の差につながることを意味する) が確率 4/256 で発生する場合 (例えば、 AES 暗号の非線形関数で可能)、その差分は 4 つの値 (または 2 つのペア) に対してのみ可能です。鍵が評価前に XOR され、差分を許容する値が {2,3} と {4,5} である非線形関数があるとします。攻撃者が {6, 7} の値を送信し、正しい出力の差分を観測した場合、鍵は 6 ⊕ K = 2 または 6 ⊕ K = 4 のいずれかであり、鍵 K は 2 または 4 のいずれかであることを意味します。
本質的に、暗号を攻撃から保護するには、nビットの非線形関数の場合、差分均一性を達成するために、2 −( n − 1 )にできるだけ近づけることが理想的です。こうなると、差分攻撃で鍵を特定するには、単に総当たり攻撃で鍵を特定するのと同じくらいの労力が必要になります。[ 6 ]
AES の非線形関数は、最大差分確率が 4/256 です (ただし、ほとんどのエントリは 0 または 2 です)。つまり、理論的には総当たり攻撃の半分の作業で鍵を特定できますが、AES の高ブランチにより、複数のラウンドにわたって高確率の痕跡が残ることはありません。実際、AES 暗号は、はるかに弱い非線形関数でも差分攻撃と線形攻撃に対して同様に耐性があります。非常に高いブランチ (アクティブな S ボックス数) が 25/4R であることは、8 ラウンドにわたって、50 未満の非線形変換を含む攻撃は存在しないことを意味し、成功確率は Pr[攻撃] ≤ Pr[S ボックスに対する最良の攻撃] 50を超えないことを意味します。たとえば、現在の S ボックスでは、AES は (4/256) 50または 2 −300を超える確率の固定差分を出力しません。これは、128 ビットのブロック暗号に必要なしきい値 2 −128よりもはるかに低い値です。これにより、より効率的なSボックスのためのスペースが確保され、たとえそれが16-均一であっても、攻撃の確率は依然として2-200であっただろう。
偶数サイズの入力/出力に対して2-均一性を持つ全単射は存在しません。奇数体（GF(2 7 )など）では、立方演算または反転演算（他の指数も使用可能）を用いて存在します。例えば、任意の奇数バイナリ体におけるS(x) = x 3は、差分暗号解読と線形暗号解読に対して耐性があります。これが、 MISTY設計で16ビット非線形関数に7ビット関数と9ビット関数が使用されている理由の一つです。これらの関数は、差分攻撃と線形攻撃に対する耐性が向上しますが、代数攻撃に対しては耐性を失います。 つまり、SATソルバーで記述および解くことが可能です。これが、AES（例えば）が反転後にアフィン写像を持つ理由の一つです。
