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 47の選択平文程度の労力で DES を正常に解読できます。
攻撃の仕組み
差分暗号解読法は通常、選択平文攻撃であり、つまり、攻撃者は選択した平文セットの暗号文を取得できなければなりません。ただし、既知の平文や暗号文のみの攻撃を可能にする拡張機能もあります。基本的な方法では、一定の差によって関連付けられた平文のペアを使用します。差はいくつかの方法で定義できますが、排他的論理和 (XOR)演算が一般的です。次に、攻撃者は対応する暗号文の差を計算し、その分布の統計パターンを検出しようとします。結果として得られる差のペアは差分と呼ばれます。その統計的特性は暗号化に使用されるS ボックスの性質に依存するため、攻撃者は、各 S ボックスS について、 （および ⊕ は排他的論理和を表す） の差分 を分析します。基本的な攻撃では、特定の暗号文の差が特に頻繁に発生することが予想されます。このようにして、暗号をランダムと区別できます。より洗練されたバリエーションでは、網羅的な検索よりも速くキーを復元できます。
差分暗号解析による鍵回復の最も基本的な形式では、攻撃者は多数の平文ペアの暗号文を要求し、差分が少なくともr − 1ラウンド（ rはラウンドの総数）まで保持されると想定します。[5]次に、攻撃者は、最終ラウンド前のブロック間の差が固定されていると仮定して、どのラウンドキー（最終ラウンド用）が可能かを推測します。ラウンドキーが短い場合、これは、可能性のある各ラウンドキーを使用して1ラウンドの暗号文ペアを徹底的に復号するだけで実現できます。1つのラウンドキーが他のどのキーよりもかなり頻繁に潜在的なラウンドキーと見なされた場合、そのラウンドキーは正しいラウンドキーであると想定されます。
特定の暗号の場合、攻撃を成功させるには、入力の差分を慎重に選択する必要があります。アルゴリズムの内部の分析が行われます。標準的な方法は、暗号化のさまざまな段階を通じて、差分特性と呼ばれる、非常に可能性の高い差分のパスを追跡することです。
差分暗号解読法が一般に知られるようになって以来、それは暗号設計者の基本的な関心事となっている。新しい設計には、アルゴリズムがこの攻撃に耐性があるという証拠が伴うことが期待されており、Advanced Encryption Standardを含む多くのアルゴリズムがこの攻撃に対して安全であることが証明されている。[6]
攻撃の詳細
この攻撃は、主に、特定の入力/出力の差のパターンが特定の入力値に対してのみ発生するという事実に依存しています。通常、この攻撃は本質的には非線形コンポーネントをソリッド コンポーネントであるかのように適用されます (通常、それらは実際にはルックアップ テーブルまたは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)にできるだけ近い値を求めるのが理想的です。これが起こると、差分攻撃では、鍵を総当たり攻撃するのと同じくらい多くの作業が鍵を決定するために必要になります。[7]
AES 非線形関数の最大差分確率は 4/256 です (ただし、ほとんどのエントリは 0 または 2 です)。つまり、理論上はブルート フォースの半分の作業でキーを特定できますが、AES の高分岐により、複数のラウンドにわたって高確率の痕跡が存在することが防止されます。実際、AES 暗号は、はるかに弱い非線形関数を使用しても、差分攻撃と線形攻撃に対して同様に耐性があります。4R を超える 25 という非常に高い分岐 (アクティブな S ボックス数) は、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 ビットの関数を使用する理由の 1 つです。これらの関数は、差分攻撃と線形攻撃に対する耐性が向上しますが、代数攻撃に対しては耐性が低下します。[なぜ? ]つまり、 SAT ソルバー を使用して記述および解決できます。これは、AES (例) が反転後に アフィン マッピングを持つ理由の 1 つです。
特殊タイプ
参照
参考文献
- ^ Biham E、Shamir A (1993)。データ暗号化標準の差分暗号解析。ニューヨーク：Springer Verlag。ISBN 978-0-387-97930-4。
- ^ abc Coppersmith D (1994 年5 月)。「データ暗号化規格 (DES) と攻撃に対するその強度」( PDF)。IBM Journal of Research and Development。38 ( 3): 243–250。doi :10.1147/rd.383.0243。(サブスクリプションが必要です)
- ^ Levy S (2001)。暗号：コード反逆者がいかにして政府を打ち負かすか — デジタル時代のプライバシー保護。ペンギンブックス。pp. 55–56。ISBN 0-14-024432-8。
- ^ Blaze M (1996 年 8 月 15 日). 「Re: リバース エンジニアリングと Clipper チップ」. sci.crypt .
- ^ 「差分暗号解析 - 概要 | ScienceDirect Topics」www.sciencedirect.com 。 2023年4月13日閲覧。
- ^ Nechvatal J、Barker E、Bassham L、Burr W、Dworkin M、Foti J、Roback E (2001 年 5 月～6 月)。「Advanced Encryption Standard (AES) の開発に関するレポート」。米国国立標準技術研究所の研究ジャーナル。106 ( 3): 511–577。doi : 10.6028 / jres.106.023。PMC 4863838。PMID 27500035。3.2.1.3。
- ^ Indesteege, Sebastiaan; Preneel, Bart (2009)。「EnRUPT の実用的な衝突」。Dunkelman, Orr (編)。高速ソフトウェア暗号化。コンピュータサイエンスの講義ノート。第 5665 巻。ベルリン、ハイデルベルク: Springer。pp. 246–259。doi : 10.1007 / 978-3-642-03317-9_15。ISBN 978-3-642-03317-9。
さらに読む
- Biham E、 Shamir A (1991 年 1 月)。 「 DES のような暗号システムの差分暗号解析」。Journal of Cryptology。4 ( 1): 3–72。doi :10.1007/BF00630563。S2CID 33202054。
- Biham E、Shamir A (1992 年 8 月)。「完全な 16 ラウンド DES の差分暗号解析」。国際暗号学年次会議。コンピュータ サイエンスの講義ノート。第 740 巻。ベルリン、ハイデルベルク: Springer。pp. 487–496。doi : 10.1007 /3-540-48071-4_34。ISBN 978-3-540-57340-1. S2CID 6188138。2005年4月5日にオリジナルからアーカイブされました。
- Knudsen LR、 Robshaw M (2011)。「差分暗号解析：そのアイデア」。ブロック暗号コンパニオン。情報セキュリティと暗号化。Springer。pp. 109–126。doi :10.1007 / 978-3-642-17342-4。ISBN 978-3-642-17341-7。
外部リンク
- 差分（および線形）暗号解読のチュートリアル
- 差分暗号解読に関するヘルガー・リップマーのリンク
- Wayback Machineにおける DES に適用された攻撃の説明(2007 年 10 月 19 日アーカイブ)