高度暗号化標準

1. 鍵拡張–ラウンド鍵は、 AES鍵スケジュールを使用して暗号鍵から生成されます。AESでは、各ラウンドごとに個別の128ビットのラウンド鍵ブロックが必要であり、さらに1つ追加する必要があります。 
2. 初回ラウンドのキー追加:
   1. AddRoundKey –状態の各バイトは、ビットごとの排他的論理和を使用してラウンドキーのバイトと結合されます。 
3. 9ラウンド、11ラウンド、または13ラウンド：
   1. サブバイト–ルックアップテーブルに従って各バイトが別のバイトに置き換えられる非線形置換ステップ。 
   2. ShiftRows –状態の最後の 3 行を一定数のステップだけ巡回的にシフトする転置ステップ。 
   3. MixColumns –状態の列に対して動作する線形混合操作であり、各列の4バイトを結合します。 
   4. AddRoundKey
4. 最終ラウンド（合計10ラウンド、12ラウンド、または14ラウンド）：
   1. サブバイト
   2. ShiftRows
   3. AddRoundKey

SubBytesステップでは、状態配列の各バイトa _i,jは、8 ビット置換ボックスを使用してSubByte S ( a _i,j )に置き換えられます。ラウンド 0 の前は、状態配列は単に平文/入力です。この操作により、暗号に非線形性が生じます。使用される S ボックスは、優れた非線形性を持つことが知られているGF (2 ⁸ )上の乗法逆から導出されます。単純な代数的性質に基づく攻撃を回避するために、S ボックスは逆関数と可逆アフィン変換を組み合わせることによって構築されます。S ボックスは、固定点 (したがって置換)、つまりS ( a _i,j ) ≠ a _i,jおよび反対の固定点、つまりS ( a _i,j ) ⊕ a _i,j ≠ FF ₁₆を回避するように選択されます。復号化を実行する際には、InvSubBytesステップ（ SubBytesの逆）が使用されます。これは、まずアフィン変換の逆変換を行い、次に乗法逆変換を求める必要があります。

ShiftRowsステップは状態の行に対して動作し、各行のバイトを一定のオフセットで巡回的にシフトします。AES の場合、最初の行は変更されません。2 番目の行の各バイトは 1 つ左にシフトされます。同様に、3 番目の行と 4 番目の行はそれぞれ 2 つと 3 つのオフセットでシフトされます。^{[注 5 ]}このようにして、 ShiftRowsステップの出力状態の各列は、入力状態の各列のバイトで構成されます。このステップの重要性は、列が個別に暗号化されることを回避することです。その場合、AES は 4 つの独立したブロック暗号に退化してしまいます。

MixColumnsステップでは、状態の各列の4バイトが可逆線形変換を用いて結合されます。MixColumns関数は4バイトを入力として受け取り、4バイトを出力します。入力バイトは4バイトすべての出力バイトに影響を与えます。MixColumnsはShiftRowsと組み合わせることで、暗号における拡散を実現します。

この操作中、各列は固定行列を使用して変換されます（行列を列に左から乗算すると、状態における列の新しい値が得られます）。 $${\displaystyle {\begin{bmatrix}b_{0,j}\\b_{1,j}\\b_{2,j}\\b_{3,j}\end{bmatrix}}={\begin{bmatrix}2&3&1&1\\1&2&3&1\\1&1&2&3\\3&1&1&2\end{bmatrix}}{\begin{bmatrix}a_{0,j}\\a_{1,j}\\a_{2,j}\\a_{3,j}\end{bmatrix}}\qquad 0\leq j\leq 3}$$

行列の乗算は、要素の乗算と加算で構成されます。要素は、次数x ⁷の多項式の係数として扱われるバイトです。加算は単純な XOR です。乗算は、既約多項式x ⁸ + x ⁴ + x ³ + x + 1を法とします。ビットごとに処理する場合、シフト後、シフトされた値が FF ₁₆より大きい場合は、 1B _{16との条件付き}XOR を実行する必要があります (オーバーフローは、生成多項式の減算によって修正する必要があります)。これらは、GF(2 ⁸ )における通常の乗算​​の特殊なケースです。

