Optimal Correlation Attack on the MUX Generator
by
Jovan Golic
Security Innovation, Telecom Italia, Turin, Italy
Coauthors: Guglielmo Morgari

MUX generator is a well-known keystream generator proposed by Jennings in 1980. It consists of two LFSRs, one of which produces the address sequence for a MUX, while the other produces the data input sequence to the MUX. The output sequence is taken from the MUX output, one bit at a time. It possesses controllable properties such as a long period and a high linear complexity. However, over the years, relatively many cryptanalytic attacks on the MUX generator have been developed. They include correlation attack, fast correlation attack, collision attack, linear consistency test, resynchronization attack, and the autocorrelation weakness.

The basic correlation attack targets the data LFSR and exploits the fact that the output bit is correlated to any of M inputs to the MUX with the correlation coefficient 1/M. Accordingly, it chooses the data LFSR initial state that minimizes the Hamming distance between the output segment and the segment of any selected input sequence. This work is motivated by the following questions: (1) can we use correlations to all input sequences, (2) can we just accumulate the individual Hamming distances, and (3) what is the statistically optimal correlation attack targeting the data LFSR?

In this talk, the optimal correlation attack on the MUX generator will be introduced and the minimal required output sequence length will be determined. The optimal attack will be compared with the accumulated Hamming distance attack, by using a sort of the list decoding approach, in an appropriate experimental setting. It turns out that both attacks reduce the required output sequence length considerably, in comparison with the basic correlation attack.

Date received: June 28, 2006