2013年の終わりに、標準化のための技術委員会「暗号情報セキュリティ」（TC 26）、ロシア連邦暗号アカデミー、およびOJSC「InfoTeKS」は、GOST R 34.11-2012をハッシュするための国家標準の暗号解析の競争を発表しました。 コンテストの条件の詳細な説明は、ウェブサイトwww.streebog.infoで公開されています。 したがって、この暗号規格の分析に関する既存の研究は、暗号分析者がGOST R 34.11-2012アルゴリズムのさらなる研究の出発点であるため、暗号分析者の関心が高まっていると考えられます。

現在、GOST R 34.11-2012の暗号解読に関するいくつかの研究が知られています。 しかし、このアルゴリズムに対する最も効果的な攻撃が提案されるのは、Zongyue Wang、Hongbo Yu、およびXiaoyun Wangの「 GOST Rハッシュ関数の暗号解読 」の仕事です。 したがって、私の意見では、この作品はこのトピックに関する作品の中で最も興味深いものです。 翻訳を提供します。

翻訳では、ハッシュ標準の元の名前が保持されます。「GOST」という名前は、1994年の標準GOST R 34.11-94を指し、「GOST R」は、研究で研究されたGOST R 34.11-2012アルゴリズムを示します。

作品は、その著者の許可を得てロシア語で翻訳および出版されています。

注釈

GOST Rは、ロシアのハッシュ関数の標準です。 この作品は、GOST Rのいくつかの結果を示しています。 攻撃は9.5ラウンドで提案され、 ^2,176操作の面倒さと^2,128バイトのメモリ要件があります。 この攻撃に基づいて、 ディスクリミネーターが提案されています（ transl。：Discriminatorに注意してください -攻撃された機能を、ランダムで同等の可能性のある機能と区別できるアルゴリズムです）。 さらに、GOST Rの512ビットバージョンのk-衝突を構築する方法が提示されます。これは、GOST Rで使用される構造の弱点を示しています。私たちの知る限り、これらはGOST Rの分析の最初の結果です。

キーワード ：ハッシュ関数、GOST R、リバウンド攻撃、マルチコリジョン。

1.はじめに

ハッシュ関数は暗号化で重要な役割を果たし、電子署名、認証、データ整合性などの多くのアプリケーションで使用されます。 MD5およびSHA-1アルゴリズムのハッキング[1、2]以来、暗号作成者は永続的で効率的なハッシュ関数を探し続けてきました。 GOSTアルゴリズムの後継であるGOST Rは、ロシアのハッシュ標準です[3]。 Whirlpool [4]と構造が似ていますが、圧縮機能でAESのようなブロック暗号も使用します。

リバウンド攻撃は、順列とブロック暗号の両方に基づいてハッシュアルゴリズムの衝突を見つけるために使用できる自由度のある技術です。 この技術は、メンデルらによって最初に提案され、切り捨てられたワールプールおよびグレストルアルゴリズムの衝突検索攻撃を生成します[5]。 定義済みの切り捨てられた差分に一致する値のペアを効率的に検索することを目的としています。 検索手順は、内部（インバウンド）フェーズと外部（アウトバウンド）フェーズの2つのフェーズに分かれています。 内部フェーズでは、攻撃者は利用可能な自由度を最大限に活用し、開始点として使用される内部フェーズの切り捨てられた差分のパスを満た​​す値のペアを多数生成します。 その後、外部フェーズでは、これらの開始点がチェックされ、外部フェーズの切り捨てられた微分のパスを満た​​す値のペアが見つかります。

Lamberger et al。[6]でこの技術を強化し、ワールプールの改善された結果を得ました。 キースキームで利用可能な自由度は、リバウンド攻撃の内部フェーズを最大2ラウンドまで拡張するために使用されます。 [6]の最良の結果は、複雑度が^2,176の 9.5ラウンドの圧縮関数のほぼ衝突です。 次に、この結果を使用して、ワールプールアルゴリズムの完全な10ラウンド圧縮関数の最初の識別アルゴリズムを構築しました。 同時に、Gilbert et al。は、[7]でリバウンド攻撃用のSuper-Sboxテクノロジーを提案しました。そこでは、2ラウンドのAESのような変換が拡張置換の1つのレベルと見なされました。 さらに、リバウンド攻撃は、AESおよびAESに似たブロック暗号[8、9]、およびARX暗号を分析するためにも使用できます（ transl。：ARXはAdd-Rotate-Xorの略で、これらの操作はARX暗号の基本）。 [10]。 最近、Duc et al。は適応リバウンド攻撃技術を使用して、[11]でKeccakの微分特性を構築しました。

