Improved fast correlation attacks using parity-check equations of weight 4 and 5


Anne Canteaut
INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France
Anne.Canteaut@inria.fr

Michaël Trabbia
INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France
and Ecole Polytechnique
91128 Palaiseau Cedex, France michael.trabbia@enst.fr

In Advances in Cryptology - EUROCRYPT 2000 , LNCS, Springer-Verlag, 2000.
To appear.

Abstract

This paper describes new techniques for fast correlation attacks, based on Gallager iterative decoding algorithm using parity-check equations of weight greater than~3. These attacks can be applied to any key-stream generator based on LFSRs and it does not require that the involved feedback polynomial have a low weight. We give a theoretical analysis of all fast correlation attacks, which shows that our algorithm with parity-check equations of weight~4 or~5 is usually much more efficient than correlation attacks based on convolutional codes or on turbo codes. Simulation results confirm the validity of this comparison. In this context, we also point out the major role played by the nonlinearity of the Boolean function used in a combination generator.