相関攻撃

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

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

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

これにより、LFSR-3 の可能なキー (初期値) 空間を総当たりで探索することが可能になります (LFSR-3 のタップビットが既知であると仮定します。この仮定は、ケルクホフスの原理と一致しています)。キー空間内の任意のキーに対して、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の長さに依存します。現実的な値であれば、これは非常に大きな節約となり、総当たり攻撃を非常に実用的なものにすることができます。

上記の表を見ると、${\displaystyle x_{2}}$また、発電機の出力とも8回中6回一致し、相関性は75%である。${\displaystyle x_{2}}$そして、ジェネレータの出力です。LFSR-1とLFSR-3の鍵とは無関係に、LFSR-2に対する総当たり攻撃を開始し、LFSR-1だけを未破りにすることができます。このように、完全に独立した3つのLFSRを総当たり攻撃するのに必要な労力と同程度の労力で、Geffeジェネレータを破ることができます。これは、Geffeジェネレータが非常に脆弱なジェネレータであり、ストリーム暗号のキーストリームを生成するために決して使用すべきではないことを意味します。

上記の表から、${\displaystyle x_{1}}$8回中4回はジェネレーターの出力と一致し、相関率は50%です。これを利用してLFSR-1を他のものとは独立して総当たり攻撃することはできません。正しい鍵は50%の確率でジェネレーターの出力と一致しますが、平均的には間違った鍵でも同様に一致します。これはセキュリティの観点から理想的な状況を表しています。${\displaystyle F(x_{1},x_{2},x_{3})}$各変数と結合関数の出力との相関が50%にできるだけ近づくように選択する必要があります。実際には、周期の長さなどの他の設計基準を犠牲にすることなくこれを実現する関数を見つけるのは難しい場合があるため、妥協が必要になるかもしれません。

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

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

高次の相関攻撃は、単次の相関攻撃よりも強力になる可能性がありますが、この効果には「限界収益の法則」が適用されます。以下の表は、単一のブール関数で結合された 8 つの 8 ビット LFSR で構成されるキーストリーム生成器に対するさまざまな攻撃の計算コストを示しています。コストの計算方法は比較的簡単です。合計の左端の項は相関生成器のキー空間のサイズを表し、右端の項は残りの生成器のキー空間のサイズを表します。

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

ブール関数${\displaystyle F(x_{1},\ldots ,x_{n})}$n個の変数からなる関数は、その出力と、m 個の入力からなる任意のブール関数との間に有意な相関が存在しない場合、「m次相関耐性」または「m 次相関耐性」を持つと言われます。たとえば、1 次または 2 次相関はないが 3 次相関があるブール関数は、2 次相関耐性を示します。明らかに、相関耐性が高いほど、関数はキーストリームジェネレータでの使用に適しています (ただし、考慮すべき点はこれだけではありません)。

ジーゲンターラーは、 n個の変数の代数次数dのブール関数の相関耐性mが以下を満たすことを示した。${\displaystyle m+d\leq n}$; 与えられた入力変数のセットに対して、これは、高い代数次数が可能な最大の相関耐性を制限することを意味します。さらに、関数がバランスが取れている場合、${\displaystyle m\leq n-1}$[ ^{1 ]​}

したがって、 n個の変数を持つ関数がn次相関の影響を受けないことは不可能である。これは、そのような関数はすべて、入力関数のXORの組み合わせとしてリード・ミュラー基底を用いて記述できるという事実からも導かれる。