ハッシュ関数の衝突を見つける代わりに、Jouxは[12]で多重衝突を構築する方法を提案しました。 彼は、反復ハッシュ関数の場合、マルチコリジョンの検索は、単一のコリジョンの検索よりも複雑ではないことを示しました。 ほとんどの場合、この方法を使用して、ハッシュ関数の構造の安定性を分析できます。

1.1。 私たちの貢献

GOST RとWhirlpool構造は類似しているため、[6]でWhirlpool分析に使用されるリバウンド攻撃はGOST Rにも適用できます。ただし、GOST RはAESのような構造でShiftRows操作の代わりに行列置換を使用します。 この違いがより大きな脆弱性につながることを示します。

この論文では、GOST Rの分析の最初の結果を示します。より正確には、[6]に示された方法と同様のリバウンド攻撃方法を使用して、4.5、5.5、7.5、および9.5の衝突検索攻撃を取得しましたGOST R圧縮機能ラウンド：GOST R圧縮機能に対する衝突検索攻撃を表に示します。 1.さらに、9.5ラウンドの攻撃が10ラウンドの弁別器に変換できることを示しました。 さらに、GOST Rのフル512ビットバージョンのマルチコリジョンを構築する方法を提案しました。この結果は、GOST Rで使用される構造が理想的ではないことを示しています。



タブ。 1. GOST Rの圧縮機能の要約結果。括弧内に示されているリソースの強度は、事前に計算されたテーブルを使用した変更された攻撃を指します。

ラウンド	労働投入/記憶	種類	説明
4,5	2 64/2 16	衝突	セクション3.3
5.5	2 64/2 64	衝突	セクション3.4
7.5	2 128/2 16	衝突	セクション3.5
9.5	2 240/2 16 （2 176/2 128 ）	衝突	セクション3.6

1.2。 仕事内容

この作業の概要：第2章でGOST Rのハッシュ関数について簡単に説明します。次に、第3章でリバウンド攻撃の詳細を説明します。 識別器については、第4章で説明します。第5章では、マルチコリジョンを構築する方法を紹介します。 最後に、第6章で作業をまとめます。

2. GOST Rのハッシュ関数

GOST Rはロシアのハッシュ標準です[3]。 512ビットのメッセージブロックを処理し、512または256ビットのハッシュ値を計算します。 lビットのメッセージは、最初に512ビットの倍数にパディングされます。 メッセージの最後に1ビットが追加されます。 その後に512-1-（ l mod 512）ゼロビットが続きます。 M = M _t ||とする M _{t -1} || ... || M ₁は、追加後のtブロックで構成されるメッセージで、ビッグエンディアン形式で表示されます。 次に、図に示すように。 1、 H （ M ）の計算は次のように説明できます。





図 1. GOST Rのハッシュ関数





ここで、 IVは事前に決定された初期値です。 リングでの加算操作を示します 。 g _N （ h 、 m ）は、GOST Rアルゴリズムの圧縮関数であり、512ビットブロック暗号に基づいており、次のように計算されます。



GOST Rで使用されるブロック暗号Eは、64バイトの状態（8 x 8配列として表されます-GF （2）フィールドでは64 x 64として表されることもあります）とラウンドキーを更新するAESバリアントで、12ラウンドを実行します。 各ラウンドでは、次のようにラウンド変換r _iを実行することで状態が更新されます。



ラウンド変換は以下で構成されます

• テーブルの置換が各ステータスバイトに個別に適用される非線形変換Sのレベル。
• バイト順列P 、状態行列の要素を並べ替える。
• 線形変換L。これは、各ステータスラインの右側で、フィールドGF （2）の64 x 64マトリックスAによる独立した乗算です。
• 演算X [ k _{i +1} ]は、演算XORによって状態にラウンドキーk _{i +1の}重ね合わせを実行します。

