An Improved Fast Correlation Attack on Stream Ciphers
English
Zhang, Bin[University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Feng, Dengguo[State Key Laboratory of Information Security, Institute of Software, Chinese Academy of Sciences]
2008
Selected Areas in Cryptography
Springer
Lecture Notes in Computer Science, 5381
214-227
No
978-3-642-04158-7
Berlin
Germany
15th International Workshop, SAC 2008
August 14-15,2008
Sackville, NB
Canada
[en] At Crypto’2000, Johansson and Jönsson proposed a fast correlation attack on stream ciphers based on the Goldreich-Rubinfeld-Sudan algorithm. In this paper we show that a combination of their approach with techniques for substituting keystream and evaluating parity-checks gives us the most efficient fast correlation attack known so far. An application of the new algorithm results in the first-known near-practical key recovery attack on the shrinking generator with the parameters suggested by Krawczyk in 1994, which was verified in the 40-bit data LFSR case for which the only previously known efficient attacks were distinguishing attacks.