相関攻撃

相関攻撃は、ブール関数を用いて複数の線形フィードバックシフトレジスタ（LFSR）の出力を組み合わせることでキーストリームが生成されるストリーム暗号を解読するための、暗号既知平文攻撃の一種です。相関攻撃は、キーストリームに選択された特定のブール関数に起因する統計的な弱点を悪用します。一部のブール関数は相関攻撃に対して脆弱ですが、そのような関数を用いて生成されたストリーム暗号は本質的に安全ではありません。

説明

相関攻撃は、キーストリームジェネレーターの個々の LFSR の出力状態と、すべての LFSR の出力状態を組み合わせたブール関数の出力との間に有意な相関関係がある場合に可能になります。これらの攻撃は、平文の部分的な知識から得られるキーストリームの部分的な知識と組み合わせて利用されます。次に、この 2 つを XOR ロジックゲートを使用して比較します。この脆弱性により、攻撃者は個々の LFSR とシステムの残りの部分のキーを個別に総当たり攻撃できます。たとえば、4 つの 8 ビット LFSR を組み合わせてキーストリームを生成するキーストリームジェネレーターで、レジスタの 1 つがブール関数の出力と相関している場合、最初にそのレジスタを総当たり攻撃し、次に残りの 3 つの LFSR を総当たり攻撃できます。その結果、攻撃の複雑さは全体で 2 ⁸ + 2 ²⁴になります。

^{複雑度が 2 32}であるシステム全体に対するブルートフォース攻撃を実行するコストと比較すると、これは攻撃の労力節約係数が 256 未満であることを意味します。2 番目のレジスタが関数と相関関係にある場合、このプロセスを繰り返して攻撃の複雑度を 2 ⁸ + 2 ⁸ + 2 ¹⁶まで下げることができ、労力節約係数は 65028 未満になります。

例

ゲッフェ発電機

一例として、Geffeジェネレータが挙げられます。これは3つのLFSR（LFSR-1、LFSR-2、LFSR-3）で構成されています。これらのレジスタをそれぞれ、、、と表記します。すると、3つのレジスタを組み合わせてジェネレータの出力を生成するブール関数は、（すなわち、（AND ）XOR（NOT AND ））で表されます。3つのレジスタの出力には2 ³ = 8通りの値があり、それぞれの組み合わせ関数の値は下表のようになります。 $x_{1}$ $x_{2}$ $x_{3}$ $F(x_{1},x_{2},x_{3})=(x_{1}\wedge x_{2})\oplus (\neg x_{1}\wedge x_{3})$ $x_{1}$ $x_{2}$ $x_{1}$ $x_{3}$

ブール関数の出力表
$x_{1}$	$x_{2}$	$x_{3}$	$F(x_{1},x_{2},x_{3})$
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

3番目のレジスタの出力を考えてみましょう。上の表は、の8つの可能な出力のうち6つが、ジェネレータの出力の対応する値と等しいことを示しています。すべての可能なケースの75%において、となります。したがって、LFSR-3はジェネレータと「相関」しています。これは、次のように悪用される可能性のある弱点です。 $x_{3}$ $x_{3}$ $F(x_{1},x_{2},x_{3})$ $x_{3}=F(x_{1},x_{2},x_{3})$

Geffe ジェネレータをキーストリームジェネレータとして使用してストリーム暗号で暗号化されたプレーンテキストの暗号文、つまりに対して（は時刻における LFSR-1 の出力など）を傍受することができます。また、プレーンテキストの一部、たとえばプレーンテキストの最初の 32 ビット（テキストの 4 つの ASCII 文字に対応）がになる可能性もあります。プレーンテキストが有効な XML ファイルであることを考えると、これはまったくあり得ないことではありません。たとえば、最初の 4 つの ASCII 文字は "<xml" でなければなりません。同様に、多くのファイル形式やネットワークプロトコルには、非常に標準的なヘッダーまたはフッターがあります。傍受されたと既知/推測されたがあれば、この 2 つを XOR 演算することでに対してを簡単に見つけることができます。これにより、ジェネレータ出力の連続する 32 ビットを簡単に特定できます。 $c_{1},c_{2},c_{3},\ldots ,c_{n}$ $p_{1},p_{2},p_{3},\ldots$ $c_{i}=p_{i}\oplus F(x_{1i},x_{2i},x_{3i})$ $i=1,2,3,\ldots ,n$ $x_{1i}$ $i$ $p_{1},p_{2},p_{3},\ldots ,p_{32}$ $c_{1},c_{2},c_{3},\ldots ,c_{32}$ $p_{1},p_{2},p_{3},\ldots ,p_{32}$ $F(x_{1i},x_{2i},x_{3i})$ $i=1,2,3,\ldots ,32$

