ブロック暗号

ほとんどのブロック暗号アルゴリズムは反復ブロック暗号に分類され、これは固定サイズの平文ブロックを、ラウンド関数と呼ばれる可逆変換を繰り返し適用することによって、同じサイズの暗号文ブロックに変換することを意味し、各反復はラウンドと呼ばれます。^{[ 12 ]}

通常、ラウンド関数R は、元のキーから導出された異なるラウンドキーK _{i を2 番目の入力として受け取ります。} ^{[ 13 ]}

${\displaystyle M_{i}=R_{K_{i}}(M_{i-1})}$

どこ${\displaystyle M_{0}}$は平文であり、${\displaystyle M_{r}}$暗号文。rはラウンド数。

これに加えて、キーホワイトニングがよく用いられます。データの最初と最後に、キーマテリアル（多くの場合XOR演算）を用いてデータが変更されます。

${\displaystyle M_{0}=M\oplus K_{0}}$

${\displaystyle M_{i}=R_{K_{i}}(M_{i-1})\;;\;i=1\dots r}$

${\displaystyle C=M_{r}\oplus K_{r+1}}$

標準的な反復ブロック暗号設計方式のいずれかを用いる場合、ラウンド数を多くすることで、暗号学的に安全なブロック暗号を比較的容易に構築できます。しかし、この方法では暗号の効率が低下します。したがって、効率性はプロフェッショナルな暗号にとって最も重要な設計基準となります。さらに、優れたブロック暗号は、分岐予測や入力依存型のメモリアクセスなど、キャッシュ状態や実行時間を通じて秘密データが漏洩する可能性のあるサイドチャネル攻撃を回避するように設計されています。加えて、ハードウェアやソフトウェアの実装規模が小さいため、暗号は簡潔である必要があります。

反復ブロック暗号の重要なタイプの 1 つは置換-順列ネットワーク(SPN)として知られており、平文のブロックと鍵を入力として受け取り、置換段階と順列段階からなるいくつかの交互のラウンドを適用して、各ブロックの暗号文を出力します。^{[ 14 ]}非線形置換段階では、鍵のビットを平文のビットと混合し、シャノンの混同を生成します。次に、線形順列段階で冗長性を消散させ、拡散を生成します。^{[ 15 ] [ 16 ]}

置換ボックス（Sボックス）は、入力ビットの小さなブロックを別の出力ビットのブロックに置き換えます。この置換は、可逆性（つまり復号）を保証するために、 1対1でなければなりません。安全なSボックスは、1つの入力ビットを変更すると、平均して出力ビットの約半分が変化するという特性を持ち、いわゆるアバランシェ効果を示します。つまり、各出力ビットはすべての入力ビットに依存するという特性を持ちます。^{[ 17 ]}

順列ボックス（Pボックス）は、すべてのビットの順列です。1ラウンドのすべてのSボックスの出力を受け取り、ビットを順列にして、次のラウンドのSボックスに入力します。優れたPボックスは、任意のSボックスの出力ビットが可能な限り多くのSボックス入力に分配されるという特性を持っています。^{[ 18 ]}

各ラウンドでは、ラウンドキー（SボックスやPボックスなどを使った簡単な操作でキーから得られる）が、通常はXORなどのグループ演算を使って結合されます。

復号は、プロセスを逆にするだけで行われます（SボックスとPボックスの逆を使用し、ラウンドキーを逆順に適用します）。^{[ 19 ]}

フェイステル暗号では、暗号化する平文のブロックを2つの等しいサイズの半分に分割します。サブキーを使用して一方の半分にラウンド関数を適用し、その出力をもう一方の半分とXOR演算します。その後、2つの半分を交換します。^{[ 20 ]}

させて${\displaystyle {\rm {F}}}$を丸め関数とし、 ${\displaystyle K_{0},K_{1},\ldots ,K_{n}}$ラウンドのサブキーとなる${\displaystyle 0,1,\ldots ,n}$それぞれ。

すると、基本的な操作は次のようになります。^{[ 20 ]}

プレーンテキストブロックを2つの等しい部分に分割します。${\displaystyle L_{0}}$、${\displaystyle R_{0}}$）

