GOST（ハッシュ関数）

Russian cryptographic hash function

GOST R 34.11-94

一般的な
デザイナー	FAPSIとVNIIstandart（ソ連）
初版	1994年5月23日（機密解除）
由来	GOSTブロック暗号
後継者	ストリーボグ
認証	GOST規格
詳細
ダイジェストサイズ	256ビット
ラウンド	32
最高の公開暗号解読
2008年の攻撃により、フルラウンドハッシュ関数が破られました。この論文では、衝突攻撃を2 105 倍の時間で、原像攻撃を2 192倍の時間で実行できることが示されています。[1]

GOSTハッシュ関数は、 GOST R 34.11-94およびGOST 34.311-95規格で定義されている256ビットの暗号ハッシュ関数です。これは、ロシアの国家規格GOST R 34.11-94 「情報技術 - 暗号情報セキュリティ - ハッシュ関数」で最初に定義されました。CIS加盟国で使用されている同等の規格はGOST 34.311-95です。

この関数は、 GOST R 34.11-2012規格の新しい改訂版で定義されている別のStreebogハッシュ関数と混同しないでください。^[2]

GOST ハッシュ関数は、GOST ブロック暗号に基づいています。

アルゴリズム

GOSTは可変長メッセージを256ビットの固定長出力に変換します。入力メッセージは256ビットブロック（8つの32ビット・リトルエンディアン整数）に分割され、メッセージの長さが256ビットになるまで、必要な数のゼロが付加されます。残りのビットは、それまでにハッシュされたすべてのブロックの256ビット整数の算術和と、元のメッセージの長さ（ビット単位）を表す256ビット整数で埋められます。

基本表記

アルゴリズムの説明では次の表記法を使用します。

• ${\displaystyle {\mathcal {f}}0{\mathcal {g}}^{j}}$— ゼロで埋められた j ビット ブロック。
• ${\displaystyle {\mathcal {j}}M{\mathcal {j}}}$^{— 2256}を法としたビット単位のMブロックの長さ。
• ${\displaystyle {\mathcal {k}}}$— 2 つのブロックの連結。
• ${\displaystyle +}$^{— 2 256}を法とした 2 つのブロックの算術和。
• ${\displaystyle \oplus }$— 2 つのブロックの論理 XOR。

さらに、下位ビットはブロックの左側に配置され、上位ビットは右側にあるとみなします。

説明

入力メッセージは256ビットのブロックに分割されます。最後のブロックのビット数が256ビット未満の場合、必要な長さになるように先頭に0ビットが追加されます。 ${\displaystyle M}$ ${\displaystyle m_{n},\,m_{n-1},\,m_{n-2},\,\ldots ,\,m_{1}}$ ${\displaystyle m_{n}}$

各ブロックはステップハッシュ関数によって処理されます。ここで、、、は256 ビットのブロックです。 ${\displaystyle H_{\text{out}}=f(H_{\text{in}},\,m)}$ ${\displaystyle H_{\text{out}}}$ ${\displaystyle H_{\text{in}}}$ ${\displaystyle m}$

各メッセージブロックは、最初のブロックからステップハッシュ関数によって処理され、中間ハッシュ値が計算されます。 ${\displaystyle f}$

${\displaystyle \!H_{i+1}=f(H_{i},\,m_{i})}$

値は任意に選択でき、通常は です。 ${\displaystyle H_{1}}$ ${\displaystyle 0^{256}}$

計算後、最終的なハッシュ値は次のように得られる。 ${\displaystyle H_{n+1}}$

• ${\displaystyle H_{n+2}=f(H_{n+1},\,L)}$ここで、LはメッセージMの長さをビット単位で表したもので、 ${\displaystyle 2^{256}}$
• ${\displaystyle h=f(H_{n+2},\,K)}$ここで、K — は M の 256 ビット制御和です。 ${\displaystyle m_{1}+m_{2}+m_{3}+\ldots +m_{n}}$

