Ciphertext Only Reconstruction of Stream Ciphers based on Combination Generators


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

Eric Filiol
INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France
and
Ecoles Militaires de Coëtquidan, DGER/CREC
56381 Guer Cedex, France
Eric.Filiol@inria.fr

In Fast Software Encryption 2000 , LNCS, Springer-Verlag, 2000.
To appear.

Abstract

This paper presents an operational reconstruction technique of most stream ciphers. We primarily expose it for key-stream generators which consist of several linear feedback shift registers combined by a nonlinear Boolean function. It is shown how to completely recover the different feedback polynomials and the combining function, when the algorithm is totally unknown. This attack only requires the knowledge of some ciphertexts, which may be generated from different secret keys. Estimates of necessary ciphertext length and experimental results are detailed.

Keywords

stream cipher, Boolean function, correlation, linear feedback shift register, ciphertext only reconstruction.