各ラウンドごとに${\displaystyle i=0,1,\dots ,n}$計算する

${\displaystyle L_{i+1}=R_{i}\,}$

${\displaystyle R_{i+1}=L_{i}\oplus {\rm {F}}(R_{i},K_{i})}$。

すると暗号文は${\displaystyle (R_{n+1},L_{n+1})}$。

暗号文の復号${\displaystyle (R_{n+1},L_{n+1})}$計算によって達成される${\displaystyle i=n,n-1,\ldots ,0}$

${\displaystyle R_{i}=L_{i+1}\,}$

${\displaystyle L_{i}=R_{i+1}\oplus {\rm {F}}(L_{i+1},K_{i})}$。

それから${\displaystyle (L_{0},R_{0})}$これも平文です。

置換・順列ネットワークと比較したフェイステルモデルの利点の1つは、ラウンド関数が${\displaystyle {\rm {F}}}$可逆である必要はない。^{[ 21 ]}

ライ・マッセイ方式は、フェイステル構造と同様のセキュリティ特性を提供する。また、ラウンド関数が${\displaystyle \mathrm {F} }$可逆である必要はありません。もう一つの共通点は、入力ブロックを2つの等しい部分に分割することです。ただし、丸め関数は2つの部分の差に適用され、その結果が両方の半分のブロックに加算されます。

させて${\displaystyle \mathrm {F} }$丸め関数とし、${\displaystyle \mathrm {H} }$半円形関数と${\displaystyle K_{0},K_{1},\ldots ,K_{n}}$ラウンドのサブキーとなる${\displaystyle 0,1,\ldots ,n}$それぞれ。

基本的な操作は以下のとおりです。

プレーンテキストブロックを2つの等しい部分に分割します。${\displaystyle L_{0}}$、${\displaystyle R_{0}}$）

各ラウンドごとに${\displaystyle i=0,1,\dots ,n}$計算する

${\displaystyle (L_{i+1}',R_{i+1}')=\mathrm {H} (L_{i}'+T_{i},R_{i}'+T_{i}),}$

どこ${\displaystyle T_{i}=\mathrm {F} (L_{i}'-R_{i}',K_{i})}$そして${\displaystyle (L_{0}',R_{0}')=\mathrm {H} (L_{0},R_{0})}$

すると暗号文は${\displaystyle (L_{n+1},R_{n+1})=(L_{n+1}',R_{n+1}')}$。

暗号文の復号${\displaystyle (L_{n+1},R_{n+1})}$計算によって達成される${\displaystyle i=n,n-1,\ldots ,0}$

${\displaystyle (L_{i}',R_{i}')=\mathrm {H} ^{-1}(L_{i+1}'-T_{i},R_{i+1}'-T_{i})}$

どこ${\displaystyle T_{i}=\mathrm {F} (L_{i+1}'-R_{i+1}',K_{i})}$そして${\displaystyle (L_{n+1}',R_{n+1}')=\mathrm {H} ^{-1}(L_{n+1},R_{n+1})}$

それから${\displaystyle (L_{0},R_{0})=(L_{0}',R_{0}')}$これも平文です。

この特性により、暗号のセキュリティは2乗に比例して低下するため、ブロックサイズを選択する際には考慮する必要があります。ただし、ブロックサイズが大きいとアルゴリズムの動作効率が低下するというトレードオフがあります。^{[ 34 ]} DESなどの初期のブロック暗号は通常64ビットのブロックサイズを選択していましたが、AESなどの新しい設計では128ビット以上のブロックサイズをサポートしており、一部の暗号ではさまざまなブロックサイズをサポートしています。^{[ 35 ]}

線形暗号解読は、暗号の動作に対するアフィン近似を見つけることに基づく暗号解読の一種です。線形暗号解読は、ブロック暗号に対する最も広く使用されている2つの攻撃の1つであり、もう1つは差分暗号解読です。 ^{[ 36 ]}

この発見は、FEAL暗号にこの技術を初めて適用した松井満氏によるものとされている（松井・山岸、1992年）。^{[ 37 ]}

