グレイン（暗号）

Grainは、 2004年にMartin Hell、Thomas Johansson、Willi MeierによってeSTREAMに提出されたストリーム暗号です。eSTREAMプロジェクトによって、Profile 2の最終eSTREAMポートフォリオに選定されました。Grainは主に制限されたハードウェア環境向けに設計されています。80ビットの鍵と64ビットのIVを受け入れます。仕様では、(鍵、IV)ペアあたりの出力の最大長は推奨されていません。この暗号の潜在的な弱点がいくつか特定され、Grain 128aで修正されました。現在、Grain 128aは128ビットのセキュリティと認証の両方を提供するハードウェア環境で使用する推奨暗号となっています。

説明

Grainの160ビット内部状態は、80ビットの線形フィードバックシフトレジスタ（LFSR）と80ビットの非線形フィードバックシフトレジスタ（NLFSR）で構成されています。Grainは、非線形フィルタ関数によって解放された暗号文のビットごとに、LFSRの1ビットとNLFSRの1ビットの状態を更新します。80ビットのNLFSRは、非線形5対1ブール関数と、LFSRから選択された1ビットの線形入力によって更新されます。非線形5対1関数は、NLFSR状態の5ビットを入力として受け取ります。80ビットのLFSRは、6対1の線形関数によって更新されます。キー操作中、暗号の出力は、NLFSRとLFSR更新関数の両方に線形入力としてフィードバックされます。

Grain のオリジナルの Grain バージョン 0.0 提出では、80 ビット NLFSR の 1 ビットと 80 ビット LFSR の 4 ビットが非線形 5 対 1 ブール関数 (バランスが取れていて、1 次相関がなく、代数次数が 3 になるように選択) に供給され、出力は 80 ビット NLFSR の 1 ビットと線形に結合され、出力として解放されます。

Grain の更新された Grain バージョン 1.0 の提出では、80 ビット NLFSR の 1 ビットと 80 ビット LFSR の 4 ビットが (わずかに修正された) 非線形 5 対 1 ブール関数に供給され、出力は 80 ビット NLFSR の 7 ビットと線形に結合され、出力として解放されます。

暗号を初期化するために、80ビットの鍵が80ビットのNLFSRに直接ロードされ、64ビットのIVがLFSRの下位64ビットにロードされ、LFSRの残りの上位16ビットは1で埋められます。暗号は160ラウンドで暗号化され、生成された160ビットの鍵ストリームはLFSRとNLFSRの更新関数の両方に線形フィードバックされます。この初期化プロセス中、暗号は鍵ストリームを出力しません。

Grain の著者は、Grain バージョン 1.0 仕様書で、Grain 初期化プロセスの完全な拡散率について次のように述べています。「1 ビットのみ異なる 2 つの異なる IV を使用した初期化の場合、両方の初期化でシフトレジスタ ビットが同じである確率は 0.5 に近くなるはずです。シミュレーションでは、これが 160 回のクロッキング後に達成されることが示されています。」

パフォーマンス

この暗号は、最大 16 ラウンドを並行して実行できるように設計されており、ハードウェアの使用量が増える代わりに実装が高速化されます。

安全

鍵サイズは80ビット、IVサイズは64ビットに指定されています。著者らは、この暗号は網羅的な鍵探索よりも高速な攻撃が不可能となるように設計されており、したがって、最善の攻撃でも計算量は2 80を大幅に下回らないはずだと主張しています。

オリジナルのGrainバージョン0.0仕様[ 1 ]では、作成者は次のように主張しています。「Grainは、ハードウェアアプリケーションで使用することを目的とした他のいくつかのよく知られた暗号よりも高いセキュリティを提供します。このような暗号のよく知られた例としては、Bluetoothで使用されるE0やGSMで使用されるA5/1があります。これらの暗号は、ハードウェア実装が非常に小さいにもかかわらず、非常に安全性が低いことが証明されています。E0やA5/1と比較して、Grainはハードウェアの複雑さを小さく抑えながら、より高いセキュリティを提供します。」

著者らは、 E0に対する攻撃[ 2 ]を引用しており、その攻撃には2の40乗の計算量と2の35フレーム（1フレームは2745ビット長）の計算量が必要であった。オリジナルのGrainバージョン0.0暗号は、鍵回復攻撃[ 3 ]によって解読されたが、この攻撃では80ビットの鍵を解読するのに2の43乗の計算量と2の38ビットの鍵ストリームビットが必要であった。

改訂版Grainバージョン1.0仕様[ 4 ]では、暗号の出力関数が若干変更され、NLFSRフィードバック関数にも軽微な変更が加えられました。仕様書では次のように述べられています。「フィルタ関数は非常に小さく、変数は5つ、非線形性は12です。しかし、入力の1つがNLFSRから取得されるという事実によって、この影響は部分的に補われています。NLFSRからの入力ビットは、LFSRとNLFSRの両方から得られる状態内の他のビットに非線形に依存します。この小さなフィルタ関数は、適切な位置にNLFSRから7ビットを線形に追加することでも補われ、出力関数を形成します。」

2006 年 10 月現在、Grain バージョン 1.0 に対して、ブルート フォース攻撃よりも優れたキー回復攻撃は知られていません。

しかし、2006年9月にオズグル・クチュク（Ozgul Kucuk）は論文「Grain 1.0の初期化におけるスライド再同期攻撃」の中で、関連鍵攻撃を発表しました。[ 5 ]この論文は、「我々はストリーム暗号Grain 1.0の関連鍵と初期値を発見した。任意の(K,IV)ペアに対して、確率1/22で1ビットシフトされた鍵ストリームを生成する関連(K',IV')ペアが存在する。これはまだ効率的な鍵回復攻撃には繋がっていないが、初期化における弱点を示しており、少しの努力で克服できる可能性がある」と 主張しています。

参考文献

  1. ^ Martin Hell、Thomas Johansson、Willi Meier (2005年4月29日). 「Grain - 制約環境向けのストリーム暗号」(PDF) . eSTREAM.{{cite web}}: CS1 maint: 複数の名前: 著者リスト (リンク)
  2. ^ Yi Lu , http://lasecwww.epfl.ch/~vaudenay/ (2004). 「Bluetoothキーストリームジェネレータ2レベルE0の暗号解析」(PDF) . Advances in Cryptology – Asiacrypt 2004, LNCS vol. 3329, pp.483-499, Springer, 2004.
  3. ^ Côme Berbain、Henri Gilbert、Alexander Maximov (2006年1月2日). 「Cryptanalysis of Grain」(PDF) . eSTREAM.オリジナル(PDF)から2006年10月11日アーカイブ。 2006年2月26日閲覧。{{cite web}}: CS1 maint: 複数の名前: 著者リスト (リンク)
  4. ^ Martin Hell、Thomas Johansson、Willi Meier (2006). 「Grain - 制約環境向けのストリーム暗号」(PDF) . eSTREAM.{{cite web}}: CS1 maint: 複数の名前: 著者リスト (リンク)
  5. ^ Ozgul Kucuk (2006年7月16日). 「Grain 1.0の初期化に対するスライド再同期攻撃」 . eSTREAM.オリジナル( PS )から2011年5月27日にアーカイブ。2006年10月10日閲覧。
「 https://en.wikipedia.org/w/index.php?title=Grain_(cipher)&oldid=1229461843」より取得