これにより、LFSR-3 の可能なキー (初期値) の空間の総当たり検索が可能になります (LFSR-3 のタップされたビットがわかっていると仮定し、この仮定は Kerckhoffs の原理と一致しています)。キー空間内の任意のキーについて、LFSR-3 出力の最初の 32 ビットをすばやく生成し、これをジェネレーター全体の出力から復元された 32 ビットと比較できます。LFSR-3 の出力とジェネレーターの出力の間には 75% の相関関係があることを既に確認しているため、LFSR-3 出力の最初の 32 ビットのうち約 24 がジェネレーター出力の対応するビットと一致すれば、LFSR-3 のキーを正しく推測できたことがわかります。推測が間違っていた場合は、これら 2 つのシーケンスの最初の 32 ビットのうち約半分、つまり 16 が一致すると予想されます。したがって、LFSR-1 と LFSR-2 のキーとは独立して、LFSR-3 のキーを復元できます。この段階では、3つのLFSRからなるシステムに対する総当たり攻撃の問題は、1つのLFSR、そして2つのLFSRからなるシステムに対する総当たり攻撃の問題にまで軽減されました。ここでの労力削減量は、LFSRの長さに依存します。現実的な値であれば、これは非常に大きな節約となり、総当たり攻撃を非常に現実的なものにすることができます。

上の表を見ると、8回中6回は生成器の出力と一致しており、これも生成器の出力と75%の相関関係にあることがわかります。LFSR-1とLFSR-3の鍵とは独立して、LFSR-2に対してブルートフォース攻撃を開始し、LFSR-1だけを解読することができます。このように、完全に独立した3つのLFSRをブルートフォース攻撃するのと同じ労力で、Geffe生成器を解読することができます。これは、Geffe生成器が非常に弱い生成器であり、ストリーム暗号の鍵ストリームの生成には決して使用すべきではないことを意味します。 $x_{2}$ $x_{2}$

上の表から、8回中4回生成器の出力と一致することに注目してください。これは50%の相関です。これを他の変数とは独立してLFSR-1をブルートフォース攻撃することはできません。正しいキーは生成器の出力と50%の確率で一致しますが、平均すると間違ったキーも同様に一致します。これはセキュリティの観点から理想的な状況を表しています。つまり、各変数と結合関数の出力の相関が可能な限り50%に近くなるように結合関数を選択する必要があります。実際には、周期の長さなどの他の設計基準を犠牲にすることなくこれを実現する関数を見つけるのは難しい場合があり、妥協が必要になる可能性があります。 $x_{1}$ $F(x_{1},x_{2},x_{3})$

攻撃の統計的性質を明らかにする

上記の例は相関攻撃の背後にある比較的単純な概念をよく示していますが、個々の LFSR に対するブルートフォース攻撃がどのように行われるかという説明を簡略化している可能性があります。誤って推測されたキーは、ジェネレータの出力と約 50% の確率で一致する LFSR 出力を生成します。これは、与えられた長さの 2 つのランダムなビットシーケンスが与えられた場合、特定のビットにおけるシーケンス間の一致確率が 0.5 であるためです。しかし、特定の個々の誤ったキーは、ジェネレータの出力と正確に 50% よりも多い、または少ない頻度で一致する LFSR 出力を生成する可能性があります。これは、ジェネレータとの相関がそれほど強くない LFSR の場合に特に顕著です。相関が十分に小さい場合、誤って推測されたキーがジェネレータの出力の目的のビット数と一致する LFSR 出力を生成する可能性も否定できません。したがって、その LFSR に固有のキーを特定できない可能性があります。ただし、潜在的なキーを複数特定できる可能性はありますが、それでも暗号のセキュリティは著しく侵害されます。さらに、1 メガバイトの既知の平文があれば、状況は大きく異なります。誤ったキーでは、ジェネレータ出力の 512 キロバイト以上と一致する LFSR 出力が生成される場合がありますが、正しく推測されたキーのように、ジェネレータ出力の 768 キロバイトと一致する出力が生成される可能性は低くなります。原則として、個々のレジスタとジェネレータ出力の相関が弱いほど、高い信頼度でそのレジスタのキーを見つけるために必要な既知の平文が多くなります。特定の相関に必要な既知の平文の長さの推定値は、二項分布を使用して計算できます。

高次相関

意味

Geffeジェネレータへの攻撃例で利用された相関は、いわゆる一次相関の例です。一次相関とは、ジェネレータの出力値と個々のLFSRとの間の相関です。これらに加えて、より高次の相関を定義することもできます。例えば、あるブール関数は、それが結合する個々のレジスタのいずれとも強い相関関係を持たない一方で、2つのレジスタのブール関数間には有意な相関関係が存在する可能性があります（例：）。これは二次相関の例です。このようにして、三次以上の相関関係を定義できます。 $x_{1}\oplus x_{2}$