積分暗号解読は、置換・順列ネットワークに基づくブロック暗号に特に有効な暗号解読攻撃です。固定のXOR差を持つ選択平文のペアを使用する差分暗号解読とは異なり、積分暗号解読では、一部が固定され、他の部分がすべての可能性にわたって変化する選択平文のセット、あるいは多重セットを使用します。例えば、攻撃では、8ビットを除くすべてのビットが同じで、その8ビットだけが異なる256個の選択平文を使用する場合があります。このようなセットのXOR和は必然的に0となり、対応する暗号文セットのXOR和から暗号の動作に関する情報が得られます。テキストのペア間の差と、より大きなテキストセットの和とのこの対比が、微積分学の用語を借りて「積分暗号解読」という名前を思い起こさせました。

線形暗号解読と差分暗号解読に加えて、切り捨て差分暗号解読、部分差分暗号解読、積分暗号解読（平方攻撃と積分攻撃を含む）、スライド攻撃、ブーメラン攻撃、XSL攻撃、不可能差分暗号解読、代数攻撃など、攻撃の種類が増え続けている。新しいブロック暗号設計が信頼性を得るには、既知の攻撃に対する安全性の証拠を示す必要がある。^{[ 38 ]}

非公式には、ブロック暗号は、攻撃者が（ランダムな鍵を備えた）ブロック暗号とランダムな順列を区別できない場合に、標準モデルにおいて安全であると言えます。

もう少し正確に言うと、E をnビットのブロック暗号とします。次のゲームを想像してみましょう。

1. ゲームの進行役がコインを投げる。
   • コインが表になった場合、彼はランダムなキーKを選択し、関数f = E _Kを定義します。
   • コインが裏になった場合、彼はnビット文字列の集合からランダムな順列πを選択し、関数f = πを定義します。
2. 攻撃者はnビットの文字列Xを選択し、ゲームを実行している人がf ( X )の値を伝えます。
3. ステップ2は合計q回繰り返されます。（これらのq回のやり取りはそれぞれクエリです。）
4. 攻撃者はコインがどこに落ちたかを推測する。推測が正しければ攻撃者の勝ちとなる。

アルゴリズムとしてモデル化できる攻撃者は、敵対者と呼ばれます。敵対者が照会できた関数fは、オラクルと呼ばれます。

攻撃者は、ランダムに推測するだけで（あるいは、例えば常に「表」を推測するだけでも）、50% の勝率を簡単に確保できることに注意してください。したがって、P _E ( A ) を攻撃者A がEに対してこのゲームに勝つ確率とし、Aの優位性を2( P _E ( A ) − 1/2 ) と定義します。Aがランダムに推測する場合、その優位性は 0 になります。一方、A が常に勝つ場合、その優位性は 1 になります。ブロック暗号Eは、 qと攻撃者の実行時間に関する特定の制約が与えられた場合、どの攻撃者も 0 より著しく大きな優位性を持たない場合、擬似ランダム置換(PRP) です。上記のステップ 2 で、攻撃者がf ( X ) の代わりにf ⁻¹ ( X )を学習するオプションがある場合(ただし、優位性は小さい場合)、Eは強力なPRP (SPRP)です。敵対者がゲーム開始前にXのすべてのq値を選択する場合（つまり、ゲームを進めるにつれて各Xを選択する際に、以前のクエリから得られた情報を一切使用しない場合）、その敵対者は非適応的である。  

これらの定義は、さまざまな動作モードを分析する上で有用であることが証明されています。たとえば、ブロック暗号ベースの暗号化アルゴリズムのセキュリティを測定するために同様のゲームを定義し、（還元論法を用いて）攻撃者がこの新しいゲームに勝つ確率が、あるAに対してP _E ( A ) よりそれほど大きくないことを示そうとすることができます。（還元論法は通常、qとAの実行時間に制限を与えます。）言い換えれば、関連するすべてのAに対してP _E ( A ) が小さい場合、攻撃者が新しいゲームに勝つ確率は大きくありません。これは、上位レベルのアルゴリズムがブロック暗号のセキュリティを継承するという考え方を形式化したものです。

