RIPEMD - standard

要約。暗号ハッシュ関数は、メッセージのデジタル指紋、メッセージ認証、鍵導出などのアプリケーションにおける暗号技術の重要なツールです。過去5年間で、いくつかの高速ソフトウェアハッシュ関数が提案されてきました。それらのほとんどは、Ron RivestのMD4の設計原理に基づいています。そのような提案の1つがRIPEMDで、EUプロジェクトRIPE（Race Integrity Primitives Evaluation）の枠組みで開発されました。これらのハッシュ関数の暗号解析における最近の進歩を踏まえ、160ビットの結果を持つRIPEMDの新しいバージョンと、128ビットの結果を持つRIPEMDのプラグイン代替を提案します。また、独立した関心事として、いくつかのMD4ベースのアルゴリズムのソフトウェアパフォーマンスを比較します。

1 序論と背景

ハッシュ関数は、任意の有限長のビット列を固定長の文字列にマッピングする関数です。h と入力 x が与えられたとき、h (x) の計算は容易でなければなりません。

一方向性ハッシュ関数は、以下の特性を満たす必要があります。

原像演算困難性：ハッシュ結果が事前に指定された出力となる入力を見つけることは、計算量的に不可能です。

第二原像演算困難性：ハッシュ結果が指定された入力と同じ出力となる第二の入力を見つけることは、計算量的に不可能です。

m ビットの結果を持つ理想的な一方向性ハッシュ関数の場合、原像または第二原像を見つけるには約 2^m 回の演算が必要です。衝突耐性ハッシュ関数は、以下の追加条件を満たす一方向性ハッシュ関数です。

衝突耐性：ハッシュ結果が同じ結果となる、異なる 2 つの入力、つまり衝突を見つけることは、計算量的に不可能です。

mビットの結果を持つ理想的な衝突耐性ハッシュ関数の場合、衝突を検出する最も高速な方法は、約$ 2(m/2) 回の演算を必要とする誕生日攻撃または平方根攻撃である19。

ほとんどすべてのハッシュ関数は、入力の連続する固定サイズのブロックを処理することで、任意の長さの入力をハッシュする反復処理である。入力Xはブロック長の倍数になるようにパディングされ、その後、t個のブロック$ X_1から$ X_tに分割される。ハッシュ関数hは以下のように記述できる。

$ H_0 = IV; $ H_i = f(H_{i-1},X_i), 1 \le i \le t $ h(X) = H_t.

ここで、f は h の圧縮関数、$ H_i はステージ i - 1 とステージ i 間の連鎖変数、IV は初期値を表します。

衝突耐性ハッシュ関数は、実用的なデジタル署名方式の文脈で初めて使用されました。これらの方式の効率（およびセキュリティ）を向上させるために、メッセージはハッシュされ、（低速の）デジタル署名は短いハッシュ結果にのみ適用されます。その他の用途には、パスワードの保護、メッセージ認証コード（MAC）の構築、鍵バリアントの導出などがあります。

ハッシュ関数の最初の構築は、ブロック暗号（DES など）に基づいていました 8, 9, 10。これらの提案のセキュリティにはある程度の信頼が築かれてきましたが、ソフトウェアパフォーマンスはあまり良くなく、通常、対応するブロック暗号よりも 2 . . . 4 倍遅くなります。モジュラー算術に基づくハッシュ関数も同様に遅く、そのセキュリティについて深刻な疑問が提起されています。

現在、幅広いアプリケーションで使用されている最も一般的なハッシュ関数は、MD4 ファミリのカスタム設計されたハッシュ関数です。

