Twofish
AESに近い強度の暗号
ブロック長 128bit
鍵長 128, 192, 256 bit
Twofish: 128ビットブロック暗号
要約
Twofishは、最大256ビットの可変長鍵を受け入れる128ビットブロック暗号です。この暗号は、4つの鍵依存の8×8ビットSボックス、$ GF(2^8)上の固定の4×4最大距離分離可能行列、擬似アダマール変換、ビットローテーション、そして綿密に設計された鍵スケジュールからなる全単射F関数を持つ16ラウンドのFeistelネットワークです。Twofishの完全に最適化された実装は、Pentium Proで1バイトあたり17.8クロックサイクルで暗号化を実行し、8ビットスマートカード実装では1バイトあたり1660クロックサイクルで暗号化を実行します。Twofishは、14000ゲートのハードウェアで実装できます。ラウンド関数と鍵スケジュールの設計により、速度、ソフトウェアサイズ、鍵セットアップ時間、ゲート数、メモリの間で多様なトレードオフが可能です。私たちはTwofishを徹底的に暗号解読しました。私たちの最善の攻撃は、$ 2^{22.5} 個の選択された平文と $ 2^{51} の労力で 5 ラウンドを突破します。
1 はじめに
1972年と1974年、米国国立標準規格局（現在の米国国立標準技術研究所、NIST）は、暗号化規格に関する最初の公開要請を発表しました。その結果誕生したDES NBS77は、おそらく世界で最も広く使用され、成功を収めた暗号化アルゴリズムです。 その人気にもかかわらず、DESは論争に悩まされてきました。一部の暗号学者は、このアルゴリズムの「非公開」設計プロセスに異議を唱えました。DESの鍵が商用セキュリティとして許容されるには短すぎるかどうかという議論は長年にわたり激しく続いてきましたDH79が、近年の分散鍵検索技術の進歩により、DESの鍵が今日のセキュリティアプリケーションには短すぎることは疑いの余地がなくなりましたWie94, BDR+96。トリプルDESは、銀行業務など、多くの高セキュリティアプリケーションにおける暫定的なソリューションとして登場しましたが、一部の用途には速度が遅すぎます。より根本的な問題として、DESと他の多くのよく知られた暗号方式は64ビットのブロック長を共有しているため、大量のデータを同じ鍵で暗号化すると攻撃を受けやすくなります。 DESの代替を求める声が高まる中、NISTは1997年にAdvanced Encryption Standard（AES）プログラムを発表しましたNIST97a。NISTは提案された標準について一般からの意見を募り、最終的に標準を満たすアルゴリズムの募集を開始しましたNIST97b。NISTはすべての提案を公開し、最終的には一般からのレビューと意見のプロセスを経て、DESに代わる新しい暗号化標準を選定する予定です。 NISTの募集ではブロック暗号が求められました。ブロック暗号は、様々な同期特性やエラー拡張特性、一方向ハッシュ関数、メッセージ認証コード、疑似乱数生成器を備えたストリーム暗号の設計に使用できます。この柔軟性により、ブロック暗号は現代暗号の主力となっています。
NISTは、鍵長の延長、ブロックサイズの拡大、速度の高速化、柔軟性の向上など、他にもいくつかの設計基準を定めました。あらゆるニーズに最適化できる単一のアルゴリズムは存在しませんが、NISTはAESを今後10年間の標準対称アルゴリズムにすることを意図しています。
Twofishは、AES選定プロセスへの私たちの提案です。Twofishは、128ビットブロック、128ビット、192ビット、256ビット鍵、様々なプラットフォームでの効率性など、NISTが求めるすべての基準を満たし、さらにパフォーマンス面と暗号技術面の両方において、私たち独自の厳しい設計要件も満たしています。
Twofish は以下のことが可能です。
Pentium Pro 上で、12700 クロックサイクルの鍵設定後、ブロックあたり 285 クロックサイクルでデータを暗号化します。
Pentium Pro 上で、1250 クロックサイクルの鍵設定後、ブロックあたり 860 クロックサイクルでデータを暗号化します。
6805 スマートカード上で、1750 クロックサイクルの鍵設定後、ブロックあたり 26500 クロックサイクルでデータを暗号化します。
本論文は以下のように構成されています。第 2 章では Twofish の設計目標について説明します。第 3 章では、暗号の構成要素と全体的な設計について説明します。第 4 章では、暗号を定義します。第 5 章では、Twofish のパフォーマンスについて説明します。第 6 章では、採用した設計理念について説明します。第 7 章では、設計プロセスと、さまざまな選択を行った理由について説明します。第 8 章では、Twofish の最良の暗号解析結果を示します。第 9 章では、暗号におけるトラップドアの可能性について説明します。第10節では、Twofishを他の暗号と比較します。
第11節では、ファミリー鍵バリアントを含む、Twofishの様々な使用モードについて説明します。第12節では、これまでの経緯を述べ、第13節では結論と今後の分析の方向性を示します。
2 Twofish の設計目標
Twofish は、NIST の AES 設計基準 NIST97b を満たすように設計されました。具体的には、以下のとおりです。 128 ビットの対称ブロック暗号。
鍵長は 128 ビット、192 ビット、256 ビット。
脆弱鍵がない。
Intel Pentium Pro およびその他のソフトウェアおよびハードウェア プラットフォームの両方で効率が良い。
柔軟な設計：例えば、追加の鍵長に対応し、多様なプラットフォームやアプリケーションに実装可能であり、ストリーム暗号、ハッシュ関数、MAC にも適している。
分析と実装を容易にするシンプルな設計。
さらに、設計には以下の性能基準を課しました。
256ビットまでの任意の鍵長を受け入れること。
アルゴリズムを完全に最適化したバージョンでは、Intel Pentium、Pentium Pro、およびPentium IIでブロックあたり500クロックサイクル未満でデータを暗号化すること。
Pentium、Pentium Pro、およびPentium IIで32ブロックを暗号化するのに必要な時間よりも短い時間で、128ビット鍵（最適な暗号化速度）を設定できること。
Pentium、Pentium Pro、およびPentium IIで、鍵設定時間なしでブロックあたり5000クロックサイクル未満でデータを暗号化すること。
他の32ビットマイクロプロセッサで効率を低下させるような演算を含まないこと。
8ビットおよび16ビットマイクロプロセッサで効率を低下させるような演算を含まないこと。
提案されている64ビットマイクロプロセッサで効率を低下させるような演算を含まないこと。例：Merced
ハードウェアで非効率になる要素を含まないこと。
鍵スケジュールに関して、様々なパフォーマンスのトレードオフがあること。
一般的な8ビットマイクロプロセッサで10ミリ秒未満でデータを暗号化できること。
64バイトのRAMしか搭載していない8ビットマイクロプロセッサでも実装可能であること。
20,000ゲート未満のハードウェアで実装可能であること。
私たちの暗号目標は以下のとおりです。
16ラウンドのTwofish（ホワイトニングなし）では、選択平文数が$ 2^{80}未満で、鍵長が$ 2^N未満である選択平文攻撃が起こらないこと。
12ラウンドのTwofish（ホワイトニングなし）では、関連鍵攻撃が起こらないこと。選択平文数が$ 2^{64}未満で、鍵長が$ 2^{N/2}未満である関連鍵攻撃が起こらないこと。
最後に、私たちは以下の柔軟性目標を掲げました。
ラウンド数が可変のバリエーションを用意する。
鍵スケジュールを事前に計算して速度を最大化するか、オンザフライで計算して俊敏性を最大化しメモリ要件を最小限に抑えることができる。さらに、専用ハードウェアアプリケーションにも適している必要がある（例えば、大きなテーブルを必要としない）。
よく理解されている構築手法を用いて、ストリーム暗号、一方向ハッシュ関数、MAC、疑似乱数生成器として使用できる。
相互運用性のない異なるバージョンの暗号を可能にするために、ファミリー鍵のバリエーションを用意する。
Twofishの設計において、これらの目標はすべて達成できたと考えています。
3 Twofish の構成要素
3.1 Feistel ネットワーク
Feistel ネットワークの基本的な構成要素は F 関数、つまり入力文字列をキーに依存した出力文字列にマッピングする関数です。 F関数は常に非線形であり、非全射となる可能性もある1:
$ F : \bigr\{0, 1\bigl\}^{n/2} × \big\{0, 1\big\}^N → \big\{0, 1\big\}^{n/2}
ここで、nはFeistelネットワークのブロックサイズであり、Fはブロックのn/2ビットと鍵のNビットを入力として、長さn/2ビットの出力を生成する関数である。各ラウンドにおいて、「ソースブロック」がFへの入力となり、Fの出力は「ターゲットブロック」と排他的論理和をとられ、その後、これら2つのブロックは次のラウンドのために入れ替わる。ここでの考え方は、単独では弱い暗号化アルゴリズムとなる可能性のあるF関数を、繰り返し反復処理することで強力な暗号化アルゴリズムを作成することである。
Feistelネットワークの2ラウンドは「サイクル」と呼ばれるSK96。1サイクルでは、テキストブロックのすべてのビットが1回ずつ変更される。 Twofishは、全単射なF関数を持つ16ラウンドのFeistelネットワークである。
3.2 Sボックス
Sボックスは、ほとんどのブロック暗号で使用される、テーブル駆動型の非線形置換演算です。Sボックスは入力サイズと出力サイズが可変であり、ランダムに作成することも、アルゴリズム的に作成することもできます。Sボックスは最初にLuciferで使用され、その後DESで使用され、その後はほとんどの暗号化アルゴリズムで使用されました。
Twofishは、4つの異なる、一対一で鍵依存の8×8ビットSボックスを使用します。これらのSボックスは、2つの固定された8×8ビットの順列と鍵マテリアルを使用して構築されます。
3.3 MDS行列
体上の最大距離分離可能（MDS）符号は、a体の元からb体の元への線形写像であり、a + b個の要素からなる合成ベクトルを生成する。このとき、任意の非零ベクトルにおける非零要素の最小数は少なくともb + 1であるMS77。言い換えれば、MDS写像によって生成される任意の2つの異なるベクトル間の「距離」（すなわち、異なる要素の数）は少なくともb + 1である。2つの異なるベクトル間の最小距離がこれより大きい写像は存在しないことは容易に示せるため、「最大距離分離可能」と呼ばれる。MDS写像は、a × b個の要素からなるMDS行列で表すことができる。リード・ソロモン（RS）誤り訂正符号はMDSであることが知られている。a × b行列がMDSであるための必要十分条件は、行または列を破棄することによって得られるすべての可能な正方部分行列が非特異行列であることである。 MDS行列は、セルジュ・ヴォードネイが暗号設計要素として初めて提案したVau95。Shark RDP+96とSquare DKR97はMDS行列を使用している（YMT97も参照）。ただし、この構成が初めて確認されたのは、未発表の暗号Manta3 Fer96である。Twofishは$ GF(2^8)上の単一の4行4列MDS行列を使用している。 3.4 擬似アダマール変換
擬似アダマール変換（PHT）は、ソフトウェアで高速に実行される単純な混合演算です。2つの入力aとbが与えられた場合、32ビットPHTは次のように定義されます。
$ a' = a + b \mod 2^{32}
$ b' = a + 2b \mod 2^{32}
SAFER Mas94 は拡散に8ビットPHTを広く使用しています。Twofishは、2つの並列32ビットg関数の出力を混合するために32ビットPHTを使用します。このPHTは、Pentiumファミリーを含むほとんどの最新のマイクロプロセッサで2つのオペコードで実行できます。 3.5 ホワイトニング
ホワイトニングとは、第1ラウンドの前と最終ラウンドの後に鍵素材をXORする手法であり、クフ王/カフラー王の暗号においてマークルによって用いられ、DES-X KR96 においてリベストによって独自に発明された。KR96 では、ホワイトニングによって暗号の残りの部分に対する鍵探索攻撃の困難性が大幅に向上することが示された。ラウンド数を短縮したTwofishバリアントに対する我々の攻撃では、ホワイトニングによって第1ラウンドと最終ラウンドのF関数への特定の入力が攻撃者から隠蔽されるため、暗号への攻撃の困難性が大幅に向上することを発見した。 Twofishは、最初のFeistelラウンドの前に128ビットのサブキーを、最後のFeistelラウンドの後にさらに128ビットのサブキーをXORする。これらのサブキーはラウンドのサブキーと同じ方法で計算されるが、暗号の他の場所では使用されない。
3.6 鍵スケジュール
鍵スケジュールは、鍵ビットを暗号が使用できるラウンド鍵に変換する手段です。Twofishは大量の鍵データを必要とし、複雑な鍵スケジュールを持っています。解析を容易にするため、鍵スケジュールではラウンド関数と同じプリミティブを使用しています。
4 Twofish
図1はTwofishブロック暗号の概要を示しています。Twofishは、16ラウンドのFeistel型構造を採用し、入力と出力にホワイトニング処理を加えています。Feistel型ではない要素は1ビットローテーションのみです。これらのローテーションをF関数に移動することで純粋なFeistel構造を作成できますが、出力ホワイトニング処理の直前にワードのローテーション処理を追加する必要があります。
平文は4つの32ビットワードに分割されます。入力ホワイトニング処理では、これらを4つのキーワードと排他的論理和（XOR）演算します。その後、16ラウンドの処理が続きます。各ラウンドでは、左側の2つのワードがg関数の入力として使用されます（まず、そのうちの1つを8ビットローテーション処理します）。g関数は、4つのバイト幅のキー依存Sボックスと、MDS行列に基づく線形混合処理で構成されます。2つのg関数の結果は擬似アダマール変換（PHT）を用いて結合され、2つのキーワードが追加されます。これらの2つの結果は、右側のワードにXOR演算されます（片方はまず1ビット左にローテーションされ、もう片方はその後右にローテーションされます）。次に、左半分と右半分は、次のラウンドのためにスワップされます。全ラウンド終了後、最後のラウンドのスワップが反転され、4つのワードがさらに4つのキーワードとXOR演算され、暗号文が生成されます。
より正式には、16バイトの平文p0、…、p15は、まずリトルエンディアン規則に従って、それぞれ32ビットの4つのワードP0、…、P3に分割されます。
$ P_i = \sum_{j=0}^3p(4i+j)^{2^{8j}}$ i = 0, ..., 3
入力ホワイトニングステップでは、これらの単語は拡張キーの4つの単語とXOR演算されます。
$ R_{0,i} = P_i \oplus K_i$ i = 0, ..., 3