ハスティ・プディング暗号

ハスティ・プディング暗号
一般的な
デザイナー	リチャード・シュロッペル
初版	1998年6月
暗号の詳細
キーサイズ	変数
ブロックサイズ	変数

ハスティ・プディング暗号( HPC )は、リチャード・シュロッペルが設計した可変ブロックサイズのブロック暗号で、米国の高度暗号化標準(AES)の選定競争で落選した。ブロック暗号としては珍しい特性がいくつかある。入力ブロックサイズとキーの長さが可変で、二次的な非秘密キーとして使用するための「スパイス」と呼ばれる追加の入力パラメータが含まれている。ハスティ・プディング暗号は、米国の暗号学者によってのみ設計された唯一の AES 候補であった。^[1]^[2]

ハスティ・プディング暗号はパブリックドメインであり^[3]、オープンソースの実装も利用可能である。^[4]

暗号

ハスティ・プディング暗号は5つの異なるサブ暗号から構成されている。^[5]

Hasty Pudding 暗号アルゴリズムはすべて、内部で 64 ビットワードを使用します。この暗号は 64 ビットマシンで実行するように設計されており、64 ビットワードで簡単な操作を簡単に実行できます。

キー拡張

ハスティ・プディング暗号は、5つのサブ暗号のいずれに対しても、任意のビット数の鍵を取ることができる。暗号自体は16,384ビット（256個の64ビットワード）の鍵テーブルを使用する。鍵から鍵テーブルを導出するために、鍵拡張機能は次のアルゴリズムを使用する：^[5]

最初の 3 つのワードKX [0]、KX [1]、KX [2] は、定数、サブ暗号、およびキーの長さに基づいて設定されます。KX [1]は乗算で計算され、その他の演算は加算とビットシフトです。
後続の各単語KX [ i ]は、効率的な再帰式によって前の3つの単語から決定されます。
キービットは、 KX [0]から始まり、すべてのキービットが使用されるまで、キーテーブルのビットに XOR されます。(8,192 ビットを超えるキーでは、より複雑な手順が使用されます。)
キーテーブルに対して複数のパスが実行されます。そのたびに、キーテーブルの各ワードに「攪拌機能」が順番に適用されます。攪拌機能は 8 つの内部変数を使用し、14 の論理ビット演算、5 ビットシフト、および 14 の加算/減算を使用します。攪拌機能を使用するたびに、キーテーブル内の 1 つのワードが、その前の値、他の特定のワードの値、および攪拌機能の内部変数に基づいて変更されます (合計 3 回のパスがデフォルトです)。

暗号化と復号化

それぞれのサブ暗号は異なるアルゴリズムを使用しますが、ある程度の類似点があります。暗号文を決定するために、平文 (複数の 64 ビットワードと 1 つの「フラグメント」)、スパイス (8 つの 64 ビットワード、デフォルト値は 0)、およびキーテーブルという 3 つの入力が使用されます。暗号内の操作は、一定の間隔でキーテーブルとスパイスの値を使用してさまざまな方法で内部変数を組み合わせるStirringで構成されます。HPC-Short ではさらに 2 つの固定順列が使用され、HPC-Tiny では多くの特殊なサブケースで構成されます。

復号化では、暗号化の手順を 1 つずつ元に戻します。多くの操作は簡単に元に戻すことができます (例: s ₀ = s ₀ + s _1は、s ₀ = s ₀ − s ₁を計算することで元に戻すことができます)。その他の操作は元に戻すのがより複雑です。関連するアイデアには次のものがあります。

x = x ⊕ ( x >> 17)のような演算は、(1) x = x ⊕ ( x >> 17)、続いて (2) x = x ⊕ ( x >> 34)という2段階のプロセスによって元に戻されます。
暗号は、値に依存したキーテーブルの検索を使用します。この検索は変数の最後の 8 ビットのみに依存するため、元に戻すことができます。また、復号化でキーテーブルから値を検索する必要がある場合、キーテーブル値なしではすべての操作を元に戻すことができない場合でも、計算の特定の以前の時点での値の最後の 8 ビットは予測可能です。たとえば、kの検索がxの最後の 8 ビットに基づいている場合、 x = x ⊕ ( k << 8)のような手順を元に戻したい場合、 xの最後の 8 ビットはこの操作では変更されないことに注意してkを検索できます。

