RadioGatún
RadioGatúnは、Guido Bertoni、Joan Daemen、Michaël Peeters、Gilles Van Asscheらによって考案された暗号ハッシュプリミティブです。このハッシュ関数は、2006年にNIST（アメリカ国立標準技術研究所）が主催したハッシュ関数コンテストで発表されました。RadioGatúnは、1990年代後半に脆弱性が指摘されたストリーム暗号であるパナマを基に開発されましたが、ハッシュ関数として使用する際にはパナマの弱点が解消されていることが確認されています。
RadioGatúnは、パラメータによって区別される64種類のハッシュ関数の集合体です。ワード幅（w）は1から64ビットの間で調整でき、それぞれのサイズに対応した58ワードに変換して格納します。例えば、32ビット版では232バイト、64ビット版では464バイトに変換されます。また、ハッシュ関数だけでなく、擬似乱数ストリームを出力するストリーム暗号としても利用可能です。この特性から、RadioGatúnは「拡張可能出力関数（XOF）」としても知られています。さらに、RadioGatúnの開発チームは、この暗号プリミティブを大幅に改訂し、後にSHA-3アルゴリズムを開発しました。
RadioGatúnの設計者は、論文の中で、出力の最初の19×wビット（wは使用されるワード幅）が暗号学的に安全なハッシュ関数であると述べています。つまり、32ビット版では最初の608ビット、64ビット版では1216ビットを暗号化ハッシュ値として使用できます。誕生日攻撃に対する安全性も考慮されており、ワード幅wに対して、RadioGatúnは2^(9.5w)未満の複雑さの攻撃に対して耐性を持つように設計されています。これは、32ビット版では2^304、64ビット版では2^608に対応します。
設計者たちは、セキュリティをさらに改良し、19wの容量を持つ暗号スポンジ機能のセキュリティを確保しています。これにより、32ビット版では衝突攻撃と原像攻撃に対して304ビットのセキュリティ、64ビット版では608ビットのセキュリティが保証されています。
「RadioGatúnに対する2つの攻撃」という論文で、Dmitry KhovratovichとAlex Biryukovは、設計者のセキュリティポリシーを破らない2^(18w)と2^(23.1w)の複雑さを持つ2つの攻撃を提示しました。Khovratovichはその後、「構造を持つハッシュ関数の解読」という論文で、2^(18w)の複雑さを持つ攻撃を記述しています。
さらに、「代数的手法を用いたRadioGatúnの衝突攻撃の解析」という論文では、Charles BouillaguetとPierre-Alain Fouqueが2^(24.5)回の操作を必要とする攻撃を用いて、アルゴリズムの1ビット版で衝突を生成することに成功しました。ただし、この攻撃をより大きな幅に拡張することはできないとされています。この攻撃は他の攻撃よりも効果的ではありません。
Thomas FuhrとThomas Peyrinによる論文「Cryptanalysis of RadioGatun」では、2^(11w)の複雑さを持つ最も効果的な攻撃が示されました。しかし、この攻撃もセキュリティポリシーを破るものではありません。
開発者たちは、自分たちの実験ではこのアルゴリズムのセキュリティに問題はないと結論付けています。
RadioGatúnの設計者は、テストベクトルを提供しており、プログラマーがアルゴリズムを正しく実装しているかどうかを検証できるようになっています。公開されているのは、32ビット版と64ビット版のテストベクトルです。これらのテストベクトルは、RadioGatúnの任意の長い出力ストリームの最初の256ビットを示しています。
以下は、32ビット版と64ビット版のテストベクトルの例です。
32ビット版の例
RadioGatun32 =
F30028B54AFAB6B3E55355D277711109A19BEDA7091067E9A492FB5ED9F20117
RadioGatun32 =
191589005FEC1F2A248F96A16E9553BF38D0AEE1648FFA036655CE29C2E229AE
RadioGatun32 =
EBDC1C8DCD54DEB47EEEFC33CA0809AD23CD9FFC0B5254BE0FDABB713477F2BD
64ビット版の例
RadioGatun64 =
64A9A7FA139905B57BDAB35D33AA216370D5EAE13E77BFCDD85513408311A584
RadioGatun64 =
6219FB8DAD92EBE5B2F7D18318F8DA13CECBF13289D79F5ABF4D253C6904C807
RadioGatun64 =
C06265CAC961EA74912695EBF20F1C256A338BC0E980853A3EEF188D4B06FCE5
The RadioGatún Hash Function Family
rg32hash
[1] "The Road from Panama to Keccak via RadioGatún"
The RadioGatún Hash Function Family
* "Two attacks on RadioGatún"
RadioGatúnの構造
RadioGatúnは、パラメータによって区別される64種類のハッシュ関数の集合体です。ワード幅（w）は1から64ビットの間で調整でき、それぞれのサイズに対応した58ワードに変換して格納します。例えば、32ビット版では232バイト、64ビット版では464バイトに変換されます。また、ハッシュ関数だけでなく、擬似乱数ストリームを出力するストリーム暗号としても利用可能です。この特性から、RadioGatúnは「拡張可能出力関数（XOF）」としても知られています。さらに、RadioGatúnの開発チームは、この暗号プリミティブを大幅に改訂し、後にSHA-3アルゴリズムを開発しました。
セキュリティ
RadioGatúnの設計者は、論文の中で、出力の最初の19×wビット（wは使用されるワード幅）が暗号学的に安全なハッシュ関数であると述べています。つまり、32ビット版では最初の608ビット、64ビット版では1216ビットを暗号化ハッシュ値として使用できます。誕生日攻撃に対する安全性も考慮されており、ワード幅wに対して、RadioGatúnは2^(9.5w)未満の複雑さの攻撃に対して耐性を持つように設計されています。これは、32ビット版では2^304、64ビット版では2^608に対応します。
設計者たちは、セキュリティをさらに改良し、19wの容量を持つ暗号スポンジ機能のセキュリティを確保しています。これにより、32ビット版では衝突攻撃と原像攻撃に対して304ビットのセキュリティ、64ビット版では608ビットのセキュリティが保証されています。
攻撃実験
「RadioGatúnに対する2つの攻撃」という論文で、Dmitry KhovratovichとAlex Biryukovは、設計者のセキュリティポリシーを破らない2^(18w)と2^(23.1w)の複雑さを持つ2つの攻撃を提示しました。Khovratovichはその後、「構造を持つハッシュ関数の解読」という論文で、2^(18w)の複雑さを持つ攻撃を記述しています。
さらに、「代数的手法を用いたRadioGatúnの衝突攻撃の解析」という論文では、Charles BouillaguetとPierre-Alain Fouqueが2^(24.5)回の操作を必要とする攻撃を用いて、アルゴリズムの1ビット版で衝突を生成することに成功しました。ただし、この攻撃をより大きな幅に拡張することはできないとされています。この攻撃は他の攻撃よりも効果的ではありません。
Thomas FuhrとThomas Peyrinによる論文「Cryptanalysis of RadioGatun」では、2^(11w)の複雑さを持つ最も効果的な攻撃が示されました。しかし、この攻撃もセキュリティポリシーを破るものではありません。
開発者たちは、自分たちの実験ではこのアルゴリズムのセキュリティに問題はないと結論付けています。
開発者によるテスト
RadioGatúnの設計者は、テストベクトルを提供しており、プログラマーがアルゴリズムを正しく実装しているかどうかを検証できるようになっています。公開されているのは、32ビット版と64ビット版のテストベクトルです。これらのテストベクトルは、RadioGatúnの任意の長い出力ストリームの最初の256ビットを示しています。
以下は、32ビット版と64ビット版のテストベクトルの例です。
32ビット版の例
RadioGatun32 =
F30028B54AFAB6B3E55355D277711109A19BEDA7091067E9A492FB5ED9F20117
RadioGatun32 =
191589005FEC1F2A248F96A16E9553BF38D0AEE1648FFA036655CE29C2E229AE
RadioGatun32 =
EBDC1C8DCD54DEB47EEEFC33CA0809AD23CD9FFC0B5254BE0FDABB713477F2BD
64ビット版の例
RadioGatun64 =
64A9A7FA139905B57BDAB35D33AA216370D5EAE13E77BFCDD85513408311A584
RadioGatun64 =
6219FB8DAD92EBE5B2F7D18318F8DA13CECBF13289D79F5ABF4D253C6904C807
RadioGatun64 =
C06265CAC961EA74912695EBF20F1C256A338BC0E980853A3EEF188D4B06FCE5
参考文献
The RadioGatún Hash Function Family
rg32hash
[1] "The Road from Panama to Keccak via RadioGatún"
The RadioGatún Hash Function Family
* "Two attacks on RadioGatún"
もう一度検索
【記事の利用について】
タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。
【リンクついて】
リンクフリーです。