ラウンド鍵k _iは次のように計算されます。



ここで、 C _iはGOST Rアルゴリズムの定数であり、初期値k ₁は次のように定義されます。

状態を更新する変換の最後のラウンドの後、ブロック暗号Eの出力値、以前の状態値h _{j -1}およびメッセージブロックM _jは、圧縮関数の出力値としてXOR演算によって結合されます。

ラウンド変換r _iの結果をR _{i +1}として、変換後の中間状態S 、 P 、およびLをそれぞれR _i ^S 、 R _i ^P 、およびR _i ^{Lとして示します。} 初期状態 。

3. GOST R圧縮機能に対するリバウンド攻撃

リバウンド攻撃は、Mendel et al。[5]によって最初に提案されたハッシュ関数解析技術で、切り捨てられたラウンドでGrøstlとWhirlpoolを攻撃します。 この技術の主なアイデアは、利用可能な自由度を使用して差分パスを構築し、低い確率でフラグメントを一致させることです。 通常、これは、中間一致を含む内部フェーズと、その後の確率論的な外部フェーズで構成されます。

リバウンドテクノロジーを使用して、4.5および5.5ラウンドのGOST R圧縮関数の衝突を検出し、さらに[6]のようにキー拡張スキームの利用可能な自由度を使用して、7.5および9.5ラウンド。

3.1。 元のリバウンド攻撃

リバウンド攻撃では、圧縮関数で使用されるブロック暗号またはハッシュ関数の並べ替えが3つのコンポーネントに分割されます。 Eをブロック暗号とすると、 。 リバウンド攻撃は2つのフェーズに分けられます。

• 内部フェーズ ：このフェーズは、 E _inで選択されたいくつかの入力/出力の違いから始まり、順方向および逆方向に回線レベルを伝搬します。 次に、必要な差を満たし、1レベルの表置換後の差に対応する実際の値のすべての可能なペアが生成されます。 これらの実際の値のペアは、外部フェーズの開始点です。
• 外部フェーズ ：内部フェーズの一致ペアは、 E _fwおよびE _bwを介した順方向および逆方向の計算で使用され、目的の衝突または衝突に近い状態を取得します。 通常、 E _fwおよびE _bwは確率が低いため、より多くの開始点を取得するために内部フェーズを繰り返す必要があります。

3.2。 リバウンド攻撃の予備計算

GOST Rアルゴリズムのリバウンド攻撃について説明する前に、線形変換Lのいくつかのプロパティと圧縮関数の表形式の置換について簡単に説明します。

• Lの 差の伝播 ： Lは線形変換であるため、 Lの特定の入力差は特定の出力差につながります。 Lは各ステータスラインに独立して作用するため、特定のラインの出力の差は、このラインの入力の差のみに依存します。 文字列のアクティブバイトが1つある場合、 L変換は、アクティブバイトの位置に関係なく、常に正方向と逆方向の両方で8アクティブバイトになります。
• 微分特性 S ：特定の 、平等の解決策の数

0、2、4、6、8、および256のみがあり、それぞれ38235、22454、4377、444、25、および1の頻度で発生します。 平均して、ランダムに選択された差分（ a 、 b ）については、解として1つの値を見つけることが期待できます。 また、256 x 256の入出力の差の表は、わずかな計算で解決策を見つけるのに役立ちます。

3.3。 GOST R 4.5ラウンド圧縮機能の衝突検出

このセクションでは、4.5ラウンドに切り捨てられたGOST Rアルゴリズムの圧縮機能に対するリバウンド攻撃の使用について説明します。 攻撃の中心は、次の一連のアクティブなSボックスを持つ4ラウンドの差分パスです。







図 2. GOST Rの4.5ラウンドの圧縮機能に対する攻撃の概略図。アクティブステータスバイトは黒で強調表示されます。



リバウンド攻撃では、主にブロック暗号Eを3つのサブ暗号に分割します 。 図に示すように。 2、差動パスの最もリソースを消費する部分は、内部フェーズに隠されています。 利用可能な自由度を使用して、 Eの差動経路を保存_します。

