GOST（ブロック暗号）

GOST 28147-89 (マグマ)
	GOST の図
一般的な
デザイナー	ソ連、KGB、第8部
初版	1994-05-23 (機密解除)
後継者	GOST ハッシュ関数、クズニエチク
認証	GOST規格
暗号の詳細
キーサイズ	256ビット
ブロックサイズ	64ビット
構造	フェイステルネットワーク
ラウンド	32
最高の公開暗号解読
	2011年に数人の著者がGOSTのより重大な欠陥を発見し、初めて任意の鍵で32ラウンドのGOST全体を攻撃することができた。ニコラ・クルトワはこれを「重大な欠陥のある暗号」とさえ呼んだ。

GOSTブロック暗号( Magma ) は、標準GOST 28147-89 (RFC 5830) で定義され、ブロックサイズが 64 ビットのソビエトおよびロシア政府標準の対称鍵ブロック暗号です。1989 年に発行された元の標準では、この暗号に名前が付けられていませんでしたが、標準の最新の改訂版であるGOST R 34.12-2015 (RFC 7801、RFC 8891) では、この暗号を Magma と呼ぶことができると規定されています。^[2] GOSTハッシュ関数はこの暗号に基づいています。新しい標準では、 Kuznyechikと呼ばれる新しい 128 ビットブロック暗号も規定されています。

1970年代に開発されたこの規格は「最高機密」とされ、1990年に「機密」に格下げされました。ソ連崩壊後まもなく機密解除され、1994年に一般に公開されました。GOST 28147は、米国の標準アルゴリズムであるDESのソ連版でした。^[3]そのため、この2つは構造が非常に似ています。

アルゴリズム

GOST のブロックサイズは 64 ビット、鍵長は 256 ビットです。Sボックスは秘密にすることができ、約 354 (log ₂ (16! ^{8 )) ビットの秘密情報が含まれているため、有効な鍵サイズは 610 ビットまで増やすことができます。ただし、選択鍵攻撃により、約 2}^{32 回の}暗号化で S ボックスの内容を復元できます。^[4]

GOST は32 ラウンドのFeistel ネットワークです。そのラウンド関数は非常に単純です。32 ビットのサブキーを 2 32 で割ったものを追加し、その^結果を S ボックスのレイヤーに通して、その結果を 11 ビット左に回転させます。その結果がラウンド関数の出力です。隣の図では、1 本の線が 32 ビットを表しています。

サブキーは、事前に指定された順序で選択されます。キースケジュールは非常に単純です。256 ビットのキーを 8 つの 32 ビットのサブキーに分割し、各サブキーをアルゴリズムで 4 回使用します。最初の 24 ラウンドではキーワードを順番に使用し、最後の 8 ラウンドでは逆の順序で使用します。

S ボックスは 4 ビットの入力を受け取り、4 ビットの出力を生成します。ラウンド関数の S ボックス置換は、8 つの 4 × 4 S ボックスで構成されます。S ボックスは実装に依存するため、GOST を使用して通信を保護したい関係者は同じ S ボックスを使用する必要があります。セキュリティを強化するために、S ボックスを秘密にしておくことができます。GOST が規定された元の標準では、S ボックスは提供されていませんでしたが、何らかの方法で提供されることになりました。これにより、政府がスパイしたい組織に弱い S ボックスが与えられたという憶測が広まりました。ある GOST チップ製造業者は、疑似乱数ジェネレータを使用して S ボックスを自分で生成したと報告しました。^[5]

たとえば、ロシア連邦中央銀行は次の S ボックスを使用しました。

しかし、この規格の最新版であるGOST R 34.12-2015では、欠落していたSボックス仕様が追加され、次のように定義されています。^[2]

GOSTの暗号解読

GOST の最新の暗号解析では、理論上は安全であることが示されています。実際には、公開されている最良の攻撃のデータとメモリの複雑さは実用的なレベルに達していますが、2 ^{64 個のデータが利用可能な場合、最良の攻撃の時間複雑さでも 2}^{192 の}ままです。

2007年以来、GOSTのラウンド数を減らした実装や弱い鍵に対する攻撃がいくつか開発されている。^[6]^[7]

2011年、数人の著者がGOSTのより重大な欠陥を発見し、初めて任意の鍵で32ラウンドのGOST全体を攻撃することができた。ニコラ・クルトワはこれを「重大な欠陥のある暗号」とさえ呼んだ。^[8]初期の攻撃では、膨大なメモリを消費することで時間計算量を2 ²⁵⁶から2 ^{228に削減することができ、}^{[9]すぐに時間計算量を2}¹⁷⁸にまで削減することができた（2 ^70のメモリと2 ^64のデータ消費を犠牲にして）。^[10]^[11]

2012年12月、Courtois、Gawinecki、Songは、GOSTラウンドを2 ^{101回だけ計算することでGOSTへの攻撃を改善しました。}^[12] Isobeはすでに完全なGOST暗号に対する単一鍵攻撃を発表していましたが^[13] 、 Dinur、Dunkelman、Shamirはそれを改良し、 2 ^32のデータと2 ^{36のメモリで2}^224の時間計算量、 2 ^{64のデータで2}^192の時間計算量に達しました。^[14]