MD4 は 1990 年に R. Rivest によって提案されました 13, 14。これは 32 ビットプロセッサ向けに調整された非常に高速なハッシュ関数です。3 で特定された予期せぬ脆弱性 (3 ラウンドのうち 2 ラウンドで衝突が発生する) のため、R. Rivest は 1991 年に MD4 の強化版である MD5 15 を設計しました。MD4 は非常に保守的な設計ではなかったものの、製品への実装が迅速だったという理由もありました。MD5 は、4 で MD5 の圧縮関数が衝突耐性がない (検出された衝突はメッセージブロックではなく連鎖変数を変更する) ことが示されているにもかかわらず、おそらく最も広く使用されているハッシュ関数です。これは MD5 の標準的なアプリケーションにとっては脅威にはなりませんが、それでも設計原則の 1 つに違反していることになります。 RIPEコンソーシアム^3は、推奨される整合性プリミティブのポートフォリオ12を提案することを目標としていました。MD4とMD53, 4の独自の評価に基づき、コンソーシアムはMD4の強化版であるRIPEMDを提案しました。RIPEMDは基本的にMD4の2つの並列バージョンで構成され、シフトとメッセージワードの順序にいくつかの改良が加えられています。2つの並列インスタンスの違いはラウンド定数のみです。圧縮関数の最後に、左半分と右半分のワードが追加されます。

*3 C.W.I.（オランダ）主契約者、オーフス大学（デンマーク）、KPN（オランダ）、ルーヴェン・カトリック大学（ベルギー）、Phillips Crypto B.V.（オランダ）、およびSiemens AG（ドイツ）。

MD5 の 2 つ目の代替として、NSA が設計し NIST (米国国立標準技術研究所) が公開したセキュアハッシュアルゴリズム (SHA-1) があります 7。このアルゴリズムの主な改良点は、結果のサイズが大きくなったこと (他の方式では 128 ビットであるのに対し、SHA-1 では 160 ビット)、および各ラウンドのメッセージワードが並べ替えられるのではなく、前のメッセージワードの合計として計算される点です。この主な結果として、数ビットに限定したローカルな変更を加えることが非常に困難になります。個々のメッセージビットが多数の場所で計算に影響するからです。1993 年 5 月に公開された SHA の最初のバージョンでは、この特性が弱められており (ワード内の異なる位置にあるビットが混合されない)、これを利用すれば $ 2^{80} 回の演算よりも高速に衝突を生成できるようです。ただし、詳細は公開されていません。この弱点は 1995 年 4 月に公開された改良版では解消されています。

本稿の残りの部分は、以下のとおりです。§2では、RIPEMDの新バージョンが提案される理由をより詳細に議論します。§3では新しいスキームについて説明し、§4では設計上の決定の理由を説明します。§5では、RIPEMDの新バージョンのパフォーマンスを他のMD4ベースのハッシュ関数と比較します。§6では結論を示します。

2 RIPEMDの新バージョン開発の動機

MD4の主な貢献は、現在の32ビットプロセッサの構造を最適に活用した最初の暗号ハッシュ関数であることです。逐次演算の使用とリトルエンディアンアーキテクチャの優位性は、MD4がソフトウェア実装向けに調整されていることを示しています。

しかし、暗号アルゴリズムに新しい構造を導入することは、予期せぬ脆弱性のリスクも伴います。差分解読法や線形解読法といった既存の手法は適用できず、暗号解読を成功させるには新しい手法の開発が必要であることが明らかになりました。

B. den BoerとA. BosselaersによるMD4の3ラウンド中2ラウンド3とMD5の圧縮関数4に対する攻撃は、アルゴリズムの一部の構造的特性が悪用される可能性があることを初めて示しましたが、アルゴリズム全体に対する深刻な脅威とは考えられませんでした。最近では、MD4に対する攻撃がS. Vaudenay 18 によって改良され、わずか数ビットしか違わない2つのハッシュ結果が生成されました。これは、MD4がランダム関数に期待されるような動作をしないことを明確に示しています（例えば、1 で定義されているような相関耐性はありません）。

1995年初頭、H. DobbertinはRIPEMD 5の3ラウンドのうち最後の2ラウンド（後に最初の2ラウンド）で衝突を発見しました。これは3ラウンドのRIPEMDに対する直接の脅威ではありませんが、この攻撃は非常に驚くべきものでした。さらに、この攻撃はこの種の関数を解読するための新しい手法を導入しました。1995年秋、H. Dobbertinはこれらの手法を拡張し、MD4 6と、MD4の拡張版の圧縮関数 13（§ 3.3も参照）で衝突を生成することに成功しました。 MD4 への攻撃は PC 上で数秒しかかからず、メッセージにいくらかの自由度が残ります。これにより、衝突耐性機能としての MD4 の使用は明らかに排除されます。

