Abstract
In this paper we propose a new key recovery attack on irregular clocked keystream generators where the stream is filtered by a nonlinear Boolean function. We show that the attack is much more efficient than expected from previous analytic methods, and we believe it improves all previous attacks on the cipher model.
Chapter PDF
Similar content being viewed by others
References
Chepyzhov, 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)
Chose, P., Joux, A., Mitton, M.: Fast correlation attacks: An algorithmic point of view. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 209–221. Springer, Heidelberg (2002)
Courtois, N.: 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 attacks on stream ciphers with linear feedback. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 345–359. Springer, Heidelberg (2003)
Golić, J.D.: Computation of low-weight parity-check polynomials. Electronic Letters 32(21), 1981–1982 (1996)
Johansson, T., Jönsson, F.: Theoretical analysis of a correlation attack based on convolutional codes. In: Proceedings of 2000 IEEE International Symposium on Information Theory. IEEE Transaction on Information Theory, p. 212 (2000)
Jönsson, F., Johansson, T.: A fast correlation attack on LILI-128. Inf. Process. Lett. 81(3), 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)
Matsui, M.: Linear cryptanalysis method for DES cipher. In: Helleseth, T. (ed.) EUROCRYPT 1993. LNCS, vol. 765, pp. 386–397. Springer, Heidelberg (1994)
Meier, W., Staffelbach, O.: Fast correlation attacks on stream ciphers. In: Günther, C.G. (ed.) EUROCRYPT 1988. LNCS, vol. 330, pp. 301–314. Springer, Heidelberg (1988)
Molland, H.: Improved linear consistency attack on irregular clocked keystream generators. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 109–126. Springer, Heidelberg (2004), To appear Available at http://www.ii.uib.no/~molland/crypto
Molland, H., Mathiassen, J.E., Helleseth, T.: Improved fast correlation attack using low rate codes. In: Paterson, K.G. (ed.) Cryptography and Coding 2003. LNCS, vol. 2898, pp. 67–81. Springer, Heidelberg (2003)
Penzhorn, W.T., Kuhn, G.J.: Computation of low-weight parity checks for correlation attacks on stream ciphers. In: Boyd, C. (ed.) Cryptography and Coding 1995. LNCS, vol. 1025, pp. 74–83. Springer, Heidelberg (1995)
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.: Decrypting a class of stream ciphers using ciphertext only. IEEE Trans. on Comp. C-34, 81–85 (1985)
Simpson, L., Dawson, E., Golić, J., Millan, W.: LILI keystream generator. In: Stinson, D.R., Tavares, S. (eds.) SAC 2000. LNCS, vol. 2012, pp. 231–236. Springer, Heidelberg (2001), Available at http://www.isrc.qut.edu.au/lili
Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288–303. Springer, Heidelberg (2002)
Zhang, X.-M., Zheng, Y.: The nonhomomorphicity of boolean functions. In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, pp. 280–295. Springer, Heidelberg (1999)
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
Molland, H., Helleseth, T. (2004). An Improved Correlation Attack Against Irregular Clocked and Filtered Keystream Generators. In: Franklin, M. (eds) Advances in Cryptology – CRYPTO 2004. CRYPTO 2004. Lecture Notes in Computer Science, vol 3152. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-28628-8_23
Download citation
DOI: https://doi.org/10.1007/978-3-540-28628-8_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22668-0
Online ISBN: 978-3-540-28628-8
eBook Packages: Springer Book Archive