RadioGatún

RadioGatúnはGuido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Asscheらによって考案、作成された暗号化ハッシュプリミティブである。これは最初に公表された、NISTの第二の暗号化ハッシュであり、カリフォルニア州サンタバーバラで2006年8月24日から25日にかけて開催されたNISTによるハッシュ関数を競う大会によって発表された。これは1990年代後半にてハッシュ構造が破られたストリーム暗号とハッシュ構造であるパナマから派生した暗号化ハッシュプリミティブだが、ハッシュ関数として使用すると、パナマの弱点はないことが確認されている。

RadioGatúnは実際には1つのパラメータで区別される64種類のハッシュ関数の集合体で、ワード幅はビット数 (w) の1から64の間で調整可能な幅である。仕組みは、それぞれのサイズ (w) のそれぞれ58ワードに変換し格納する。例えば、32ビットバージョンでは、232バイト、64ビットバージョンでは464バイトに変換される。さらにハッシュ関数またはストリーム暗号として使用でき、擬似乱数の任意の長いストリームを出力することができます。この種のハッシュ構造は、現在、「拡張可能出力関数」(XOF) として知られています。また、RadioGatúnを開発した同チームは、この暗号プリミティブを大幅に改訂し、SHA-3アルゴリズムを作成した。

安全性

RadioGatúnの設計者は、論文で、RadioGatúnの出力の最初の19 × wビット（wは使用されるワード幅）が暗号で安全なハッシュ関数であるとしている。つまり、32ビットバージョンの最初の608ビットと、64ビットバージョンの1216ビットを暗号化ハッシュ値として使用できると発表した。誕生日攻撃の観点から言えば、これは、与えられた単語の幅wに対して、RadioGatúnは29.5w未満の複雑さの攻撃を持たないように設計されていることを意味する。これは、32ビット版では2304、64ビット版では2608に対応している。

論文を発表して以来、設計者はセキュリティを改良し、19wの容量を持つ暗号スポンジ機能のセキュリティを保っている。つまり、32ビットバージョンを使用して、衝突攻撃と原像攻撃の両方から304ビットでのセキュリティでハッシュを作成できる。また、64ビットバージョンでは608ビットのセキュリティが保証されている。

攻撃実験

"RadioGatúnに対する2つの攻撃" という論文では、Dmitry KhovratovichとAlex Biryukovは、218wと223.1wの設計者のセキュリティポリシーを反さない2つの攻撃を提示している。また、Khovratovich氏はその後、「構造を持つハッシュ関数の解読」というタイトルの論文を発表した。これは、218wの複雑さを持つ攻撃を記述している。

「代数的手法を用いたRadioGatúnの衝突攻撃の解析」の論文では、Charles BouillaguetとPierre-Alain Fouqueは、224,5回の操作を必要とする攻撃を使用して、アルゴリズムの1ビットバージョンとの衝突を生成する攻撃を成功させている。また、「1ビット版では、nビット版に拡張することは不可能であることが判明した」と、攻撃をより大きな幅に拡張することはできないということも発表している。この攻撃は他の攻撃より効果的ではなく、またRadioGatnのセキュリティのポリシーを破ることもない。

アルゴリズムに対する最も効果的な攻撃は、211wの複雑さを持つもので、Thomas FuhrとThomas Peyrinによる論文 "Cryptanalysis of RadioGatun" に示されている。他の攻撃よりも効果的だが、この攻撃は依然としてセキュリティのポリシーを破るものではない。開発者たちは、彼ら自身の実験がこのアルゴリズムのセキュリティに問題を起こすことはないとしている。

開発者によるテスト

設計者がテストベクトル（サンプル入力のために公開されたハッシュ値で、プログラマがアルゴリズムを正しく実装していることを検証できるように公開されている）を提供している。唯一のRadioGatanの例は、32ビット版と64ビット版である。

これらのテストベクトルは、RadioGatúnの任意の長い出力ストリームの最初の256ビットのみを表示する。

RadioGatun[32]("") = 
F30028B54AFAB6B3E55355D277711109A19BEDA7091067E9A492FB5ED9F20117

RadioGatun[32]("The quick brown fox jumps over the lazy dog") = 
191589005FEC1F2A248F96A16E9553BF38D0AEE1648FFA036655CE29C2E229AE

RadioGatun[32]("The quick brown fox jumps over the lazy cog") = 
EBDC1C8DCD54DEB47EEEFC33CA0809AD23CD9FFC0B5254BE0FDABB713477F2BD

64ビットの例

RadioGatun[64]("") = 
64A9A7FA139905B57BDAB35D33AA216370D5EAE13E77BFCDD85513408311A584

RadioGatun[64]("The quick brown fox jumps over the lazy dog") = 
6219FB8DAD92EBE5B2F7D18318F8DA13CECBF13289D79F5ABF4D253C6904C807

RadioGatun[64]("The quick brown fox jumps over the lazy cog") = 
C06265CAC961EA74912695EBF20F1C256A338BC0E980853A3EEF188D4B06FCE5

参考文献

リンク集（リファレンス）