ルシファーは一般的に、ホルスト・ファイステルの研究に基づいて1970年代にIBMで開発された最初の民間用ブロック暗号と考えられています。アルゴリズムの改訂版は、米国政府の連邦情報処理標準であるFIPS PUB 46データ暗号化標準（DES）として採用されました。^{[ 42 ]}これは、米国国立標準局（NBS）が一般からの提案募集とNBS（およびおそらくNSA）による内部変更を経て選定したものです。DESは1976年に一般公開され、広く使用されています。

DESは、とりわけ、NSAが知っていたもののIBMが再発見し、1980年代後半にEli BihamとAdi Shamirによって再び発見され発表されるまで一般には知られていなかった、ある暗号解読攻撃に対抗するために設計された。この手法は差分暗号解読と呼ばれ、ブロック暗号に対する数少ない一般的な攻撃手法の一つである。線形暗号解読もその一つだが、松井充氏による発表以前はNSAでさえ知らなかった可能性がある。DESは、暗号学と暗号解読に関する多くの研究や論文をオープンコミュニティに促し、多くの新しい暗号設計に影響を与えた。

DES のブロックサイズは 64 ビット、鍵サイズは 56 ビットです。64 ビットのブロックは、DES 以降、ブロック暗号設計で一般的になりました。鍵長は、政府の規制など、いくつかの要因に依存していました。1970年代には、DES に使用されている 56 ビットの鍵長は短すぎると多くの観察者が指摘しました。時が経つにつれ、特に1998 年に電子フロンティア財団がDES を解読するために設計された専用マシンを実証した後、その不十分さが明らかになりました。DESの拡張であるTriple DES は、2 つの独立した鍵 (112 ビットの鍵と 80 ビットのセキュリティ) または 3 つの独立した鍵 (168 ビットの鍵と 112 ビットのセキュリティ) を使用して各ブロックを三重に暗号化します。これは、DES の代替として広く採用されました。 2011年現在、3キーバージョンは依然として安全であると考えられているが、米国国立標準技術研究所（NIST）の基準では、80ビットのセキュリティレベルのため、新しいアプリケーションでの2キーバージョンの使用はもはや許可されていない。^{[ 43 ]}

国際データ暗号化アルゴリズム（IDEA ）は、チューリッヒ工科大学のジェームズ・マッセイとシュエジア・ライによって設計されたブロック暗号であり、DESの代替として1991年に初めて発表された。

IDEAは128ビットの鍵を使用して64ビットのブロック上で動作し、8つの同一の変換（ラウンド）と出力変換（ハーフラウンド）から構成されます。暗号化と復号化のプロセスは似ています。IDEAのセキュリティの大部分は、モジュラー加算と乗算、ビットごとの排他的論理和（XOR）など、代数的に何らかの意味で「互換性がない」異なるグループの演算をインターリーブすることによって実現されています。

設計者たちはIDEAを分析し、差分暗号解読に対する耐性を測定した結果、特定の条件下では耐性があると結論付けた。線形または代数的な脆弱性は報告されていない。2012年現在すべてのキーに適用できる最良の攻撃は、総当たり攻撃よりも約4倍速く、狭いバイクリック攻撃を使用して完全な8.5ラウンドのIDEAを破ることができます。

RC5は、1994年にロナルド・リベストによって設計されたブロック暗号で、他の多くの暗号とは異なり、ブロックサイズ（32、64、または128ビット）、鍵サイズ（0～2040ビット）、ラウンド数（0～255）を可変にすることができます。当初提案されたパラメータは、ブロックサイズ64ビット、鍵長128ビット、ラウンド数12でした。

RC5の重要な特徴は、データ依存回転の使用です。RC5の目標の1つは、このような操作を暗号プリミティブとして研究および評価することを促すことでした。RC5はまた、多数のモジュラー加算とXORで構成されています。アルゴリズムの一般的な構造は、Feistelのようなネットワークです。暗号化および復号ルーチンは、数行のコードで指定できます。ただし、鍵スケジュールはより複雑で、eと黄金比の両方のバイナリ展開を「隠し数字なし」のソースとして、基本的に一方向関数を使用して鍵を拡張します。アルゴリズムの魅力的な単純さとデータ依存回転の斬新さにより、RC5は暗号解読者にとって魅力的な研究対象となっています。

