AESはアメリカの暗号化標準です。パートV.攻撃

個々の変換の詳細を含む詳細なプレゼンテーションの後、（多くの出版物のように、Khabrovskyを除く）代数フィールドではなく、（具体的な）有限の要素を使用して、RIJNDAEL、AES-128、および（AES-128標準の操作を実行する）が実装されます。、暗号に対する攻撃の可能性の検討に進むことができます。今のところ、私たちは1つの攻撃に限定します。私たちの意見では、最も理解しやすく、透過的に構築された（ただし、おそらくすべての読者にではない）Habrです。



私はすでに不利な点に慣れていますが、悪魔が冗談を言っていないこと。起こりうる攻撃と期待される結果の分析は多くの著者によって行われてきましたが、具体的な成功例や単に印象的なデザインだけでは明らかに十分ではありません。ここでは、数学的な観点から、侵入者によって暗号テキストに導入されたエラーを使用した攻撃について検討します。デモンストレーションのための攻撃を選択するとき、著者は、あまりにもねじれていて厄介な数学的なものが使用されているものを含まないようにしましたが、問題の主題自体は非常に深刻であり、「指」の説明に進むことはできません。



この出版物の重要な目標は、AES-128の基礎を形成する数学の応用を示すことであり、残念ながら、多くの著者は、自分たちの発明をチェックして指摘できる人はほとんどいないという事実に導かれて、根拠のない根拠のないものを迂回または誤って解釈しています。



記事の内容は完全に攻撃の元の概念ではなく、主なアクションは作業から取られていますが、それは私の学生によって慎重に作成され、補足され、実験的にテストされました。彼らは高等代数と暗号学の両方で良い習慣を得ました。

1.AES暗号鍵への攻撃

まず、AESへの攻撃を簡単なケースで説明し、次にそのような攻撃をどのように一般化できるかが明らかになります。検討中の攻撃の目的は、暗号のキーK（Nr）を回復することです。部分（ラウンド）キーK（Nr）が決定されると、キーKの取得が容易になります。

1.1攻撃の原則

ShiftRows（Nr-1）操作の後に、状態行列Sの別のバイト（16の1つ）にエラー「ε」を導入することによって変更できると想定されます。つまり、最後から2番目のラウンド、および破損したバイト（要素の＃）のインデックス（セルの＃）です。 ）状態。この最後の仮説は省略できます。攻撃メカニズムをより簡単に説明するために導入されました。状態項目の新しい値は不明であると見なされます。



エラー「ε」は、プロセスの終了ステータスの4バイト以下にまで及びます。出力状態の4つの変更可能な要素すべてについて、エラー「ε」の可能性のあるベクトルの値のセット（セット）がセクション1.4にあります。さらに、これらの4つの要素の可能な値のセット「ε」（定義1）を交差させることが可能になります。このようなセットが交差すると、より小さなセットが取得されるため、完全な分析に必要な暗号テキストの数が減ります。



最後に、エラーごとに、前のラウンドキーの4つの要素についていくつかの文字化けした値を出力します。他の暗号テキストを形成すると、4バイトのラウンドキーK（10）が見つかります。この攻撃は、エラーの場所に関する多くの一般的な仮定があっても成功したままです。 9番目のMixColumns（）変換前のエラーの場所に関する情報の欠如など。歪みがある場合とない場合の暗号テキストマトリックスの違いにより、歪みとその位置が明らかになります（この例では、これらは位置0、7、10、13です）。



また、ラウンド8（8番目のMixColumns（）変換の前）で導入された「ε」エラーが分析に役立つ可能性があることも想定されています。しかし同時に、より完全な分析に必要な暗号テキストの数が増加します。検討中の数値例では、エラー位置の仮説が考慮されていない条件下で、4バイトのラウンドキーK（10）を取得するために約10個の暗号テキストが必要です。

1.2エラーがメッセージに与える影響の数値例

ここでは、名前付き作品の付録に記載されているのと同じ例が使用されています。暗号化プロセスの最後から2番目と最後のラウンドが考慮されます（データのバイト表現の形式は次のとおりです）。



入力= '32 43 F6 A8 88 5A 30 8D 31 31 98 A2 E0 37 07 34 ';

暗号キー= '2B 7E 15 16 28 AE D2 A6 AB F7 15 88 09 CF 4F 3C';

出力= '39 25 84 1D 02 DC 09 FB DC 11 85 97 19 6A 0B 32 ';

エラー "ε" = '1E 00 00 00 00 00 00 00 00 00 00 00 00 0000'。



次の図は、それぞれ16バイトの暗号ブロック長と暗号キー長（つまり、Nb = 4とNk = 4）に従って状態配列に含まれる値を示しています。



エラーの伝播は、太字および16進表記で示されています。以下は、さまざまな状況での州の正方形です。