ハスティ・プディング暗号は、整数ビットの文字列に変換できない範囲の値を暗号化するためにも使用できます。たとえば、0 から N までの数字を暗号化するには、0 からNまでの別の数字を生成します。これは、入力をビット文字列として処理できる最小のサブ暗号を使用し、出力が適切な範囲になるまで、それを入力にビット文字列として繰り返し適用することで行われます。^[5]

パフォーマンス

Schroeppelは、Hasty Pudding暗号が64ビットアーキテクチャ上で最速のAES候補であると主張した。^{[6] Schroeppelは、この暗号は最も近い競合相手である}DFCの2倍、他の候補の3倍の速さであり、32ビットマシン上でのパフォーマンスは適切であると主張した。^[6] 他の人からのコメントはこの見解を支持しなかった。例えば、Schneierらの分析では、Hasty Pudding暗号は64ビットマシン上で4番目に優れている（376サイクル）と評価されたが、RijndaelとTwofishの場合、パフォーマンスは推定値に過ぎなかった。^[7] 32ビットのPentiumでは、Hasty Pudding暗号化はSchneierらによって1600クロックサイクルと評価され、15の候補の中で10番目に優れている。^[7] シュナイアーらとシュロッペルは、64ビット演算、特にビットシフトを多用するため、32ビットマシンでは暗号の速度に著しい影響が出ると指摘した。^[3]^[7]

ハスティ・プディング暗号の鍵設定は比較的遅いと評価され、ペンティアムで120000サイクルかかった。^[7]

この暗号はスマートカード上でのパフォーマンスについて批判された。特に、鍵テーブル用に2KB以上のRAMを保持することの難しさを指摘するコメントもあった。^[8]

さらなる作業

ハスティ・プディング暗号を攻撃する研究結果は比較的少ない。AES プロセスの初期段階で、デイビッド・ワグナーは、比較的大規模なクラスのハスティ・プディング鍵が同じ鍵表につながる点で同等であると指摘した。^{[9]この点は、128 ビット鍵の場合、約 2}^{120 個}の鍵がそれぞれ 2 ^{30 個}の同等の鍵を持つ弱い鍵であると指摘した D'Halluin らによって拡張された。^[10] この攻撃に対応して、シュロッペルは鍵拡張アルゴリズムを修正し、1 つの追加ステップを含めた。^[5]

暗号解読が比較的少ないにもかかわらず、ハスティ・プディング暗号は理解しにくい設計と研究結果の根拠が欠けていると批判された。^[9]^[11]シュロッペルはハスティ・プディング暗号の進歩を発表した最優秀論文にドン・ペリニヨンのシャンパンを1本提供した。 ^[3]ハスティ・プディング暗号はAESの第2ラウンドの検討には残らなかった。^[12]

ハスティ・プディング暗号は、最初の調整可能なブロック暗号と考えられている。^[13]

参考文献

