Optimal correlation attack on the multiplexer generator

The security of the well-known multiplexer generator with respect to correlation attacks on the data shift register is investigated. Apart from the basic correlation attack exploiting the bitwise correlation between the output sequence and any data input sequence, two new correlation attacks are introduced. One is based on computing the a posteriori probabilities and is statistically optimal, whereas the other makes use of the accumulated bitwise correlation to all data input sequences. It is theoretically argued and experimentally confirmed that the optimal attack requires a significantly shorter output sequence to be successful than the basic attack. The experiments also show that the less complex accumulated correlation attack requires a somewhat longer output sequence than the optimal attack.