3.3.1。 内部段階

内部フェーズの最初のステップでは、 R ₂ ^PとR ₃ ^Lのステージで同時に8バイトの差から開始し^、それぞれR ₃とR ₃ ^Sに前後に移動します（図2を参照）。 セクション3.2で説明した操作Lの違いの伝播特性に従って、 R ₃とR ₃ ^Sの両方で完全にアクティブな状態を取得します^。

内部フェーズの2番目のステップでは、入力/出力の差の適切な組み合わせを見つけるために、 r _3のレベルSでの一致を検索します。 セクション3.2に示すように、特定の差動経路に対して平均で1つのソリューションが見つかると予想されます。 合計で^2,128の異なる差動パスがあり、 R ₃とR ₃ ^Sの実際の値が^2,128を超えないことは注目に値します^。 k _3には任意の値を設定できるため、開始点の最大数は2 ^{128 + 512} = 2 ⁶⁴⁰です。

3.3.2。 外相

外部フェーズでは、内部フェーズで開発された開始点を使用し、それらの値を順方向および逆方向に処理します。 図に示すように。 図2に示すように、 R ₂ ^PとR ₃ ^Lの違いは^、それぞれR ₁とR ₅ ^Pの最初の列の違いのみにつながります。

前の手順で生成された値を使用して、4.5ラウンドに切り捨てられたGOST R圧縮関数の衝突を簡単に構築できます。 以来 、 hとkの値が同じ場合、 mとE （ k 、 m ）の同じ差は常に衝突につながります。 外部フェーズで生成された値のペアの場合、差は2 ^-64の確率でmとE （ k 、 m ）で同等です。 したがって、衝突を構築するために約2 ^64の開始点を生成する必要があります。 これの複雑さは約2 ⁶⁴です。 置換テーブルには256 x 256の入出力の差分テーブルのみを保存する必要があるため、メモリ要件は2 ¹⁶バイトのみです。

3.4。 5.5ラウンド圧縮機能GOST Rの衝突検出

高度な交換技術[7]を使用して、内部フェーズに1ラウンドを追加することで、4.5ラウンドの結果を強化できます。 これにより、GOST Rの5.5ラウンドの圧縮機能が攻撃されます。この攻撃の外部フェーズは、4.5ラウンドの攻撃と同じであり、アクティブなSボックスの新しいシーケンスは次のとおりです。







図 3. 5.5ラウンド圧縮機能GOST Rに対する攻撃の内部フェーズ



図に示すように。 図３に示されるように、 Ｒ _４ ^Ｓの各行の値は、 Ｒ _３の対応する列のみに依存する。 つまり、 R ₃の段階で列値のペアを知っていれば、 k _4がわかっているので、対応する行R ₄ ^Sの値を計算できます^。 したがって、拡張置換として、各列R ₃と対応する行R ₄ ^Sの間の対応を考慮することができます^。 ランダムに指定された入力と出力の差を持つ拡張置換ごとに、平均で1つの実際の値が見つかると予想されます。

次に、5.5ラウンドの攻撃について詳しく説明します。

3.4.1。 内部段階

5.5ラウンドのGOST Rに対するリバウンド攻撃の内部フェーズは、次のように説明できます。

1. R ₂ ^Pの最初の列の8アクティブバイトの差から始めて、 R _3に進みます。
2. それぞれの独立した拡張置換について、その入力の違いを知って、入力値の2 ⁶⁴ペアすべてを処理し、前方置換を計算します。 これにより、出力差の2 ^64個の値が得られます。 得られた各差について、それにつながる入力値の対応するペアを保存します。 このフェーズには、約2 ^64の操作とメモリが必要です。
3. R ₄ ^Lの 8バイトの差ごとに、 R ₄ ^Sに戻ります^。 必要な違いがあるかどうか、以前に保存した値をすべてチェックします。

R ₂ ^Pステージで他の差異を選択して、差異を満たすより多くの実際の値を取得できます。 R ₂ ^Pの入力の差については、約2 ^64の開始点が見つかると予想されます。

3.4.2。 外相

