グレイン（暗号）

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 ⁸⁰を大幅に下回らない計算複雑度が必要であると主張しています。

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

著者らは、 E0に対する攻撃^{[2]では240フレーム}と²³⁵フレーム（フレームの長さは2745ビット）の複雑さが必要であると述べている。オリジナルのGrainバージョン0.0暗号は、80ビットのキーを決定するために^243の計算と^238のキーストリームビットの複雑さを必要とするキー回復攻撃^[3]によって破られた。

改訂版 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') ペアが存在します。これはまだ効率的なキー回復攻撃にはつながりませんが、初期化の弱点を示しており、少しの努力で克服できる可能性があります。」と 主張しています。

• Grain の eSTREAM ページは、Wayback Machineで 2008-10-06 にアーカイブされています。