相関攻撃

1985年、ジーゲンターラーは、キーストリームが複数の LFSR の非線形関数になっている結合ジェネレーターを、レジスタ1本ずつ破れることを示した。出力が特定のレジスタの出力と十分な頻度で一致するなら、攻撃者はキーストリームからそのレジスタの状態を推測し、短いサンプルに照らして各候補を検証できる。

この攻撃は、相関が弱くてもレジスタが短ければ実用になる。現代のストリーム暗号が、複数の LFSR を組み合わせるだけでなく非線形な構成要素に頼る理由の一つでもある。乱数らしく見える出力を足し合わせても、自動的に乱数になるわけではない。