外部フェーズは4.5ラウンド攻撃と同じで、2 ^64の開始ポイントが必要です。 したがって、5.5ラウンドの衝突を検索するための複雑さとメモリ要件は^それぞれ 2 ⁶⁴です。

3.5。 7.5ラウンド圧縮関数GOST Rの衝突検出

[6]のように、キー拡張スキームの自由度を使用して内部ラウンドに3ラウンドを追加することにより、4.5ラウンドの結果を改善できます。 主なアイデアは、内部フェーズを2つのサブフェーズに分離することです。 これらの2つのサブフェーズは、キー拡張手順の自由度を最大限に活用することで、後で組み合わせることができます。 その結果、7.5ラウンドに切り捨てられたGOST R圧縮関数の衝突が発生します。

拡張内部フェーズでは、次のアクティブバイトのシーケンスを使用します。



次に、内部経路は、差動経路に対応する入力値を見つけるために2つのサブフェーズに分割されます（図4）。 最初のサブフェーズでは、ラウンド1-2および4-5の一致を検索します。 そして、2番目のサブフェーズでは、ラウンドキーの値を選択して自由度を使用し、 r ₂とr _4の間のアクティブ状態の値を組み合わせます。





図 4. 7.5ラウンド圧縮関数GOST Rの衝突検索の内部フェーズ

3.5.1。 内部サブフェーズ1

このサブフェーズでは、ラウンド1-2および4-5の一致検索を実行します。これは次のように説明できます。

1.ラウンド1-2：

• R _3の最初の列の8バイトの差から開始し、 R ₂ ^Sと反対方向に移動します^。
• 最初の列R ₁ ^Pの8バイトの差ごとに、 R _2に進みます。 R ₁ ^Pの差には2 ^64個の異なる値しかないため、 R _2には 2 ^64個の差を得ることができます。 マッチング後、差分データは約2 ^64の実際の値になります。 ただし、各行に対して個別に一致する検索を実行し、行に対して2 ^8個の有効な値を取得できます。 したがって、差分パスに対応する2 ^64個の実数値を生成する複雑さは、2 ⁸回のラウンド変換のみです。

2.ラウンド4-5：ラウンド1-2と同じことを行います。

現在、約2 ⁹回のラウンド変換という面倒な攻撃の最初のサブフェーズを実行した後、 R ₂ ^SとR _5の候補が2 ^64個あります。

3.5.2。 内部サブフェーズ2

2番目のサブフェーズでは、キー拡張スキームの自由度を使用して、 R ₂ ^Sの違いとR ₅の違い、および実際の値を結合する必要があります。 これは、次の方程式を解かなければならないことを意味します。



で



R ₂ ^Sの 2 ^64個の候補とR _5の 2 ^64個の候補について、 k ₃ 、 k ₄ 、およびk ₅の値の512自由度を考慮して、2 ^64個の解が見つかると予想されます。 LP （ R ₂ ^S ）= R ₂ ^Lおよび（ X [ k ₅ ]） ^-1 = X [ k ₅ ]なので、次のように（8）を書き換えることができます。



PとSの順序はいつでも変更できるため、



次の方程式が得られます。



表記を紹介します およびT = P ^-1 L ^-1 （ R ₅ ）の場合、上記の式は次のように書き換えることができます。



この方程式の解は、 R ₂ ^SとR ₅の差と値を組み合わせることと同等です。 方程式を解くために使用する方法を以下に説明します。





図 5. 7.5ラウンド圧縮機能GOST Rの衝突を見つけるための内部サブフェーズ2攻撃



R ₂ ^LとR ₄ ^Sの差はサブフェーズ1内で固定されるため、 R ₂ ^*とTの差も固定されます。 また、サブフェーズ1で生成された状態R ₂ ^SおよびR _5の 2 ⁶⁴値は、それぞれR ₂ ^*およびTの 2 ⁶⁴値に直接つながります。 これで、図15に示すように、各行について個別に（15）を解くことができます。 5、次のように説明できます。

