Correlation Attacks on Stream Ciphers

Correlation attacks apply mainly to stream ciphers and can be considered as an extension of the idea of distinguishing attacks to collect information on secret key bits. The original correlation attack was proposed by Siegenthaler on nonlinear combination generators. In a nonlinear combination generator, the keystream is generated as the output of a Boolean function with inputs being sequences from several linear-feedback shift registers (LFSRs). The keystream depends on the state. In some constructions the LFSR has a feedback polynomial of low weight, chosen because it allows for an efficient implementation. This chapter gives two examples of basic generalized correlation attacks: The E0 stream cipher and The A5/1 stream cipher. The E0 stream cipher in the Bluetooth standard uses sequences from four different LFSRs entering a finite state machine. A5/1 is a stream cipher used in the old Global System for mobile communication standard, protecting communication from mobile to base station.