高階相関攻撃は単階相関攻撃よりも強力になる可能性がありますが、この効果は「収穫逓減の法則」の影響を受けます。下の表は、8ビットLFSRを1つのブール関数で結合した8つのキーストリーム生成器に対する様々な攻撃の計算コストの測定値を示しています。コストの計算を理解するのは比較的簡単です。合計の左端の項は相関する生成器のキー空間のサイズを表し、右端の項は残りの生成器のキー空間のサイズを表します。

発電機攻撃の取り組み
攻撃	労力（キースペースのサイズ）
力ずくで	$2^{8\times 8}=18446744073709551616$
単一の1次相関攻撃	$2^{8}+2^{7\times 8}=72057594037928192$
単一の2次相関攻撃	$2^{2\times 8}+2^{6\times 8}=281474976776192$
単一の3次相関攻撃	$2^{3\times 8}+2^{5\times 8}=1099528404992$
単一の4次相関攻撃	$2^{4\times 8}+2^{4\times 8}=8589934592$
単一の5次相関攻撃	$2^{5\times 8}+2^{3\times 8}=1099528404992$
単一の6次相関攻撃	$2^{6\times 8}+2^{2\times 8}=281474976776192$
単一の7次相関攻撃	$2^{7\times 8}+2^{8}=72057594037928192$

高次の相関関係はより強力な攻撃につながりますが、関数の引数の数が増えるにつれて、ジェネレーターの出力と相関する利用可能なブール関数の空間が増加するため、それらを見つけることもより困難になります。

用語

$n$ 変数のブール関数は、関数の出力と $m個の入力を持つブール関数との間に有意な相関がない場合、「$ $m$ 次相関耐性」、またはある整数 $m$ に対して「 m 次相関耐性」を持つ $と$ 言われます。例えば、1 次または 2 次相関を持たないが、3 次相関を持つブール関数は、2 次相関耐性を示します。明らかに、相関耐性が高いほど、関数はキーストリーム生成器での使用により適したものになります（ただし、これは考慮すべき唯一の点ではありません）。 $F(x_{1},\ldots ,x_{n})$

$ジーゲンサーラーは、 n$ 変数の代数次数 $d$ のブール関数の相関耐性 $mが$ を満たすことを示した。これは、与えられた入力変数の集合に対して、高い代数次数が相関耐性の最大可能値を制限することを意味する。さらに、関数が釣り合っている場合、mはを満たす。^[¹^] $m+d\leq n$ $m\leq n-1$

$したがって、 n$ 変数の関数が $n$ 次の相関に対して無関係であることは不可能である。これは、そのような関数はリード・ミュラー基底を用いて入力関数の排他的論理和の組み合わせとして記述できることからも明らかである。

暗号設計への影響

相関攻撃がストリーム暗号のセキュリティに及ぼす影響が極めて深刻である可能性を考慮すると、候補となるブール組み合わせ関数をストリーム暗号で使用するかどうかを決定する前に、相関耐性についてテストすることが不可欠です。ただし、高い相関耐性はブール関数をキーストリーム生成器で使用するのに適切であるための必要条件ではありますが、十分条件ではないことに注意することが重要です。他にも考慮すべき点があります。例えば、関数がバランスが取れているかどうか、つまり、すべての可能な入力を考慮した際に、1が0と同数、あるいはほぼ同数出力されるかどうかなどです。

与えられたサイズで、少なくとも特定の順序の相関耐性を保証するブール関数を容易に生成する手法に関する研究が行われてきました。この研究により、相関耐性ブール関数と誤り訂正符号との関連性が明らかになりました。^{[ 2 ]}

参照

暗号学のトピック

参考文献

^ T. Siegenthaler (1984年9月). 「暗号アプリケーションにおける非線形結合関数の相関耐性」. IEEE Transactions on Information Theory . 30 (5): 776– 780. doi : 10.1109/TIT.1984.1056949 .
^ Chuan-Kun Wu と Ed Dawson、「相関免疫ブール関数の構築」、Wayback Machineに 2006-09-07アーカイブ、ICICS97

ブルース・シュナイアー著『応用暗号：C言語によるプロトコル、アルゴリズム、ソースコード』第2版、John Wiley & Sons, Inc. 1996年ISBN 0-471-12845-7セクション 16.4 の 382 ページ: LFSR を使用したストリーム暗号。

外部リンク

ブール関数のオンラインデータベースでは、相関免除などのさまざまな方法でブール係数のデータベースを検索できます。

[Siegenthaler-1] T. Siegenthaler (1984年9月). 「暗号アプリケーションにおける非線形結合関数の相関耐性」. IEEE Transactions on Information Theory . 30 (5): 776– 780. doi : 10.1109/TIT.1984.1056949 .

[2] Chuan-Kun Wu と Ed Dawson、「相関免疫ブール関数の構築」、Wayback Machineに 2006-09-07アーカイブ、ICICS97

[

[ 2 ]