1. R ₂ ^SからR ₂ ^*の8バイトの差と2 ⁶⁴値を計算し、 R ₅からTの8バイトの差と対応する2 ⁶⁴値を計算します。 方程式を1行ずつ解くことができるため、 R ₂ ^*とTの値の文字列を計算して保存するだけです。このステップの複雑さとメモリ要件は、2 ⁶⁵ではなく2 ⁹です。2. 最初の行R ₃ ^*の 2 ^64個の値すべてについて、次の手順^を繰り返します。

• R ₃ ^*の差^は既知であるため、最初の行R ₃ ^*の選択された値について、順方向に最初の行R ₃ ^Lの値と最初の行R _4の差を計算します。
• R ₄ R ₄ ^S R ₄ . R ₃ ^L , k ₄ .
• k ₃ ^* , R ₂ ^* , R ₄ ^S T . R ₂ ^* , R ₄ ^S 2 ⁶⁴ , . , , .

3.このステップでは、前のステップで取得した対応するR ₂ ^*とTの 2〜8行目の値を組み合わせます。行ごとに、キーk ₃ ^*の対応する行の2 ^64個の値すべてに対して個別に徹底的な検索が実行されます。 64ビット値を接続し、2 ^64個のキー値をチェックすることにより、常に解決策を見つけることができることに注意してください。すべてのこれらのステップの後、我々は2つのを得る⁶⁴のリンク、対応する値をR ₂ ^*及びTを。つまり、2 ⁶⁴

外部フェーズの開始点。複雑さは約2 ¹²⁸ 2についてのメモリ要件を持つラウンドの変換の¹⁶バイト。平均して、2 ^64の複雑さを持つ出発点を見つけることが期待されます。サイズ2 ^128のルックアップテーブルを適用することで、ステップ3をスキップできます。ルックアップテーブルを使用すると、平均複雑度1の開始点を見つけることができます。ただし、ルックアップテーブルの構築の複雑さは^2,128であり、メモリ要件は^2,128バイトです。R ₃には2 ^64の違いがあり、R ₄ ^Sには2 ^64の違いがあることに注意してください。 。R ₃とR ₄ ^Sの差の固定ペアについては、2 ^64の開始点が見つかると予想されます。したがって、合計で、外部フェーズの開始点を生成する必要があるのは2 ¹⁹²以下です。

3.5.3。外相

7.5ラウンド攻撃の外部フェーズは、4.5ラウンド攻撃に似ています。7.5ラウンドで衝突を検索する攻撃は、次のアクティブバイトのシーケンスを使用します：



GOST Rの圧縮機能の7.5ラウンドの衝突を検索する複雑さは、2 ¹⁶バイトのメモリ要件で約2 ^{64 + 64} = 2 ¹²⁸です。

3.6。 9.5ラウンド圧縮機能GOST Rの衝突検出

2 ^192を超える開始点を取得できますが、7.5ラウンド攻撃の外部フェーズに必要なのは2 ⁶⁴だけです。9.5ラウンドの衝突を見つける攻撃を構築するために、最初に1ラウンド、最後に1ラウンドを追加することにより、外部フェーズを拡張できます。このような攻撃は、次の一連のアクティブバイトを使用します。



次に、9.5ラウンド攻撃の外部フェーズについて詳しく説明します。





図 6. 9.5ラウンドの圧縮関数GOST Rに対する攻撃の概略図

3.6.1。外相

7.5ラウンドの外部攻撃フェーズとは異なり、ここでは切り捨てられた差分を使用します。内部フェーズの実行後、生成された値により、図_3に示すように、R ₃とR _8に8バイトの差が生じます。 6.両方向で切り捨てられた差動経路8→1への対応を見つけたい。この切り捨てられた差分パスの確率は2 ^-56です。R ₂とR ₉の1バイトの違いにより、R ₁とR _10のアクティブバイトは常に8バイトになります。したがって、外部フェーズの確率は2 ^-112です。したがって、2で生成する必要があります¹¹²倍の出発点。

9.5ラウンドに切り捨てられた圧縮関数の衝突では、mとR ₁₀ ^Pに同じ差が必要なので、合計2 ^{112 + 64} = 2 ^176の開始点を生成する必要があります。セクション3.5で説明したように、労働投入量が2 ⁶⁴である出発点を1つ見つけることが期待されます。したがって、9.5ラウンドの衝突を検出する複雑さは約2 ^{64 + 176} = 2 ²⁴⁰であり、メモリ要件は2 ¹⁶バイトです。^2,128個の値を持つルックアップテーブルを使用する場合、複雑度は^2,176です2 ¹²⁸バイトのメモリ要件。