エラー「ε」= 1Eは、第9ラウンドステータスの0番目のバイトに挿入され、最終状態の4バイトが変更されます。状態の「正方形」の主対角線のコーナーセルの計算例：



-エラー「ε」=



1E87⊕1E=10000111⊕00011110= 1001 1001 = 99

は、第9ラウンドの状態正方形の左上（コーナー）セルに入力されます-右下MixColum9がキーバイトK（9）と合計された後の第9ラウンドの角度状態：



BC⊕6E= 1011 110010 0110 1110 = 1101 0010 = d2。

-結果のエラーの値を計算します。



エラーの有無にかかわらず、2つのメッセージテキストが存在する場合、破損したステータスバイトの値と位置は、一方のテキストをもう一方のテキストから差し引くことによって決定されます。私たちの場合、そのような減算は、2を法としてテキストを合計することによって置き換えることができます。ソーステキストに導入されたエラーによって変更されたバイトに対してのみ、ゼロ以外の結果が得られます。



たとえば、16進形式では、エラー値が見つかります。



表7-エラー値の計算







結果として、差分エラー$$$ε_0’=E7, ε_1’=51, ε_2’=47, ε_3’=99$..。最後のエラーバイトを計算する例を挙げましょう：



62⊕FB=01100010⊕11111011= 1001 1001 = 99。



エラーによって変更されたステータスバイトの位置

$$$ε_0’=E7, ε_1’=51, ε_2’=47, ε_3’=99$。ラウンドキー（最終ラウンド）の要素のインデックスをK [0]、K [7]、K [10]、K [13]として示します。ここで、0、7、10、13は状態行列のセル番号であり、行列Aoは暗号化プロセスの列を混合するための変換行列であり、最初の列の形式は「02」、「01」、「01」、「03」です。

入力したエラーが最終的な最終状態にどのように影響するか

エラーが発生したときに取得した情報の分析

キーK（Nr）に関する情報を含めることができる唯一の操作は、最後のSubBytes（）変換です。したがって、4つの方程式があり、x0、x1、x2、x3、εは未知の変数です。



次の4つの方程式の解を求めます。

$$$s(x_0 +2ε) + s(x_0) =ε_0’,$

$$$s(x_1 +ε) + s(x_1) =ε_1’,$

$$$s(x_2 +ε) + s(x_2) =ε_2’,$

$$$s(x_3 +3ε) + s(x_3) =ε_3’,$

バイト $$$ε_0’, ε_1’, ε_2’, ε_3’$エラーによって変更されたものには、これらのバイトを生成した不明なキーに関する情報が含まれています。



このような方程式はすべて、単一の方程式

s（x +cε）+ s（x）=ε '、（1）

に一般化できます。ここで、定数値=' 01 '、' 02 '、または' 03 'であり、この方程式をさらに解いて、分析します。



定義1。記号B（Cε '）で示され、式で定義：れるεエラーの式（1）の解の集合

B（Cε'）= S（Cε「）= {εєGF [2 ⁸ ]：∃XєGF [2 ⁸ ] s（x +cε）+ s（x）=ε '}、| B（cε'）| = 127。



これは、特定のエラーε 'に対応する個々のエラー領域です。他のε 'の場合、エラー領域は異なります。



定義2。フィールドGF（2）での線形変換ℓを考えてみましょう。

ℓ：GF [2 ⁸ ]→GF [2 ⁸ ]。

X→X ² + X。



ℓの画像は、Im（ℓ）GF（2）-ベクトル空間のマッピングです。GF [2 ⁸ ]の要素のセット

（x ² + x）は、Å1= Im（ℓ）とその次元dimGF（2）（E1）= 7を表します。θє1の場合、2つの異なる解x1、x2єGF[ 2 ⁸ ]式X ² + X =θ、およびソリューションが満たす関係X2 = X1 + 1及びX 2∙X1 =θ（MODDφX、（2 ⁸ -1））VIETAの定理による。 変数θは二次方程式の自由項です。 考えられる線形変換を例を挙げて説明しましょう。例GFフィールドは[2設定されている⁸











]、変換x→x ² + xはその要素に対して実行されます。



表8 -フィールドGF [2の最初の断片⁸ ]および要素の変換の結果。





表8は、変換によって、10進数のリスト内の隣接するペアが同じフィールド要素にどのように変更されるかを示しています。このことから、変換の結果（イメージ）はプレイメージの2分の1になります（フィールドは、いわば2倍に圧縮されます）。セットの次元の縮小のこの原則は、提案された攻撃の基礎を形成します。





提案2。次のステートメントは、λ1、λ2єGF[2 ⁸ ]-{0}に当てはまります。

2.一般化と実装