この攻撃により、予想される強度が 2 ²⁵⁶ (キーの長さ) から約 2 ^{178に減少するため、暗号は破られたとみなすことができます。ただし、実行するテストの数が 2}¹⁷⁸に達することは不可能であるため、この攻撃は実際には実行可能ではありません。

ブロックサイズがnビットのブロック暗号の場合、誕生日のパラドックス^[15]により、再鍵化を行う前に暗号化できる平文の最大量は2n ^{/2ブロックであり、前述の攻撃のいずれも}²³²未満のデータを必要としないことに注意する必要がある。

参照

GOST規格

参考文献

^ Courtois, Nicolas T. (2011 年 5 月 9 日)。「国際標準化の観点から見た GOST 28147-89 のセキュリティ評価」。Cryptology ePrint Archive。IACR。2011年まで、研究者は全員一致で GOST は非常に安全であるべきである、または安全である可能性があると同意していましたが、2010 年には次のように要約されました。「過去 20 年間にかなりの暗号解読の努力が払われてきたにもかかわらず、GOST はまだ解読されていません」。残念ながら、最近、GOST は解読可能であり、深刻な欠陥のある暗号であることが判明しました。
^ ab "GOST R 34.12-2015 (ロシア語のみ)" (PDF) 。 2015年9月24日時点のオリジナル(PDF)からアーカイブ。2015年8月28日閲覧。
^ Fleischmann, Ewan; Gorski, Michael; Hühne, Jan-Hendrik; Lucks, Stefan (2009). 「ゼロ時間とゼロメモリによるフル GOST ブロック暗号へのキー回復攻撃」。ISO /IEC JTC 1として発行。
^ Saarinen, Markku-Juhani (1998). 「GOST の秘密 S ボックスに対する選択鍵攻撃」。GOSTに対する単純な「ブラックボックス」選択鍵攻撃により、約 2^32 回の暗号化で秘密 S ボックスを復元できることを示します。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です
^ Schneier, Bruce (1996). 応用暗号学: C言語のプロトコル、アルゴリズム、ソースコード (第2版、[Nachdr.] 版). ニューヨーク [ua]: Wiley. ISBN 978-0-471-11709-4。
^ Eli Biham、Orr Dunkelman、Nathan Keller (2007)。「改良されたスライド攻撃」(PDF)。
^ Orhun Kara (2008). 「いくつかの暗号の反射暗号解析」
^ Courtois, Nicolas T. (2011 年 5 月 9 日)。「国際標準化の観点から見た GOST 28147-89 のセキュリティ評価」。Cryptology ePrint Archive。IACR。2011年まで、研究者は全員一致で GOST は非常に安全であるべきである、または安全である可能性があると同意していましたが、2010 年には次のように要約されました。「過去 20 年間にかなりの暗号解読の努力が払われてきたにもかかわらず、GOST はまだ解読されていません」。残念ながら、最近、GOST は解読可能であり、深刻な欠陥のある暗号であることが判明しました。
^ ニコラ・T・クルトワ;ミハウ・ミスタウ (2011)。「GOSTの差分暗号解析」。IACR。
^ Nicolas T. Courtois (2012). 「完全な GOST に対する改良された差分攻撃」(PDF) . IACR .
^ Courtois, Nicolas T. (2011 年 6 月 13 日)。「GOST の代数的複雑性の削減と暗号解析」( PDF)。Cryptology ePrint Archive。IACR 。
^ Nicolas T. Courtois、Jerzy A. Gawinecki、Guangyan Song (2012)。「CONTRADICTION IMMUNITY AND GUESS-THEN-DETERMINE ATTACKS ON GOST」(PDF)。Versita 。 2014年8月25日閲覧。
^ 磯部孝則 (2011)。「フル GOST ブロック暗号に対する単一キー攻撃」。高速ソフトウェア暗号化。コンピュータサイエンスの講義ノート。第 6733 巻。pp . 290–305。doi :10.1007 / 978-3-642-21702-9_17。ISBN 978-3-642-21701-2。
^ Dinur, Itai; Dunkelman, Orr; Shamir, Adi (2012). 「Full GOST に対する改良された攻撃」.高速ソフトウェア暗号化. コンピュータサイエンスの講義ノート. Vol. 7549. pp. 9–28. doi : 10.1007/978-3-642-34047-5_2 . ISBN 978-3-642-34046-8。
^ 「暗号化技術と鍵の長さの評価に関する ISO/IEC JTC 1/SC 27 常設文書 No. 12 (SD12) の草案、第 4 版」(PDF)。2016 年。

さらに読む