4. 10ラウンドの弁別器

この章では、10ラウンドに切り捨てられたGOST R圧縮関数の識別器を示します。

。次のように提案されたギルバートら[7]種類判別を説明することができる：行うランダム関数のためにBのビット順列マッピング入力部分空間のサイズ差Iを部分空間の大きさの出力差にJのみ{maxの必要、2 ^bは / （IJ）}関数呼び出しは、（一般性を失うことなく、我々は仮定するI ≤ J）。

適用することによってLとX [ K ₁₁] 9.5ラウンドの前の結果に、差動経路を10ラウンドに拡張します。にもかかわらず、R _11は、切り捨て差の点で完全に活性であり、差R _11は、依然として2の部分空間サイズに属する入力差分圧縮機能のでせいぜい64の部分空間の次元にある⁶⁴、部分空間サイズ2の出力差嘘¹²⁸。ランダム関数の場合、この種の入力と出力の差の対応を完全に決定するには、2 ^{512-（64 + 128）} = 2 ^320の計算が必要です。ただし、10ラウンドに切り捨てられた圧縮関数の場合、複雑さはわずか^2,176ですメモリ要件2 ¹⁶または2 ^128のメモリ要件2 ¹²⁸。圧縮関数に必要な複雑さは、ランダム関数の場合よりもはるかに少ないです。このプロパティを使用して、GOST Rの圧縮関数とランダム関数を区別できます。

5. GOST Rハッシュ関数の多重衝突

ここで、GOST Rハッシュ関数の構造的安定性について検討し、このタイプの構造について、k-衝突を構築する方法を提案します。この場合の複雑さは、理想的な構造のk-衝突を構築する複雑さよりも大幅に小さくなります。つまり、このタイプの構造は理想的ではないことを証明しています。nビットの出力値を

持つ理想的なハッシュ関数の場合、衝突を与えるペアの検索の複雑さは約2 ^{n / 2}であり、k-衝突（マルチコリジョン）の検索では2 ^{n（k -1）/ kです。}。しかし、ペアワイズ衝突に基づいて、Zhua on Crypto'04 [12]は、t x 2 ^{n / 2}のみの複雑さを持つ反復構造に対して2 ^t-衝突を構築する方法を提案しました。図に示すように。図7に示すように、攻撃者は最初にt個の異なるペアワイズ衝突{（B ₁、B ₁ ^*）、（B ₂、B ₂ ^*）、...、（B _t、B _t ^*）}を生成します。その後、攻撃者は、直ちに2受信することができる^T -kolliziyuタイプ（B ₁、Bを ₂、...、b _t）、ここでb _iは2つのブロックB _iおよびB _i ^{*のいずれか}です。





図 7. ジョイスの^t衝突の スキーム2 。2 ^tメッセージの形式は（ b ₁、 b ₂、...、 b _t）です。ここで、 b _iは2つのブロック B _iおよび B _iの 1つです^*



GOST R構造は反復的ではないという事実にもかかわらず、そのために構築することもできますk衝突。この方法は、次の要素で構成されています

。1.図に示すように 8、h _tの同じ値につながる2 ^tメッセージを生成します。

• してみましょうH _0が初期値であるIVアルゴリズムGOST R
• i 1 t :
  
  
  • B _i B _i ^* , g _N ( h _{i -1} , B _i ) = g _N ( h _{i -1} , B _i *), B _i B _i ^* 0 ²⁵⁶ || {0, 1} ²⁵⁶ . 2 ²⁵⁶ , [13].
  • 結果の2 ^tメッセージを（b ₁、...、b _t）の形式でコンパイルします。ここで、b _iは、B _iまたはB _i ^*の2つのブロックのいずれかです。
  
  
  

2. 手順1で生成された2 ^tのメッセージの中から、inでk個の衝突を見つけようとし、結果としてk個のメッセージを取得します。すべての2 ^tメッセージは同じ値Nを持ち、これらのkメッセージは常にGOST Rハッシュ関数のk-衝突につながることに注意してください。