はメッセージ M のハッシュ関数の目的の値です。 ${\displaystyle h}$

したがって、アルゴリズムは次のように機能します。

1. 初期化:
   1. ${\displaystyle h:={\text{initial}}}$— ユーザーが決定するハッシュ関数の初期 256 ビット値。
   2. ${\displaystyle \Sigma :=0}$— コントロール合計
   3. ${\displaystyle L:=0}$— メッセージの長さ
2. 内部反復の圧縮関数：i = 1 … n — 1 の場合、次の操作を実行します（while ）。 ${\displaystyle |M|>256}$
   1. ${\displaystyle h:=f(h,\,m_{i})}$ – ステップハッシュ関数を適用する
   2. ${\displaystyle L:=L+256}$ – メッセージの長さを再計算する
   3. ${\displaystyle \Sigma :=\Sigma +m_{i}}$ – 制御合計を計算する
3. 最終反復の圧縮関数:
   1. ${\displaystyle L:=L+{\mathcal {j}}\,m_{n}\,{\mathcal {j}}}$ – 完全なメッセージの長さをビット単位で計算する
   2. ${\displaystyle m_{n}:={0}^{256-{\mathcal {j}}m_{n}{\mathcal {j}}}{\mathcal {k}}m_{n}}$– 最後のメッセージをゼロで埋める
   3. ${\displaystyle \Sigma :=\Sigma +m_{n}}$ – 更新制御合計
   4. ${\displaystyle h:=f(h,\,m_{n})}$ – 最後のメッセージブロックを処理する
   5. ${\displaystyle h:=f(h,\,L)}$ – MD – メッセージ長をハッシュすることで強化
   6. ${\displaystyle h:=f(h,\,\Sigma )}$– ハッシュ制御合計
4. 出力値は です。 ${\displaystyle h}$

ステップハッシュ関数

ステップ ハッシュ関数は、2 つの 256 ビット ブロックを 1 つにマッピングします。 ${\displaystyle f}$ ${\displaystyle H_{\text{out}}=f(H_{\text{in}},\,m)}$

それは3つの部分から構成されます:

• キーの生成 ${\displaystyle K_{1},\,K_{2},\,K_{3},\,K_{4}}$
• 鍵を使った暗号化変換 ${\displaystyle H_{\text{in}}}$ ${\displaystyle K_{1},\,K_{2},\,K_{3},\,K_{4}}$
• シャッフル変換

鍵生成

キー生成アルゴリズムでは以下を使用します。

• 256 ビット ブロックの 2 つの変換:
  • 変換、ここではYの 64 ビットのサブブロックです。 ${\displaystyle A(Y)=A(y_{4}\ {\mathcal {k}}\ y_{3}\ {\mathcal {k}}\ y_{2}\ {\mathcal {k}}\ y_{1})=(y_{1}\oplus y_{2})\ {\mathcal {k}}\ y_{4}\ {\mathcal {k}}\ y_{3}\ {\mathcal {k}}\ y_{2}}$ ${\displaystyle y_{1},\,y_{2},\,y_{3},\,y_{4}}$
  • 変換、ここで、 、 はYの 8 ビットのサブブロックです。 ${\displaystyle P(Y)=P(y_{32}{\mathcal {k}}y_{31}{\mathcal {k}}\dots {\mathcal {k}}y_{1})=y_{\varphi (32)}{\mathcal {k}}y_{\varphi (31)}{\mathcal {k}}\dots {\mathcal {k}}y_{\varphi (1)}}$ ${\displaystyle \varphi (i+1+4(k-1))=8i+k,\quad i=0,\,\dots ,\,3,\quad k=1,\,\dots ,\,8}$ ${\displaystyle y_{32},\,y_{31},\,\dots ,\,y_{1}}$
• 3つの定数:
  • C ₂ = 0
  • C ₃ = 0xff00ffff000000ffff0000ff00ffff0000ff00ffff00ff00ff00ff00ff00ff00
  • C ₄ = 0