「WebCrypto GOST ライブラリ」。Rudolf Nickolaev、WebCrypto GOST チーム。
Dolmatov, Vasily (2010 年 3 月)。「RFC 5830: GOST 28147-89 暗号化、復号化、および MAC アルゴリズム」。IETF。
Popov, Vladimir、Leontiev, Serguei、Kurepkin, Igor (2006 年 1 月)。「RFC 4357: GOST で使用するための追加の暗号化アルゴリズム」。IETF。
Alex Biryukov & David Wagner (2000 年 5 月)。高度なスライド攻撃(PDF)。Advances in Cryptology、Proceedings of EUROCRYPT 2000。ブルージュ: Springer-Verlag。pp. 589–606。doi : 10.1007/3-540-45539-6_41。2007年 9 月 3 日に取得。

外部リンク

説明、標準のテキスト、オンライン GOST 暗号化および復号化ツール
SCANのGOSTへのエントリー
ロシアのGOST暗号化標準機能を備えたPKCS#11ソフトウェアデバイスのオープンソース実装
https://github.com/gost-engine/engine — OpenSSL 用のロシア GOST 暗号化のオープンソース実装。

[1] Courtois, Nicolas T. (2011 年 5 月 9 日)。「国際標準化の観点から見た GOST 28147-89 のセキュリティ評価」。Cryptology ePrint Archive。IACR。2011年まで、研究者は全員一致で GOST は非常に安全であるべきである、または安全である可能性があると同意していましたが、2010 年には次のように要約されました。「過去 20 年間にかなりの暗号解読の努力が払われてきたにもかかわらず、GOST はまだ解読されていません」。残念ながら、最近、GOST は解読可能であり、深刻な欠陥のある暗号であることが判明しました。

[std2015-2] "GOST R 34.12-2015 (ロシア語のみ)" (PDF) 。 2015年9月24日時点のオリジナル(PDF)からアーカイブ。2015年8月28日閲覧。

[fleischmann2009-3] Fleischmann, Ewan; Gorski, Michael; Hühne, Jan-Hendrik; Lucks, Stefan (2009). 「ゼロ時間とゼロメモリによるフル GOST ブロック暗号へのキー回復攻撃」。ISO /IEC JTC 1として発行。

[4] Saarinen, Markku-Juhani (1998). 「GOST の秘密 S ボックスに対する選択鍵攻撃」。GOSTに対する単純な「ブラックボックス」選択鍵攻撃により、約 2^32 回の暗号化で秘密 S ボックスを復元できることを示します。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です

[schneier1996-5] Schneier, Bruce (1996). 応用暗号学: C言語のプロトコル、アルゴリズム、ソースコード (第2版、[Nachdr.] 版). ニューヨーク [ua]: Wiley. ISBN 978-0-471-11709-4。

[6] Eli Biham、Orr Dunkelman、Nathan Keller (2007)。「改良されたスライド攻撃」(PDF)。

[7] Orhun Kara (2008). 「いくつかの暗号の反射暗号解析」

[8] Courtois, Nicolas T. (2011 年 5 月 9 日)。「国際標準化の観点から見た GOST 28147-89 のセキュリティ評価」。Cryptology ePrint Archive。IACR。2011年まで、研究者は全員一致で GOST は非常に安全であるべきである、または安全である可能性があると同意していましたが、2010 年には次のように要約されました。「過去 20 年間にかなりの暗号解読の努力が払われてきたにもかかわらず、GOST はまだ解読されていません」。残念ながら、最近、GOST は解読可能であり、深刻な欠陥のある暗号であることが判明しました。

[9] ニコラ・T・クルトワ;ミハウ・ミスタウ (2011)。「GOSTの差分暗号解析」。IACR。

[10] Nicolas T. Courtois (2012). 「完全な GOST に対する改良された差分攻撃」(PDF) . IACR .

[11] Courtois, Nicolas T. (2011 年 6 月 13 日)。「GOST の代数的複雑性の削減と暗号解析」( PDF)。Cryptology ePrint Archive。IACR 。

[12] Nicolas T. Courtois、Jerzy A. Gawinecki、Guangyan Song (2012)。「CONTRADICTION IMMUNITY AND GUESS-THEN-DETERMINE ATTACKS ON GOST」(PDF)。Versita 。 2014年8月25日閲覧。

[13] 磯部孝則 (2011)。「フル GOST ブロック暗号に対する単一キー攻撃」。高速ソフトウェア暗号化。コンピュータサイエンスの講義ノート。第 6733 巻。pp . 290–305。doi :10.1007 / 978-3-642-21702-9_17。ISBN 978-3-642-21701-2。

[14] Dinur, Itai; Dunkelman, Orr; Shamir, Adi (2012). 「Full GOST に対する改良された攻撃」.高速ソフトウェア暗号化. コンピュータサイエンスの講義ノート. Vol. 7549. pp. 9–28. doi : 10.1007/978-3-642-34047-5_2 . ISBN 978-3-642-34046-8。

[15] 「暗号化技術と鍵の長さの評価に関する ISO/IEC JTC 1/SC 27 常設文書 No. 12 (SD12) の草案、第 4 版」(PDF)。2016 年。