より一般的な意味では、各列はGF(2 ⁸ )上の多項式として扱われ、その後、法を乗算されます。${\displaystyle {01}_{16}\cdot z^{4}+{01}_{16}}$固定された多項式${\displaystyle c(z)={03}_{16}\cdot z^{3}+{01}_{16}\cdot z^{2}+{01}_{16}\cdot z+{02}_{16}}$係数は、 GF(2 ⁸ )[ x ]からのビット多項式のバイナリ表現の16進数相当で表示されます。MixColumnsステップは、有限体GF(2 ⁸ )の特定のMDS 行列による乗算と見なすこともできます。このプロセスについては、記事Rijndael MixColumnsでさらに詳しく説明されています。

AddRoundKeyステップでは、サブキーが状態と結合されます。各ラウンドにおいて、Rijndaelのキースケジュールを使用してメインキーからサブキーが生成されます。各サブキーのサイズは状態と同じです。サブキーは、状態とサブキーの対応するバイトをビットごとのXOR演算で結合することにより追加されます。

32 ビット以上のワードを持つシステムでは、SubBytesおよびShiftRowsステップをMixColumnsステップと組み合わせ、それらをテーブル参照のシーケンスに変換することで、この暗号の実行を高速化できます。これには、4 つの 256 エントリの 32 ビット テーブル (合計で 4096 バイト) が必要です。その後、16 回のテーブル参照操作と 12 回の 32 ビット排他的論理和操作でラウンドを実行でき、続いてAddRoundKeyステップで 4 回の 32 ビット排他的論理和操作を実行します。^{[ 12 ]} あるいは、単一の 256 エントリの 32 ビット テーブル (1024 バイト) とそれに続く円形回転操作でテーブル参照操作を実行することもできます。

バイト指向のアプローチを使用すると、SubBytes、ShiftRows、およびMixColumnsステップを単一のラウンド操作に組み合わせることができます。^{[ 13 ]}

暗号学者にとって、暗号学的「突破」とは、総当たり攻撃（つまり、考えられるすべての鍵に対して順番に1回ずつ復号を試行すること）よりも速いものすべてを指します。したがって、突破には、現在の技術では実現不可能な結果が含まれる可能性があります。理論的な突破は、実用的ではないものの、脆弱性のパターンに関する洞察を提供する場合があります。広く実装されているブロック暗号アルゴリズムに対する、公に知られている最大の総当たり攻撃の成功例は、2006年にdistributed.netが行った64ビットRC5鍵に対する攻撃です。 ^{[ 16 ]} 

鍵長が1ビット増えるごとに鍵空間は2倍になり、鍵のすべての可能な値が等確率であると仮定すると、これは鍵長が1ビット増えるごとに総当たり攻撃による鍵探索の平均時間が2倍になることを意味します。つまり、総当たり攻撃の労力は鍵長に対して指数関数的に増加するということです。鍵長自体は攻撃に対する安全性を保証するものではありません。なぜなら、非常に長い鍵を持つ暗号でも脆弱性が発見されているからです。

AES は比較的単純な代数的フレームワークを持っています。^{[ 17 ]} 2002 年に、ニコラ・クルトワとヨゼフ・ピエプジクによって「 XSL 攻撃」と呼ばれる理論的な攻撃が発表され、非線形コンポーネントの複雑さが低いことなどが原因で AES アルゴリズムに弱点があると主張しました。^{[ 18 ]}それ以降、他の論文では、最初に提示された攻撃は実行不可能であることが示されています。ブロック暗号に対する XSL 攻撃を参照してください。

AES の選定プロセス中、競合アルゴリズムの開発者は Rijndael のアルゴリズムについて「 セキュリティ上重要なアプリケーションでの使用について懸念している」と述べている。^{[ 19 ]}しかし、2000 年 10 月、AES 選定プロセスの終了時に、競合アルゴリズムTwofishの開発者であるBruce Schneier は、Rijndael に対する学術的な攻撃がいつか開発されるだろうと考えているものの、「Rijndael の通信を読み取ることができる攻撃が発見されるとは誰も思っていない」と述べている。^{[ 20 ]}

2006年までに最もよく知られた攻撃は、128ビット鍵の場合は7ラウンド、192ビット鍵の場合は8ラウンド、256ビット鍵の場合は9ラウンドに対するものでした。^{[ 21 ]}