アルゴリズム:

1. ${\displaystyle U:=H_{\text{in}},\quad V:=m,\quad W:=U\ \oplus \ V,\quad K_{1}=P(W)}$
2. j = 2、3、4の場合、次の操作を実行します。

   ${\displaystyle U:=A(U)\oplus C_{j},\quad V:=A(A(V)),\quad W:=U\oplus V,\quad K_{j}=P(W)}$

暗号化変換

鍵生成後、GOST 28147-89を用いて、鍵 の単純置換モードでの暗号化が行われます。暗号化変換を E （256ビット鍵を用いた64ビットデータの暗号化）と表記します。暗号化では、 は4つの64ビットブロック に分割され、各ブロックは次のように暗号化されます。 ${\displaystyle H_{\text{in}}}$ ${\displaystyle K_{1},\,K_{2},\,K_{3},\,K_{4}}$ ${\displaystyle H_{\text{in}}}$ ${\displaystyle H_{\text{in}}=h_{4}{\mathcal {k}}h_{3}{\mathcal {k}}h_{2}{\mathcal {k}}h_{1}}$

• ${\displaystyle s_{1}=E(h_{1},\,K_{1})}$
• ${\displaystyle s_{2}=E(h_{2},\,K_{2})}$
• ${\displaystyle s_{3}=E(h_{3},\,K_{3})}$
• ${\displaystyle s_{4}=E(h_{4},\,K_{4})}$

この後、結果ブロックは 1 つの 256 ビット ブロックに連結されます。 ${\displaystyle S=s_{4}{\mathcal {k}}s_{3}{\mathcal {k}}s_{2}{\mathcal {k}}s_{1}}$

シャッフル変換

最後のステップでは、線形フィードバックシフトレジスタを用いて、 、 S 、 mにシャッフル変換を適用します。その結果、中間ハッシュ値が得られます。 ${\displaystyle H_{\text{in}}}$ ${\displaystyle H_{\text{out}}}$

まず、 256 ビット ブロックでLFSRを実行する ψ 関数を定義します。

${\displaystyle \psi (Y)=\psi (y_{16}{\mathcal {k}}y_{15}{\mathcal {k}}\ldots {\mathcal {k}}y_{2}{\mathcal {k}}y_{1})=(y_{1}\oplus y_{2}\oplus y_{3}\oplus y_{4}\oplus y_{13}\oplus y_{16}){\mathcal {k}}y_{16}{\mathcal {k}}y_{15}{\mathcal {k}}\ldots {\mathcal {k}}y_{3}{\mathcal {k}}y_{2}}$、

ここで、 Yの 16 ビットのサブブロックです。 ${\displaystyle y_{16},y_{15},\ldots ,y_{2},y_{1}}$

シャッフル変換は であり、 は関数の i 乗を表します。 ${\displaystyle H_{\text{out}}=\psi ^{61}{\mathord {\left(H_{\text{in}}\oplus \psi \left(m\oplus \psi ^{12}(S)\right)\right)}}}$ ${\displaystyle \psi ^{i}}$ ${\displaystyle \psi }$

初期値

GOST R 34.11 94には一般的に使用される初期パラメータのセットが2つあります。両方のセットの開始ベクトルは

${\displaystyle H_{1}}$= 0x00000000 00000000 00000000 00000000 00000000 00000000 00000000 .

GOST R 34.11 94規格自体は暗号化変換のアルゴリズム初期値とSボックスを指定していないが、サンプルセクションで以下の「テストパラメータ」を使用している。^[3] ${\displaystyle H_{1}}$ ${\displaystyle E}$

「テストパラメータ」Sボックス

RFC 5831 ではこれらのパラメータのみが指定されていますが、RFC 4357 ではこれらを「テスト パラメータ」と名付けており、本番アプリケーションでの使用は推奨されていません。