これらの技術は、MD5、そしておそらくRIPEMDでも衝突を生成するために使用できると期待されています。これにはおそらく追加の努力が必要になるでしょうが、1年前ほど遠い未来の話ではなくなりました。

RIPEMDをアップグレードする別の理由として、総当たり衝突探索攻撃に対する耐性が限られていることが挙げられます。P. van OorschotとM. Wienerは17で、24日で衝突を発見できる1000万ドルのMD5衝突探索マシンの設計を発表しました。予算が100万ドルしかなく、既存のコンピュータネットワークのメモリを使用した場合、計算には約6か月かかります。計算とメモリのコストが3年ごとに4分の1になるという事実（この観察はムーアの法則として知られています）を考慮すると、128ビットのハッシュ結果では今後10年間は十分な保護を提供できないと結論付けることができます。この方法で得られる衝突には、ランダムに見える10バイト未満が必要です。残りの入力は任意に選択できます。

RIPEMDは複数の銀行アプリケーションで使用されており、現在、ISO/IEC JTC 1/SC27においてSHA-1と共に標準化候補として検討されています。しかしながら、現状を鑑みると、現在の実装をアップグレードし、より安全な標準化スキームを検討することが賢明であるとの結論に至りました。そこで著者らは、10年以上の安全性が確保されるRIPEMD-160の強化版を設計しました。また、改良された128ビット版も提案されていますが、これは現在のアプリケーションにおいてRIPEMDの代替としてのみ使用されるべきです。

SHA-1は既に160ビットの結果を有しており、その特性から、SHA-1は既知の攻撃に対して脆弱ではない可能性が高いと考えられます。しかしながら、その設計基準と最初のバージョンに対する攻撃は秘密です。

3 新しいRIPEMDの説明

本節では、RIPEMD-160、RIPEMD-128、そしてより長いハッシュ結果を生成する2つの変種について簡単に説明する。読者はMD4の構造と表記法に精通していることを前提とする（例えば13を参照）。

3.1 RIPEMD-160

RIPEMD-160のハッシュ結果と連鎖変数のビットサイズは160ビット（32ビットワード5つ）に増加され、ラウンド数は3から5に増加し、2つのラインの差異は拡大されている（定数だけでなく、ブール関数とメッセージワードの順序も変更されている）。

これにより、以下のパラメータが生成される（RIPEMD-160の擬似コードは付録Aに示されている）。

1. 1ステップでの処理。 $ A := (A + f(B, C, D) + X + K)^{<<s} + E かつ $ C := C^{<<10} ここで $ ^{<<s} は s 位置の巡回シフト (回転) を表します。

2. メッセージワードの順序付け。次の順列pを取る。

table:p

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

p(i) 7 4 13 1 10 6 15 3 12 0 9 5 2 14 11 8

さらに、π(i) = 9i + 5 (mod 16) と設定して、順列 π を定義します。メッセージワードの順序は次の表で与えられます。

table:π

行 Round 1 Round 2 Round 3 Round 4 Round 5

left id p p^2 p^3 p^4

right π πp πp^2 πp^3 πp^4

3. Boolean関数。次のBoolean関数を定義します。

$ f_1(x,y,z) = x ⊕ y ⊕ z,

$ f_2(x, y, z) = (x ∧ y) ∨ (-x ∧ z),

$ f_3(x,y,z) = (x∨-y) ⊕z,

$ f_4(x,y,z) = (x∧z)∨(y∧-z),

$ f_5(x,y,z) = x ⊕ ( y ∨ -z ).

これらのブール関数は次のように適用される。

table:Boolean

Line Round 1 Round 2 Round 3 Round 4 Round 5

left f_1 f_2 f_3 f_4 f_5

right f_5 f_4 f_3 f_2 f_1

4. Shifts. 両方のラインに対して、次のシフトを実行します。

table:Shift

Round X_0 X_1 X_2 X_3 X_4 X_5 X_6 X_7 X_8 X_9 X_10 X_11 X_12 X_13 X_14 X_15

