Abstract
This paper presents a new simple distinguishing attack that can be applied on stream ciphers constructed from filter generators or similar structures. We demonstrate the effectiveness by describing key recovery attacks on the stream cipher LILI-128. One attack on LILI-128 requires 247 bits of keystream and a computational complexity of roughly 253. This is a significant improvement compared to other known attacks.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Canteaut, A., Trabbia, M.: Improved fast correlation attacks using parity-check equations of weight 4 and 5. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 573–588. Springer, Heidelberg (2000)
Chepyzhov, V.V., Johansson, T., Smeets, B.: A simple algorithm for fast correlation attacks on stream ciphers. In: Schneier, B. (ed.) FSE 2000. LNCS, vol. 1978, pp. 181–195. Springer, Heidelberg (2001)
Simpson, L.R., Dawson, E., Golić, J.D., Millan, W.L.: LILI keystream generator. In: Stinson, D.R., Tavares, S. (eds.) SAC 2000. LNCS, vol. 2012, p. 248. Springer, Heidelberg (2001)
Coppersmith, D., Halevi, S., Jutla, C.S.: Cryptanalysis of stream ciphers with linear masking. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 515–532. Springer, Heidelberg (2002)
Courtois, N.T.: Fast algebraic attacks on stream ciphers with linear feedback. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 176–194. Springer, Heidelberg (2003)
Courtois, N., Meier, W.: Algebraic attack on strem ciphers with linear feedback. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 345–359. Springer, Heidelberg (2003)
Cover, T., Thomas, J.A.: Elements of Information Theory. Wiley series in Telecommunication. Wiley, Chichester (1991)
Ekdahl, P., Johansson, T.: Distinguishing attacks on SOBER-t16 and t32. In: Daemen, J., Rijmen, V. (eds.) FSE 2002. LNCS, vol. 2365, pp. 210–224. Springer, Heidelberg (2002)
Golić, J.D.: Computation of low-weight parity-check polynomials. Electronic Letters 32(21), 1981–1982 (1996)
Golić, J.D.: On the security of nonlinear filter generators. In: Gollmann, D. (ed.) FSE 1996. LNCS, vol. 1039, pp. 173–188. Springer, Heidelberg (1996)
Golić, J.D., Clark, A., Dawson, E.: Inversion attack and branching. In: Pieprzyk, J.P., Safavi-Naini, R., Seberry, J. (eds.) ACISP 1999. LNCS, vol. 1587, pp. 88–102. Springer, Heidelberg (1999)
Golić, J.D., Clark, A., Dawson, E.: Generalized inversion attack on nonlinear filter generators. ITCOMP 49(10), 1100–1109 (2000)
Johansson, T., Jönsson, F.: Fast correlation attacks based on turbo code techniques. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 181–197. Springer, Heidelberg (1999)
Johansson, T., Jönsson, F.: Improved fast correlation attacks on stream ciphers via convolutional codes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 347–362. Springer, Heidelberg (1999)
Johansson, T., Jönsson, F.: A fast correlation attack on LILI-128. Information Processing Letters 81, 127–132 (2002)
Leveiller, S., Zémor, G., Guillot, P., Boutros, J.: A New Cryptanalytic Attack for PN-generators Filtered by a Boolean Function. In: Nyberg, K., Heys, H.M. (eds.) SAC 2002. LNCS, vol. 2595, pp. 232–249. Springer, Heidelberg (2003)
Meier, W., Staffelbach, O.: Fast correlation attacks on stream ciphers. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 301–316. Springer, Heidelberg (1988)
Menezes, A., van Oorschot, P., Vanstone, S.: Handbook of Applied Cryptography. CRC Press, Boca Raton (1997)
Molland, H.: Improved linear consistency attack on irregular clocked keystream generators. In: Fast Software Encryption (2004)
Molland, H., Helleseth, T.: An improved correlation attack against irregular clocked and filtered keystream generators. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 373–389. Springer, Heidelberg (2004)
Pasalic, E.: On Boolean Functions in Symmetric-Key Ciphers. PhD thesis, Lund University, Department of Information Technology, P.O. Box 118, SE–221 00, Lund, Sweden (2003)
Saarinen, M.-J.O.: A time-memory tradeoff attack against LILI-128. In: Daemen, J., Rijmen, V. (eds.) FSE 2002. LNCS, vol. 2365, pp. 231–236. Springer, Heidelberg (2002)
Siegenthaler, T.: Correlation-immunity of non-linear combining functions for cryptographic applications. IEEE Transactions on Information Theory 30, 776–780 (1984)
Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288–303. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Englund, H., Johansson, T. (2004). A New Simple Technique to Attack Filter Generators and Related Ciphers. In: Handschuh, H., Hasan, M.A. (eds) Selected Areas in Cryptography. SAC 2004. Lecture Notes in Computer Science, vol 3357. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30564-4_3
Download citation
DOI: https://doi.org/10.1007/978-3-540-30564-4_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24327-4
Online ISBN: 978-3-540-30564-4
eBook Packages: Computer ScienceComputer Science (R0)