GOST (ハッシュ関数)

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}}}$^{— 2 256}を法としたビット単位の M ブロックの長さ。
• ${\displaystyle {\mathcal {k}}}$— 2 つのブロックの連結。
• ${\displaystyle +}$^{— 2 256}を法とする 2 つのブロックの算術和。
• ${\displaystyle \oplus}$— 2 つのブロックの論理排他的論理和。

さらに、下位ビットはブロックの左側に配置され、上位ビットは右側に配置されることを考慮します。

入力メッセージは 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 つの定数:
  • 2 = 0_です
  • C ₃ = 0xff00ffff000000ffff0000ff00ffff0000ff00ffff00ff00ff00ff00ff00ff00
  • ₄ = 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}$

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

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

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

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

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

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

メッセージに小さな変更を加えただけでも、雪崩効果により、ハッシュは完全に異なる結果になる可能性が高くなります。たとえば、d をcに変更すると、次のようになります。

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

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

GOST("これはメッセージです、長さ=32バイト") =
 b1c466d37519b82e8319819ff32595e047a28cb6f83eff1c6916a815a637fffa

GOST("元のメッセージの長さが50バイトであると仮定") =
 471aba57a60a770d3a76130635c1fbea4ef14de51f78b4ae57dd893b62f55208

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

GOST("") =
 ce85b99cc46752fffee35cab9a7b0278abb4c2d2055cff685af4912c49490f8d

GOST("a") =
 d42c539e367c66e9c88a801f6649349c21871b4344c6a573f849fdce62f314dd

GOST("メッセージダイジェスト") =
 ad4434ecb18f2c99b60cbe59ec3d2469582b65273f48de72db2fde16a4889a4d

GOST( 128 文字の 'U' ) =
 53a3a3ed25180cef0c1d85a074273e551c25660a87062a52d926a9e8fe5733a4

GOST( 1000000 文字の 'a' ) =
 5c00ccc2734cdd3332d3d4749576e3c1a7dbaf0e7ea74e9fa602413c90a129fa

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

GOST("") = 981e5f3ca30c841487830f84fb433e13ac1101569b9c13584ac483234cd656c0

GOST("a") = e74c52dd282183bf37af0079c9f78055715a103f17e3133ceff1aacf2f403011

GOST("abc") = b285056dbf18d7392d7677369524dd14747459ed8143997e163b2986f92fd42c

GOST("メッセージダイジェスト") =
  bc6041dd2aa401ebfa6e9886734174febdb4729aa972d60f549ac39b29721ba0

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

GOST("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") =
  73b70a39497de53a6e08c67b6d4db853540f03e9389299d9b0156ef7e85d0f61

GOST("12345678901234567890123456789012345678901234567890123456789012345678901234567890") =
  6bc7b38989b28cf93ae8842bf9d752905910a7528a61e5bce0782de43e610c90

GOST("これはメッセージです、長さ=32バイト") =
  2cefc2f7b7bdc514e18ea57fa74ff357e7fa17d652c75f69cb1be7893ede48eb

GOST("元のメッセージの長さが50バイトであると仮定") =
  c3730c5cbccacf915ac292676f21e8bd4ef75331d9405e5f1a61dc3130a65011

GOST(「U」の128) = 1c4ac7614691bbf427fa2316216be8f10d92edfd37cd1027514c1008f649c4e8

GOST(1000000 の「a」) = 8693287aa62f9478f7cb312ec0866b6c4e4a0f11160441e8f4ffcd2715dd554f

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

• ドルマトフ、V. (2010 年 3 月)。ドルマトフ、V (編)。 「GOST R 34.11-94: ハッシュ関数アルゴリズム」。 IETF。土井: 10.17487/RFC5831。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です
• 「情報技術。暗号化データセキュリティ。ハッシュ関数」。2010-02-20。GOST R 34.11-94 規格の全文 (ロシア語)。

• 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-06 にWayback Machineでアーカイブされました