1 11 14 15 12 5 8 7 9 11 13 14 15 6 7 9 8

2 12 13 11 15 6 9 9 7 12 15 11 13 7 8 7 7

3 13 15 14 11 7 7 6 8 13 14 13 12 5 5 6 9

4 14 11 12 14 8 6 5 5 15 12 15 14 9 9 8 6

5 15 12 13 13 9 5 8 6 14 11 12 11 8 6 5 5

5. 定数。次の数値の整数部分を取ります。

table:Constants

Line Round 1 Round 2 Round 3 Round 4 Round 5

left 0 2^30・√2 2^30・√3 2^30・√5 2^30・√7

right 2^80・3√2 2^30・3√3 2^30・3√5 2^30・3√7 0

3.2 RIPEMD-128

LIPEMD-160 との主な違いは、128 ビット (4 つの 32 ビットワード) のハッシュ結果と連鎖変数を保持し、4 ラウンドのみが使用されることです。

1. 1ステップの演算。$ A := (A + f(B , C, D) + X + K)^{<<S}.

2. Boolean関数。ブール関数は次のように適用されます。

table:Boolean

Line Round 1 Round 2 Round 3 Round 4

left f_1 f_2 f_3 f_4

right f_4 f_3 f_2 f_1

3. 定数。次の数の整数部分を取ります。

table:Constants

Line Round 1 Round 2 Round 3 Round 4

left 0 2^30・√2 2^30・√3 2^30・√5

right 2^80・3√2 2^30・3√3 2^30・3√5 0

3.3 256ビットおよび320ビットハッシュへのオプション拡張 - 結果

ハッシュ関数の用途によっては、セキュリティレベルを高くすることなく、より長いハッシュ結果が必要となる場合があります。これを実現する簡単な方法は、初期値が異なる同じハッシュ関数の2つの並列インスタンスを使用することです。しかし、これは2つのチェーン間に望ましくない依存関係をもたらす可能性があります（このような依存関係はRIPEMDへの攻撃で悪用されています）。したがって、2つのインスタンス間の相互作用を強化することが推奨されます。

13では、初期値と第2ラウンドおよび第3ラウンドの定数のみが異なる2つのMD4インスタンスを並列実行することで、256ビットのハッシュ結果を生成するMD4の拡張が提案されました。圧縮関数を適用するたびに、レジスタAの値が2つのチェーン間で交換されます。H. Dobbertinはこの拡張の圧縮関数で衝突を生成することに成功しました。さらに、完全な拡張においても衝突を構築できると予測されます。

RIPEMD-128 と RIPEMD-160 には既に2つの並列ラインが存在するため、2つの並列インスタンスを必要とせずに、2倍の長さの拡張（それぞれ256ビットと320ビット）を構築できます。圧縮関数の各適用の最後に、2つのラインの結合を省略するだけで十分です。ラウンド1の後にレジスタAとA'の内容を、ラウンド2の後にレジスタBとB'の内容をスワップすることで、ライン間の相互作用を導入することを提案します。

4 設計決定の動機

RIPEMD-160 の主な設計方針は、§2 で提起された問題を克服することですが、RIPEMD とその先行モデルである MD4 および MDS でこれまでに得られた信頼性を最大限に高めるため、元の構造への変更は可能な限り少なく抑えます。

また、数年後に再設計のリスクを負って性能限界を押し上げるのではなく、高いセキュリティレベルを提供する、比較的保守的な設計を目指すことにしました。

RIPEMD の基本的な設計理念は、2 つの並列反復を持つことでした。

主な改善点は、ラウンド数を 3 から 5 に増やしたこと（RIPEMD-128 では 4）、そして 2 つの並列ラウンドの差異をより大きくしたことです。RIPEMD への攻撃から、2 つの行で異なる加法定数のみを使用するだけでは不十分であることがわかりました。RIPEMD-160 では、2 つの反復におけるメッセージブロックの順序が完全に異なり、さらにブール関数の順序も逆になっています。今後数年間で、2 つのラインのうちの 1 つと、2 つの平行ラインの最大 3 ラウンドの攻撃が可能になるが、2 つの平行ラインの組み合わせは攻撃に耐えられると予想されます。