Sボックス番号	価値
1	4	10	9	2	13	8	0	14	6	11	1	12	7	15	5	3
2	14	11	4	12	6	13	15	10	2	3	8	1	0	7	5	9
3	5	8	1	13	10	3	4	2	14	15	12	7	6	0	9	11
4	7	13	10	1	0	8	9	15	14	4	6	12	11	2	5	3
5	6	12	7	1	5	15	13	8	4	10	9	14	0	3	11	2
6	4	11	10	0	7	2	1	13	3	6	8	5	9	12	15	14
7	13	11	4	1	3	15	5	9	0	10	14	7	6	8	2	12
8	1	15	13	0	5	7	10	4	9	2	3	14	6	11	8	12

CryptoPro Sボックス

CryptoPro S-box は、CryptoPro 社によって開発された「製品対応」パラメータ セットから来ており、RFC 4357 のセクション 11.2 の一部としても指定されています。

Sボックス番号	価値
1	10	4	5	6	8	1	3	7	13	12	14	0	9	2	11	15
2	5	15	4	0	2	13	11	9	1	7	6	3	12	14	10	8
3	7	15	12	14	9	4	1	0	3	11	5	2	6	10	8	13
4	4	10	7	12	0	15	2	8	14	1	6	5	13	11	9	3
5	7	6	4	11	9	12	2	10	1	8	0	14	15	13	3	5
6	7	6	2	4	13	9	15	0	10	1	5	11	8	14	12	3
7	13	14	4	1	7	0	5	10	3	12	8	15	6	2	9	11
8	1	3	10	9	5	11	4	15	8	6	7	14	13	0	2	12

暗号解読

2008年、GOSTハッシュ関数をフルラウンドで破る攻撃が公開されました。この論文では、衝突攻撃を2 ¹⁰⁵回で、第一および第二原像攻撃を2 ¹⁹²回で実行できることが示されています（2 ⁿ回は、攻撃においてアルゴリズムが計算されたおおよその回数です）。^[1]

GOSTハッシュテストベクトル

「テストパラメータ」のハッシュ

256 ビット (32 バイト) の GOST ハッシュは、通常、64 桁の 16 進数として表されます。

ここに「テストパラメータ」を含むGOSTハッシュのテストベクトルがあります。

GOST("素早い茶色のキツネは怠け者の犬を飛び越える") = 77b7fa410c9ac58a25f49bca7d0468c9296529315eaca76bd1a10f376d1f4294

メッセージに小さな変更を加えるだけでも、雪崩効果により、圧倒的な確率でハッシュは全く異なるものになります。例えば、dをcに変更すると、次のようになります。

GOST("素早い茶色のキツネは怠け者の歯車を飛び越える") = a3ebc4daaab78b0be131dab5737a7f67e602670d543521319150d2e14eeec445

GOST R 34.11-94規格からの2つのサンプル: ^[3]

GOST("これはメッセージです、長さ=32バイト") = b1c466d37519b82e8319819ff32595e047a28cb6f83eff1c6916a815a637fffaGOST("元のメッセージの長さが50バイトであると仮定") = 471aba57a60a770d3a76130635c1fbea4ef14de51f78b4ae57dd893b62f55208

その他のテストベクトル:

GOST("") = ce85b99cc46752fffee35cab9a7b0278abb4c2d2055cff685af4912c49490f8dGOST("a") = d42c539e367c66e9c88a801f6649349c21871b4344c6a573f849fdce62f314ddGOST("メッセージダイジェスト") = ad4434ecb18f2c99b60cbe59ec3d2469582b65273f48de72db2fde16a4889a4dGOST( 128文字の「U」 ) = 53a3a3ed25180cef0c1d85a074273e551c25660a87062a52d926a9e8fe5733a4GOST( 1000000文字の「a」 ) = 5c00ccc2734cdd3332d3d4749576e3c1a7dbaf0e7ea74e9fa602413c90a129fa

CryptoProパラメータのハッシュ