まず、特別なソフトウェアアプリケーションの助けを借りて、エラーのある20個の暗号テキストが生成されます。これを行うには、ソーステキスト、キー、エラーをモデル（プログラム）に入力し、エラーが配置される位置番号を設定します。 「開始」ボタンを押すと、プログラムはアルゴリズムを実装し、エラーのあるテキスト、エラーのないテキスト、およびそれらの違いについて、最後の2ラウンドの暗号化の結果を展開形式で表示します。その後、暗号テキストはエラーなしでエラー付きで保存されます。エラー値は周期的に変化し、「開始」ボタンを押すと、エラーのある次の暗号テキストが取得されます。列の1つの値で、エラーのある5つの暗号テキストが形成されました。



攻撃を実装するには、プログラムを使用してエラーのない暗号テキストとエラーのある暗号テキストでファイルを開く必要があります（ファイル内のデータは16進形式で表示されます）。暗号テキストとそれらの違いは、バイトの正方形配列（状態）として表示されます。 「キーの検索」ボタンを押すと、キーの可能なバイトを検索する手順が開始されます。プロセスの現在の状態がテキストボックスに表示されます。その後、別のエラーのある暗号テキストが開かれ、手順が繰り返されます。ラウンド10キーバイトを受信すると、対応するスクエアバイト配列にも表示されます。前の段階で生成された20個の暗号テキストすべてをエラーで実行すると、ラウンド10キーのすべてのバイトの値を取得する可能性が高くなります（そうでない場合は、エラーのある暗号テキストも必要です）。その後、与えられたアルゴリズム「最後のサブキーを使用して暗号化キーを回復する」に従って暗号化キーを復元しますここ。





図11-エラーのある暗号テキストを作成するためのソフトウェア製品エラーのある暗号テキストを



列挙する手順を高速化するために、[キーの検索]ボタンの前にチェックマークを付けることができます。





図12 -攻撃のソフトウェア実装



ソフトウェア製品のアン例：



ソースコード3243f6a8885a308d313198a2e0370734

キー2b7e151628aed2a6abf7158809cf4f3cの

エラー1 1e000000000000000000000000000000

エラー1と暗号文

の可能性バイトde25841d02bdc09









図13-プログラムの操作例



ラウンド10キーd014f9a8c9ee2589e13f0cc8b6630ca6キーは完全に回復されました回復

されたキー2b7e151628aed2a6abf7158809cf4f3c予想どおり、暗号化セッションで指定されたキーと一致します。

2.1。エラー位置情報がない場合の状況

この時点で、MixColumns操作の最後の2回の実行の間のステータスバイトにエラーが含まれていると想定されます。これは、エラーを1〜16のバイトで囲むことができるという事実を除いて、同じケースです。エラーはMixColumns操作によって乗算され、4バイトのステータスに広がります。



差分状態マトリックスの最初の行に強制エラーが生成されます。ここでは、強制エラー列を調べることにより、入力されたエラーがどの列に属しているかを判別できます。これは、前の説明で説明した方法を使用して、入力されたエラーの4つの可能な行位置を調べることによって行われます。

2.2。ハードウェアデバイス

AESハードウェアデバイスに物理的に干渉する能力があると仮定しましょう。まず、AESデバイスを使用して10を超えるランダムプレーンテキストの暗号を計算しましょう。次に、ラインを切り取り、完了の2ラウンド前に配置されたラウンド中に2バイトの間で一時的にグラウンド（またはVcc）に接続することにより、サンプルプロジェクトを変更します。結局のところ、ラウンドNk -2にバイトがあり、常に「00」（または「FF」）に置き換えられます。



動作中のデバイスで同じメッセージをもう一度計算します。ランダムなプレーンテキストの場合、欠陥のあるバイトはランダムエラーのようなものです。この単一のエラーは、Nk -1ラウンドで4つのエラー、Nkラウンドで16のエラーに変換されます。この場合、偏差マトリックス（微分）を取得できます。これを使用すると、エラーを分析して、最後のラウンドキーを見つけることができます。



文献：



[1] FIPS PUB 197：Advanced Encryption Standard、csrc.nist.gov

/ publications / fips / fips197 / fips-197.pdf [2] Boneh、DeMillo、およびLipton、暗号化プロトコルの障害チェックの重要性について、コンピュータサイエンスの講義ノート、暗号学の進歩、EU-ROCRYPT'97の議事録、pp。 37-51、1997。

[3] E. Biham＆A。Shamir、Secret Key Cryptosystemsの差分障害分析、CS 0910、Proceedings ofCrypto'97。

[4]ロスJ.アンダーソン、マーカスG.クーン：改ざん防止-注意事項、電子商取引手続きに関する第2回USENIXワークショップ、カリフォルニア州オークランド、1996年11月18〜21日、1〜11ページ、ISBN 1〜880446- 83-9。