RIPEMD-160 の A レジスタに対する操作は MD5 の操作と関連している (ただし 5 つのワードが関係する)。C レジスタのローテーションは、最上位ビットを対象とする MD5 攻撃を回避するために追加されている 4。SHA-1 にも 2 つのローテーションがあるが、場所は異なる。C レジスタの値が 10 に選択されたのは、他のローテーションには使用されないからである。RIPEMD-128 のステップ操作は、MD4 (および RIPEMD) の操作と同一である。

RIPEMD のメッセージワードの順列は、ラウンド 1-2 で「近い」2 つのワードがラウンド 2-3 では遠く離れるように (またはその逆) 設計されている。この順列が RIPEMD-160 に適用された場合、この基準は満たされない (メッセージブロック 2 と 13 は、長さ 2 のサイクルにより望ましくないパターンを形成する 5)。したがって、12 と 13 の値を交換することが決定され、§3.1 の順列 p が生まれました。順列 π は、左半分で近い 2 つのメッセージワードが、右半分では常に少なくとも 7 つの位置離れるように選択されました。ブール関数については、対称性とパフォーマンス上の欠点のため、多数決関数を削除することが決定されました。ブール関数は、MD5 で使用されているものと同じになりました。前述のように、左半分と右半分のブール関数は異なる順序で使用されます。

RIPEMD のシフトは、内部レポートでのみ文書化された特定の戦略に従って選択されました。同じ戦略が、強化されたアルゴリズムに簡単な方法で拡張されています。設計基準は次のとおりです。

シフト数は5から15の間で選択します（シフト数が小さすぎる/大きすぎるとあまり良くないとみなされ、16より大きい値を選択してもあまり効果はありません）。

各メッセージブロックは異なる量でローテーションされ、すべてが同じパリティを持つべきではありません。

各レジスタに適用されるシフトは特別なパターンを持たないようにします（例えば、合計が32で割り切れない）。

4で割り切れるシフト定数は、あまり多くない状態にします。

設計上の決定には妥協が必要であることに注意してください。5ラウンドのメッセージ順序とシフト定数を適切に選択し、同時に5ラウンドのうち3ラウンドでも「最適」な値を得ることは不可能です。

5 パフォーマンス評価

このセクションでは、RIPEMD-160、RIPEMD-128、RIPEMD、SHA-1、MD5、およびMD4のパフォーマンスを比較します。実装は、Pentiumプロセッサ（90MHz）向けに最適化されたアセンブリ言語で記述されています。数値は現実的な入力値、つまり8KBのバッファを使用して256MBのデータをハッシュした場合のものです（これはキャッシュメモリから短いブロックをハッシュするよりも低速です）。相対的な速度は、単純な演算回数に基づく予測値とほぼ一致しています。RIPEMD-160はSHA-1より約15%遅く、RIPEMDの半分の速度、MD4の4倍の速度です。ビッグエンディアンのRISCマシンでは、SHA-1とRIPEMD-160の差はわずかに大きくなります。

RIPEMD-128はRIPEMDよりも30%遅いです。最適化されたC実装では1.8倍、2.2倍遅くなります。MD5の場合、我々のCコードは16よりも36%高速です。

table:表1 90 MHz Pentium 上でのいくつかの MD4 ベースのハッシュ関数のパフォーマンス

アルゴリズム性能(Mbit/s)

Assembly C

MD4 165.7 81.4

MD5 113.5 59.7

SHA-1 46.5 21.2

RIPEMD 82.1 44.0

RIPEMD-128 63.8 35.6

RIPEMD-160 39.8 19.3

6.結論

RIPEMDの拡張版であるRIPEMD-160を提案しました。RIPEMDで培われた信頼性が新しいアルゴリズムに引き継がれるように設計されています。セキュリティが大幅に向上する一方で、パフォーマンスは低下（2分の1）しますが、それでも速度は許容範囲内です。RIPEMD-160のセキュリティに関するコメントや結果をお待ちしています。

謝辞 Bert den Boer、Markus Dichtl、Walter Fumy、Peter Landrockの各氏には、励ましと助言をいただき、感謝申し上げます。