12ラウンドのRC5（64ビットブロック）は、2 ^{44の選択平文を使用した}差分攻撃に対して脆弱である。^{[ 44 ]} 18～20ラウンドが十分な保護として推奨されている。

ベルギーの暗号学者、ジョアン・デーメンとヴィンセント・ライメンによって開発されたラインダール暗号は、DESに代わる暗号方式として競合する候補の一つでした。そして、5年間にわたる公開コンペティションを勝ち抜き、AES（Advanced Encryption Standard：高度暗号化標準）となりました。

2001年にNISTによって採用されたAESは、ブロックサイズが128ビットに固定され、鍵サイズは128、192、または256ビットです。一方、Rijndaelは、ブロックサイズと鍵サイズを32ビットの倍数で指定でき、最小値は128ビットです。ブロックサイズは最大256ビットですが、鍵サイズには理論上の最大値はありません。AESは、状態と呼ばれる4×4列優先順序のバイト行列で動作します（ブロックサイズが大きいRijndaelのバージョンでは、状態に列が追加されます）。

Blowfish は、1993 年にBruce Schneierによって設計され、多数の暗号スイートや暗号化製品に採用されているブロック暗号です。Blowfish は 64 ビットのブロックサイズを持ち、鍵長は1 ビットから 448 ビットまで可変です。 ^{[ 45 ]}これは 16 ラウンドのFeistel 暗号で、鍵に依存する大きなS ボックスを使用します。設計上の注目すべき特徴としては、鍵に依存するS ボックスと非常に複雑な鍵スケジュールが挙げられます。

これは汎用アルゴリズムとして設計され、老朽化し​​たDESに代わるものとして、他のアルゴリズムに伴う問題や制約から解放されることを意図していました。Blowfishがリリースされた当時、他の多くの設計は特許で保護されていたり、企業秘密や政府秘密であったりしました。シュナイアー氏は、「Blowfishは特許を取得しておらず、今後もすべての国で特許を取得しない。このアルゴリズムはパブリックドメインに置かれ、誰でも自由に利用できる」と述べています。シュナイアー氏の後継アルゴリズムであるTwofishにも同じことが言えます。

ブロック暗号にはいくつかの種類があり、それらは一般的に特定の地域や管轄区域でのみ使用されています。よく知られているものとしては、以下のようなものがあります。

• SM4 — 中国
• クズニェチク(GOST R 34.12-2015) — ロシア
• GOST 28147-89 — ソビエト連邦／ロシア（廃止）
• ARIA — 韓国
• シード— 韓国
• ツバキ― 日本原産。国際的にもある程度使用されている。
• カリナ— ウクライナ

M. Liskov、R. Rivest、および D. Wagner は、「調整可能」ブロック暗号と呼ばれるブロック暗号の一般化バージョンについて説明しました。^{[ 46 ]}調整可能ブロック暗号は、通常の平文または暗号文の入力に加えて、調整と呼ばれる 2 番目の入力を受け取ります。調整は、鍵とともに、暗号によって計算される順列を選択します。調整の変更が十分に軽量である場合 (通常かなりコストのかかる鍵設定操作と比較して)、いくつかの興味深い新しい動作モードが可能になります。ディスク暗号化理論の記事では、これらのモードのいくつかについて説明しています。

ブロック暗号は従来、バイナリアルファベット上で動作します。つまり、入力と出力はどちらも、n個のゼロとイチからなるバイナリ文字列です。しかし、状況によっては、別のアルファベット上で動作するブロック暗号が必要になる場合があります。たとえば、16 桁のクレジットカード番号を暗号化して、暗号文も 16 桁の数字になるようにすると、既存のソフトウェアに暗号化レイヤーを追加しやすくなります。これは、フォーマット保持暗号化の一例です。より一般的には、フォーマット保持暗号化には、有限言語上の鍵付き順列が必要です。このため、フォーマット保持暗号化方式は、（調整可能な）ブロック暗号の自然な一般化と言えます。これに対し、CBC などの従来の暗号化方式は、固定鍵を使用した場合でも、同じ平文から複数の異なる暗号文を暗号化できるため、順列ではありません。