図 8. GOST Rのk衝突 の構築の概略図



ステップ1のすべてのメッセージブロックは0 ²⁵⁶ || という形式を持っているため {0、1} ²⁵⁶および∑ = b ₁ b ₂ ... B _トン、Σ上位ビットにはより多くのログよりも₂ トン + 256ステップ2が必要とする理想的なモデルの構築物への訪問者k個の衝突以下の不平等を遵守し、これに必要とΣ、



上記の不平等を解決するには、我々は持っている：

176≤ T ≤2 ^256ん

そして



換言すれば、Tは 176≤ポスト-blochnogo T ≤2 ^256は、私たちが見つけることができるKのみ行うことにより-kolliziyuハッシュ関数GOST Rを計算します。この複雑さは、理想的な構造のハッシュ関数のk-衝突を見つけることの複雑さよりもはるかに小さいです。

6.結論

このホワイトペーパーでは、GOST Rの暗号解析結果を示しました。最初に、リバウンド攻撃技術を使用した4.5ラウンドのGOST R圧縮機能に対する攻撃について説明しました。さらに、この結果は、高度な交換技術を使用して5.5ラウンドに強化されました。次に、7.5ラウンドと9.5ラウンドの攻撃を達成するために、キー拡張スキームの自由度が使用されました。さらに、9.5ラウンドの攻撃の結果を使用して、GOST R圧縮関数の10ラウンド識別器を提示し、作業の最後に、GOST Rハッシュ関数のk-衝突を構築する方法を提示しました。。

文学

1. X. Wang、H。Yu、MD5およびその他のハッシュ関数を破る方法、暗号化の進歩– EUROCRYPT 2005、Springer、2005、pp。19–35。
2. X. Wang, YL Yin, H. Yu, Finding Collisions in the Full SHA-1, in: Advances in Cryptology–CRYPTO 2005, Springer, 2005, pp. 17–36.
3. V. Dolmatov, Gost R 34.11-94: Hash function algorithm.
4. P. Barreto, V. Rijmen, The Whirlpool Hashing Function, in: First open NESSIE Workshop, Leuven, Belgium, Vol. 13, 2000, p. 14。
5. F. Mendel, C. Rechberger, M. Schläffer, SS Thomsen, The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grøstl, in: Fast Software Encryption, Springer, 2009, pp. 260–276.
6. M. Lamberger, F. Mendel, C. Rechberger, V. Rijmen, M. Schläffer, Rebound Distinguishers: Results on the Full Whirlpool Compression Function, in: Advances in Cryptology–ASIACRYPT 2009, Springer, 2009, pp. 126–143.
7. H. Gilbert, T. Peyrin, Super-sbox Cryptanalysis: Improved Attacks for AES-like Permutations, in: Fast Software Encryption, Springer, 2010, pp. 365–383.
8. O. Dunkelman, N. Keller, A. Shamir, Improved Single-Key Attacks on 8-Round AES-192 and AES-256, in: Advances in Cryptology-ASIACRYPT 2010, Springer, 2010, pp. 158–176.
9. F. Mendel, T. Peyrin, C. Rechberger, M. Schläffer, Improved Cryptanalysis of the Reduced Grøstl Compression Function, Echo Permutation and AES Block Cipher, in: Selected Areas in Cryptography, Springer, 2009, pp. 16–35.
10. D. Khovratovich, I. Nikolić, C. Rechberger, Rotational Rebound Attacks on Reduced Skein, in: Advances in Cryptology-ASIACRYPT 2010, Springer, 2010, pp. 1–19.
11. A. Duc, J. Guo, T. Peyrin, L. Wei, Unaligned Rebound Attack: Application to Keccak, in: Fast Software Encryption, Springer, 2012, pp. 402–421.
12. A. Joux, Multicollisions in Iterated Hash Functions: Application to Cascaded Constructions, in: Advances in Cryptology–CRYPTO 2004, Springer, 2004, pp. 306–316.
13. D.ワグナー、一般化された誕生日の問題、：暗号学の進歩– CRYPTO 2002、Springer、2002、pp。288-304。