2009 年 5 月まで、完全な AES に対する公開された攻撃で成功したものは、特定の実装に対するサイドチャネル攻撃のみでした。2009 年に、 AES の鍵スケジュールの単純さを悪用する新しい関連鍵攻撃が発見され、その複雑さは 2 ^{119でした。2009 年 12 月に、その複雑さは 2 99.5}に改善されました。^{[ 2 ]}これは、2009 年初頭にAlex Biryukov、Dmitry Khovratovich、および Ivica Nikolićによって発見された攻撃の続編であり、2 ^{35 個の}鍵のうち 1 つに対して2 ^{96の複雑さでした。 [ 22 ]}しかし、適切に設計された暗号プロトコルでは、関連鍵攻撃は問題になりません。適切に設計されたプロトコル (つまり、実装ソフトウェア) は、関連鍵を許可しないように注意し、本質的には、関連性に基づいて鍵を選択する攻撃者の手段を制限します。

別の攻撃は、2009 年 7 月 30 日に Bruce Schneier ^{[ 3 ]}によってブログに投稿され 、 2009 年 8 月 3 日にプレプリント^{[ 23 ]}として公開されました。この新しい攻撃は、Alex Biryukov、 Orr Dunkelman、Nathan Keller、Dmitry Khovratovich、およびAdi Shamirによって行われ、2 つの関連キーのみを使用する AES-256 を対象としており、9 ラウンドバージョンの完全な 256 ビットキーを復元するのに 2 ³⁹時間、より強力なタイプの関連サブキー攻撃を使用した 10 ラウンドバージョンでは2 ^{45時間、11 ラウンドバージョンでは 2 70}時間かかります。256 ビット AES は 14 ラウンドを使用するため、これらの攻撃は完全な AES に対しては効果的ではありません。

より強力な関連鍵を用いたこれらの攻撃の実用性は批判されており、^{[ 24 ]}例えば、2010年にVincent Rijmenが執筆したAES-128に対する中間鍵選択関係攻撃に関する論文^{[ 25 ]で批判されている。}

2009 年 11 月、 AES-128 の 8 ラウンド版に対する最初の既知鍵識別攻撃がプレプリントとして公開されました。 ^{[ 26 ]} この既知鍵識別攻撃は、AES のような順列に対するリバウンド攻撃、または中間から開始する攻撃の改良版で、連続する 2 ラウンドの順列をいわゆる Super-S-box の適用とみなします。これは、AES-128 の 8 ラウンド版で動作し、時間計算量は 2 ⁴⁸、メモリ計算量は 2 ³²です。128 ビット AES は 10 ラウンドを使用するため、この攻撃は完全な AES-128 に対しては有効ではありません。

完全な AES に対する最初の鍵回復攻撃は、 Andrey Bogdanov、Dmitry Khovratovich、および Christian Rechberger によって行われ、2011 年に発表されました。^{[ 27 ]}この攻撃はバイクリック攻撃であり、総当たり攻撃よりも約 4 倍高速です。AES -128 の鍵を回復するには^{2126.2回の操作が必要です。AES-192 と AES-256 の場合は、それぞれ2190.2}回と^2254.6回の操作が必要です。この結果は、Biaoshuai Tao と Hongjun Wu によって 2015 年の論文でさらに改善され、AES-128 では^{2126.0回、AES-192 では2189.9}回、 AES-256 では^2254.3回となり、現在 AES に対する鍵回復攻撃で最良の結果となっています。^{[ 28 ]}

これは非常に小さな利点です。126 ビットの鍵 (128 ビットではなく) では、現在のハードウェアや将来予測されるハードウェアで総当たり攻撃を行うのに依然として数十億年かかります。また、著者らは、128 ビットの鍵を使用した AES に対する彼らの手法による最良の攻撃には 2 ⁸⁸ビットのデータを保存する必要があると計算しています。これは約 38 兆テラバイトのデータに相当し、2016 年に地球上のすべてのコンピュータに保存されていたすべてのデータよりも多い量です。^{[ 29 ]} 2015 年の論文では、空間計算量が 2 ⁵⁶ビットに改善されました。^{[ 28 ]}これは 9007 テラバイトです (時間計算量は依然として約 2 ¹²⁶のままです)。