^ Eli Biham、「AES 候補の比較に関する注記」、1999 年 4 月、AES に関するパブリックコメント。
^ Susan Landau、「21世紀の通信セキュリティ：高度暗号化標準」、Notices of the AMS、第47巻、第4号、2000年。
^ abc Rich Schroeppel と Hilarie Orman、「Hasty Pudding 暗号の概要」、 1998 年 7 月。
^ GitHubのiscgar/hasty-pudding。
^ abcd Schroeppel, Rich (1998年6月)、Hasty Pudding Cipher Specifications (1999年5月改訂版)、2011年7月17日にオリジナルからアーカイブ、2009年6月10日に取得
^ ab Rich Schroeppel、「The Hasty Pudding Cipher: One Year Later」、2008 年 9 月 1 日にアクセス
^ abcd Bruce Schneier、John Kelsey、Doug Whiting、David Wagner、Chris Hall、Niels Ferguson、「AES 提出物のパフォーマンス比較」、第 2 回 AES 候補会議、1999 年。
^ Emanoil Daneliuc、AES 候補に関するパブリックコメント、1999 年 2 月。
^ ab David Wagner、「HPC の同等キー」、第 2 回 AES カンファレンスでの講演、ローマ、1999 年 3 月。
^ Carl D'Halluin、Gert Bijnens、Bart Preneel、およびVincent Rijmen、HPC の等価キー、暗号学の進歩 — ASIACRYPT の議事録 1999、1999。
^ Olivier Baudron、Henri Gilbert、Louis Granboulan、Helena Handschuh、Antoine Joux、Phong Nguyen、 Fabrice Noilhan、David Pointcheval、Thomas Pornin、Guillaume Poupard、Jacques Stern、およびSerge Vaudenay、AES 候補者に関する報告、第 2 回 AES 会議、1999 年 3 月。
^ James Nechvatal、Elaine Barker、Lawrence Bassham、William Burr、Morris Dworkin、James Foti、およびEdward Roback、「Advanced Encryption Standard (AES) の開発に関する報告書」、NIST公式リリース、2000 年 10 月 2 日。
^ Moses Liskov、Ronald Rivest、David Wagner、「Tweakable Block Ciphers」、Advances in Cryptology — Proceedings of CRYPTO '02、2002 年。

参照

フォーマット保存暗号化

[1] Eli Biham、「AES 候補の比較に関する注記」、1999 年 4 月、AES に関するパブリックコメント。

[2] Susan Landau、「21世紀の通信セキュリティ：高度暗号化標準」、Notices of the AMS、第47巻、第4号、2000年。

[hpc-overview-3] Rich Schroeppel と Hilarie Orman、「Hasty Pudding 暗号の概要」、 1998 年 7 月。

[4] GitHubのiscgar/hasty-pudding。

[hpc-spec-5] Schroeppel, Rich (1998年6月)、Hasty Pudding Cipher Specifications (1999年5月改訂版)、2011年7月17日にオリジナルからアーカイブ、2009年6月10日に取得

[hpc-oneyearlater-6] Rich Schroeppel、「The Hasty Pudding Cipher: One Year Later」、2008 年 9 月 1 日にアクセス

[schneier-7] Bruce Schneier、John Kelsey、Doug Whiting、David Wagner、Chris Hall、Niels Ferguson、「AES 提出物のパフォーマンス比較」、第 2 回 AES 候補会議、1999 年。

[8] Emanoil Daneliuc、AES 候補に関するパブリックコメント、1999 年 2 月。

[wagner-9] David Wagner、「HPC の同等キー」、第 2 回 AES カンファレンスでの講演、ローマ、1999 年 3 月。

[10] Carl D'Halluin、Gert Bijnens、Bart Preneel、およびVincent Rijmen、HPC の等価キー、暗号学の進歩 — ASIACRYPT の議事録 1999、1999。

[11] Olivier Baudron、Henri Gilbert、Louis Granboulan、Helena Handschuh、Antoine Joux、Phong Nguyen、 Fabrice Noilhan、David Pointcheval、Thomas Pornin、Guillaume Poupard、Jacques Stern、およびSerge Vaudenay、AES 候補者に関する報告、第 2 回 AES 会議、1999 年 3 月。

[12] James Nechvatal、Elaine Barker、Lawrence Bassham、William Burr、Morris Dworkin、James Foti、およびEdward Roback、「Advanced Encryption Standard (AES) の開発に関する報告書」、NIST公式リリース、2000 年 10 月 2 日。

[13] Moses Liskov、Ronald Rivest、David Wagner、「Tweakable Block Ciphers」、Advances in Cryptology — Proceedings of CRYPTO '02、2002 年。