参考文献

1. R. Anderson, "The classification of hash functions," Proe. of the IMA Conference on Cryptography and Coding, Cirencester, December 1993, Oxford University Press, 1995, pp. 83-95.

2. I.B. Damgs, "A design principle for hash functions," Advances in Cryptology, Proc. Crypto'89, LNCS 435, G. Brassard, Ed., Springer-Verlag, 1990, pp. 416-427.

3. B. den Boer, A. Bosselaers, "An attack on the last two rounds of MD4," Advances in Cryptology, Proc. Crypto'91, LNCS 576, J. Feigenbaum, Ed., Springer-Verlag, 1992, pp. 194-203.

4. B. den Boer, A. Bosselaers, 「MD5 圧縮関数における衝突」, Advances in Cryptology, Proe. Eurorypt'93, LNCS 765, T. Helleseth 編, Springer-Verlag, 1994, pp. 293-304.

5. H. Dobbertin, 「2ラウンド圧縮関数を用いたRIPEMDは衝突フリーではない」, Journal of Cryptology, 掲載予定.

6. H. Dobbertin, 「MD4 の暗号解析」, Fast Soft-are Encryption, 本巻.

7. FIPS 180-1, セキュアハッシュ標準, NIST, 米国商務省, ワシントン D.C., 1995年4月.

8. R. Merkle, 「一方向ハッシュ関数と DES」, Advances in Cryptology, Proc. Crypto'89, LNCS 435, G. Brassard編, Springer-Verlag, 1990, pp. 428-446.

9. C.H. Meyer, M. Schilling, "Secure program load with Manipulation Detection Code," Proc. Securicom 1988, pp. 111-130.

10. B. Preneel, R. Govaerts, J. VandewaUe, "Hash functions based on block ciphers: asynthesis approach," Advances in Cryptology, Proc. Crypto'93, LNCS 773, D. Stinson編, Springer-Verlag, 1994, pp. 368-378.

11. B. Preneel, Cryptographic Hash Functions, Kluwer Academic Publishers, 近日公開予定.

12. RIPE, 「セキュア情報システムのための整合性プリミティブ．RACE整合性プリミティブ評価の最終報告書 (RIPE-RACE 1040)」，LNCS 1007，Springer-Verlag，1995年．

13. R.L. Rivest, 「MD4メッセージダイジェストアルゴリズム」，Advances in Cryptology, Proe. Crypto'90，LNCS 537，S. Vanstone編，Springer-Verlag，1991年，303-311頁．

14. R.L. Rivest, 「MD4 メッセージダイジェストアルゴリズム」、Request for Comments (RFC) 1320、インターネット活動委員会、インターネットプライバシータスクフォース、1992年4月。

15. R.L. Rivest, 「MD5 メッセージダイジェストアルゴリズム」、Request for Comments (RFC) 1321、インターネット活動委員会、インターネットプライバシータスクフォース、1992年4月。

16. J. Touch, 「MD5 の性能に関する報告」、Request for Comments (RFC) 1810、インターネット活動委員会、インターネットプライバシータスクフォース、1995年6月。

17. P.C. van Oorschot, M.J. Wiener, 「並列衝突探索とハッシュ関数および離散対数への応用」、Proc. 2nd A CM Conference on Computer and Communications Security、ACM、1994年、pp. 210-218。

18. S. Vaudenay, 「多重順列の必要性について：MD4とSAFERの暗号解読」, Fast Software Eneryption, LNCS 1008, B. Preneel編, Springer-Verlag, 1995, pp. 286-297.

19. G. Yuval, 「ラビンを騙す方法」, Cryptologia, Vol. 3, No. 3, 1979, pp. 187-189.

A RIPEMD-160 の擬似コード

RIPEMD-160 は、32ビットワードを処理する反復ハッシュ関数です。ラウンド関数は、5ワードの連鎖変数と16ワードのメッセージブロックを入力として受け取り、これを新しい連鎖変数にマッピングします。すべての演算は32ビットワードで定義されます。パディングはMD4 13, 14 と同じです。テスト値は付録Bに記載されています。まず、すべての定数と関数を定義します。