Abstract
Fast correlation attacks have considerably evolved since their first appearance. They have lead to new design criteria of stream ciphers, and have found applications in other areas of communications and cryptography.
In this paper, a review of the development of fast correlation attacks and their implications on the design of stream ciphers over the past two decades is given.
Chapter PDF
Similar content being viewed by others
References
Ahmadian, Z., Mohajeri, J., Salmasizadeh, M., Hakala, R., Nyberg, K.: A practical distinguisher for the Shannon cipher. Journal of Systems and Software 83(4), 543–547 (2010)
Berbain, C., Gilbert, H., Maximov, A.: Cryptanalysis of grain. In: Robshaw, M.J.B. (ed.) FSE 2006. LNCS, vol. 4047, pp. 15–29. Springer, Heidelberg (2006)
Bluetooth SIG, Specification of the Bluetooth system, Version 1.1 (February 22, 2001), http://www.bluetooth.com/
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)
Chaum, D., Evertse, J.-H.: Cryptanalysis of DES with a Reduced Number of Rounds, sequences of linear factors in block ciphers. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 192–211. Springer, Heidelberg (1986)
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)
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), http://eprint.iacr.org/2002/020
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)
Cusick, T., Stanica, P.: Cryptographic Boolean Functions and Applications. Academic Press, London (2009)
Edel, Y., Klein, A.: Computational aspects of fast correlation attacks (2010) (preprint)
Ekdahl, P., Johansson, T.: A New Version of the Stream Cipher SNOW. In: Nyberg, K., Heys, H.M. (eds.) SAC 2002. LNCS, vol. 2595, pp. 47–61. Springer, Heidelberg (2003)
Ekdahl, P., Meier, W., Johansson, T.: Predicting the Shrinking Generator with Fixed Connections. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 330–344. Springer, Heidelberg (2003)
Englund, H., Johansson, T.: A New Simple Technique to Attack Filter Generators and Related Ciphers. In: Handschuh, H., Hasan, M.A. (eds.) SAC 2004. LNCS, vol. 3357, pp. 39–53. Springer, Heidelberg (2004)
Evertse, J.-H.: Linear structures in block ciphers. In: Price, W.L., Chaum, D. (eds.) EUROCRYPT 1987. LNCS, vol. 304, pp. 249–266. Springer, Heidelberg (1988)
Finiasz, M., Vaudenay, S.: When Stream Cipher Analysis Meets Public-Key Cryptography. In: Biham, E., Youssef, A.M. (eds.) SAC 2006. LNCS, vol. 4356, pp. 266–284. Springer, Heidelberg (2007)
Fossorier, M.P.C., Mihaljević, M.J., Imai, H., Cui, Y., Matsuura, K.: An Algorithm for Solving the LPN Problem and Its Application to Security Evaluation of the HB Protocols for RFID Authentication. In: Barua, R., Lange, T. (eds.) INDOCRYPT 2006. LNCS, vol. 4329, pp. 48–62. Springer, Heidelberg (2006)
Gallager, R.G.: Low-Density Parity-Check Codes. MIT Press, Cambridge (1963)
Golić, J.: Computation of low-weight parity-check polynomials. Electronic Letters 32(21), 1981–1982 (1996)
Golić, J.: Linear models for keystream generators. IEEE Trans. on Computers 45, 41–49 (1996)
Golić, J.: Correlation properties of a general binary combiner with memory. Journal of Cryptology 9, 111–126 (1996)
Golić, J., Salmasizadeh, M., Dawson, E.: Fast correlation attacks on the summation generator. Journal of Cryptology 13, 245–262 (2000)
Golić, J.D., Bagini, V., Morgari, G.: Linear Cryptanalysis of Bluetooth Stream Cipher. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 238–255. Springer, Heidelberg (2002)
Hawkes, P., Rose, G.: Exploiting Multiples of the Connection Polynomial in Word-Oriented Stream Ciphers. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 303–316. Springer, Heidelberg (2000)
Johansson, T., Jönsson, F.: Fast correlation attacks through reconstruction of linear polynomials. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 300–315. Springer, Heidelberg (2000)
Jönsson, F., Johansson, T.: A fast correlation attack on LILI-128. Inf. Process. Lett. 81(3), 127–132 (2002)
Jönsson, F.: Some results on fast correlation attacks, Thesis, Lund University, Sweden
Klapper, A., Goresky, M.: Feedback shift registers, 2-adic span, and combiners with memory. Journal of Cryptology 10, 111–147 (1997)
Levieil, É., Fouque, P.-A.: An Improved LPN Algorithm. In: De Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 348–359. Springer, Heidelberg (2006)
MacWilliams, F.J., Sloane, N.J.: The theory of error-correcting codes. North Holland, Amsterdam (1977)
Maitra, S., Gupta, K.C., Venkateswarlu, A.: Results on multiples of primitive polynomials and their products over GF(2). Theor. Comput. Sci. 341(1-3), 311–343 (2005)
Massey, J.L.: Shift-register synthesis and BCH decoding. IEEE Transactions on Information Theory 15, 122–127 (1969)
Meier, W., Staffelbach, O.: Fast correlation attacks on certain stream ciphers. Journal of Cryptology 1, 159–176 (1989)
Meier, W., Staffelbach, O.: Nonlinearity criteria for cryptographic functions. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 549–562. Springer, Heidelberg (1990)
Meier, W., Staffelbach, O.: Correlation properties of combiners with memory in stream ciphers. Journal of Cryptology 5, 67–86 (1992)
Mihaljević, M.J., Fossorier, M.P.C., Imai, H.: Fast correlation attack algorithm with list decoding and an application. In: Matsui, M. (ed.) FSE 2001. LNCS, vol. 2355, pp. 196–210. Springer, Heidelberg (2002)
Mihaljevic, M., Fossorier, M., Imai, H.: On decoding techniques for cryptanalysis of certain encryption algorithms. IEICE Trans. Fundamentals E84-A(4), 919–930 (2001)
Mobile Phone Security Algorithms - New Version, http://gsmworld.com/our-work/programmes-and-initiatives/
Mossel, E., Shpilka, A., Trevisan, L.: On ε-biased Generators in NC 0. Random Struct. Algorithms 29(1), 56–81 (2006)
Nyberg, K.: Constructions of Bent Functions and Difference Sets. In: Damgård, I.B. (ed.) EUROCRYPT 1990. LNCS, vol. 473, pp. 151–160. Springer, Heidelberg (1991)
Nyberg, K.: Perfect Nonlinear S-Boxes. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 378–386. Springer, Heidelberg (1991)
Robshaw, M., Billet, O.: New Stream Cipher Designs. LNCS, vol. 4986. Springer, Heidelberg (2008)
Rothaus, O.S.: On bent functions. Journal of Combinatorial Theory (A) 20, 300–305 (1976)
Rueppel, R.A.: Correlation immunity and the summation generator. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 260–272. Springer, Heidelberg (1986)
Shannon, C.E.: Communication theory of secrecy systems. Bell System Technical Journal 27, 656–715 (1949)
Siegenthaler, T.: Decrypting a class of stream ciphers using ciphertext only. IEEE Trans. on Computers C-34, 81–85 (1985)
Siegenthaler, T.: Correlation immunity of nonlinear combining functions for cryptographic applications. IEEE Trans. Inform. 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)
Wang, D., Lu, P.: Geometrically Invariant Watermark Using Fast Correlation Attacks. In: Proceedings of IIH-MSP 2006, pp. 465–468. IEEE Computer Society, Los Alamitos (2006)
Zeng, K., Huang, M.: On the linear syndrome method in cryptoanalysis. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 469–478. Springer, Heidelberg (1990)
Zeng, K., Yang, C.H., Rao, T.R.N.: An improved linear syndrome algorithm in cryptanalysis with applications. In: Menezes, A., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol. 537, pp. 34–47. Springer, Heidelberg (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 International Association for Cryptologic Research
About this paper
Cite this paper
Meier, W. (2011). Fast Correlation Attacks: Methods and Countermeasures. In: Joux, A. (eds) Fast Software Encryption. FSE 2011. Lecture Notes in Computer Science, vol 6733. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21702-9_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-21702-9_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21701-2
Online ISBN: 978-3-642-21702-9
eBook Packages: Computer ScienceComputer Science (R0)