スノーデン文書によると、NSAはタウ統計に基づく暗号攻撃がAESの解読に役立つかどうかを研究している。^{[ 30 ]}

現時点では、鍵を知らない者が、正し​​く実装されたAESで暗号化されたデータを読み取ることを可能にするような、既知の実用的な攻撃方法は存在しない。

サイドチャネル攻撃は、暗号をブラックボックスとして攻撃するものではないため、古典的な文脈で定義される暗号のセキュリティとは関係ありませんが、実際には重要です。サイドチャネル攻撃は、意図せずデータを漏洩させてしまうハードウェアまたはソフトウェアシステム上の暗号の実装を攻撃します。AESのさまざまな実装に対して、このような既知の攻撃がいくつか存在します。

2005 年 4 月、D.  J. Bernstein は、 OpenSSLの AES 暗号化を使用するカスタム サーバーを破るために使用したキャッシュ タイミング攻撃を発表しました。 ^{[ 31 ]}この攻撃には 2 億を超える選択平文が必要でした。^{[ 32 ]}カスタム サーバーは、可能な限り多くのタイミング情報を提供するように設計されていました (サーバーは暗号化操作にかかったマシン サイクル数を返します)。しかし、Bernstein が指摘したように、「サーバーのタイム スタンプの精度を下げたり、サーバーの応答からタイム スタンプを削除したりしても、攻撃は阻止されません。クライアントはローカル クロックに基づく往復タイミングを使用し、より多くのサンプルで平均化することでノイズの増加を補償します。」^{[ 31 ]}

2005 年 10 月、Dag Arne Osvik、Adi Shamir、およびEran Tromer はdm-crypt、OpenSSL および Linux のパーティション暗号化機能に実装されている AES に対するいくつかのキャッシュタイミング攻撃を示す論文を発表しました。 ^{[ 33 ]}ある攻撃では、暗号化をトリガーする 800 回の操作だけで、合計 65 ミリ秒で AES キー全体を取得することができました。この攻撃では、攻撃者は AES を実行しているシステムまたはプラットフォームと同じシステムまたはプラットフォームでプログラムを実行できる必要があります。

2009年12月、差分障害解析を用いて鍵の復元を可能にする、一部のハードウェア実装に対する攻撃が発表された。この攻撃は^2³²の複雑さを持つ鍵の復元を可能にする。^{[ 34 ]}

2010 年 11 月、Endre Bangerter、David Gullasch、Stephan Krenn は、暗号文も平文も必要とせずに AES-128 から秘密鍵を「ほぼリアルタイム」で復元する実用的なアプローチを説明した論文を発表しました。このアプローチは、OpenSSL などの圧縮テーブルを使用する AES-128 実装でも機能します。^{[ 35 ]}以前の攻撃のいくつかと同様に、この攻撃では、AES 暗号化を実行するシステム上で非特権コードを実行できる能力が必要ですが、これは、root アカウントを乗っ取るよりもはるかに簡単にマルウェア感染によって達成できます。^{[ 36 ]}

2016年3月、C. Ashokkumar、Ravi Prakash Giri、Bernard Menezesは、わずか6～7ブロックの平文/暗号文で完全な128ビットAES鍵を復元できるAES実装に対するサイドチャネル攻撃を発表しました。これは、100回から100万回の暗号化を必要とする従来の研究に比べて大幅な改善です。^{[ 37 ]}提案された攻撃には標準的なユーザー権限が必要で、鍵取得アルゴリズムは1分以内に実行されます。

多くの最新のCPUには、タイミング関連のサイドチャネル攻撃から保護するAES用のハードウェア命令が組み込まれています。 ^{[ 38 ] [ 39 ]}

AES-256 は、128ビットのセキュリティで従来の非量子攻撃に対する AES-128 の耐性と同様の量子耐性を持つため、量子耐性があるとみなされています。AES-192 と AES-128 は、鍵サイズが小さいため、量子耐性があるとはみなされていません。AES-192 は量子攻撃に対して 96 ビットの強度を持ち、AES-128 は量子攻撃に対して 64 ビットの強度を持つため、どちらも安全ではありません。^{[ 40 ] [ 41 ]}