CryptoPro S-box を使用した GOST アルゴリズムは、異なるハッシュ値のセットを生成します。

GOST("") = 981e5f3ca30c841487830f84fb433e13ac1101569b9c13584ac483234cd656c0GOST("a") = e74c52dd282183bf37af0079c9f78055715a103f17e3133ceff1aacf2f403011GOST("abc") = b285056dbf18d7392d7677369524dd14747459ed8143997e163b2986f92fd42cGOST("メッセージダイジェスト") = bc6041dd2aa401ebfa6e9886734174febdb4729aa972d60f549ac39b29721ba0GOST("素早い茶色のキツネは怠け者の犬を飛び越える") = 9004294a361a508c586fe53d1f1b02746765e71b765472786e4770d565830a76GOST("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = 73b70a39497de53a6e08c67b6d4db853540f03e9389299d9b0156ef7e85d0f61GOST("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = 6bc7b38989b28cf93ae8842bf9d752905910a7528a61e5bce0782de43e610c90GOST("これはメッセージです、長さ=32バイト") = 2cefc2f7b7bdc514e18ea57fa74ff357e7fa17d652c75f69cb1be7893ede48ebGOST("元のメッセージの長さが50バイトであると仮定") = c3730c5cbccacf915ac292676f21e8bd4ef75331d9405e5f1a61dc3130a65011GOST(「U」の128) = 1c4ac7614691bbf427fa2316216be8f10d92edfd37cd1027514c1008f649c4e8GOST(1000000 の "a") = 8693287aa62f9478f7cb312ec0866b6c4e4a0f11160441e8f4ffcd2715dd554f

参照

• クピナ
• ハッシュ関数のセキュリティ概要
• GOST規格
• ハッシュ関数のリスト

さらに読む

• RFC 5830 – 「GOST 28147-89: 暗号化、復号化、およびメッセージ認証コード（MAC）アルゴリズム」^[4] 情報。
• 「情報技術。暗号化データセキュリティ。ハッシュ関数」。2010年2月20日。GOST R 34.11-94 規格の全文 (ロシア語)。

参考文献

1. Mendel, Florian; Pramstaller, Norbert; Rechberger, Christian; Kontak, Marcin; Szmidt, Janusz (2008). 「GOSTハッシュ関数の暗号解析」. Wagner, David (編). Advances in Cryptology – CRYPTO 2008 . Lecture Notes in Computer Science. Vol. 5157.ドイツ: Springer Berlin Heidelberg . pp.  162– 178. doi :10.1007/978-3-540-85174-5_10. ISBN 978-3-540-85173-8。
2. GOST R 34.11-2012: ストリーボグハッシュ関数
3. 「GOST R 34.11-94規格。情報技術。暗号化データセキュリティ。ハッシュ関数。追加A。」1994年。
4. V. Dolmatov編（2010年3月）. GOST 28147-89: 暗号化、復号化、およびメッセージ認証コード（MAC）アルゴリズム. 独立提出. doi : 10.17487/RFC5830 . ISSN  2070-1721. RFC 5830. 情報提供。RFC 8891 により更新されました。

外部リンク

• Markku-Juhani SaarinenによるGOSTハッシュ関数のC実装とテストベクトル。GOST 28147-89およびGOST R 34.11-94規格の英語への翻訳草稿も含まれています。バグ修正版については[1]を参照してください。
• STL ストリームを使用した C++ 実装^{[永久リンク切れ]}。
• RHash は、 GOST ハッシュを計算および検証できるオープンソースのコマンドライン ツールです (両方のパラメーター セットをサポート)。
• GOST R 34.11-94 の JavaScript での実装 (CryptoPro パラメータ)
• GOSTハッシュ関数Ecryptページ
• オンラインGOST計算機 2014年11月6日アーカイブWayback Machine

Retrieved from "https://en.wikipedia.org/w/index.php?title=GOST_(hash_function)&oldid=1313100352"