Cryptanalysis of the "Grain" family of stream ciphers

ABSTRACT

Let us have an NLFSR with the feedback function g(x) and an LFSR with the generating polynomial f(x). The function g(x) is a Boolean function on the state of the NLFSR and the LFSR, at any time instance t. Whenever the LFSR has good statistical properties, it is used for controlling the randomness of the NLFSR's state machine. In this paper we define and study the general class of "Grain" family of stream ciphers, where the keystream bits are generated by another Boolean function h(y) on the states of the NLFSR and the LFSR. We show that the cryptographic strength of this family is related to the general decoding problem, when a key-recovering attack is considered. A proper choice of the functions f(·), g(·) and h(·) could, potentially, give us a strong instance of a stream cipher. One of such stream ciphers Grain was recently proposed as a candidate for the European project ECRYPT in May, 2005. Grain uses the secret key of length 80 bits and its internal state is of size 160 bits. It was suggested as a fast and small primitive for efficient hardware implementation. In our work we propose the analysis of such structures in general, and, in particular, we give a linear distinguishing attack on Grain with time complexity O(2⁵⁴), when O(2⁵¹) bits of the keystream is available. This is the first paper presenting an attack on Grain, and it reveals a leakage in the choice of the functions in this particular design instance.

REFERENCES

• 1: Joan Daemen , Vincent Rijmen, The Design of Rijndael, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 2: N. Smart. Cryptography: An Introduction, 2003.
• 3: J.D. Golić. Linear statistical weakness of alleged RC4 keystream generator. In W. Fumy, editor, Advances in Cryptology---EUROCRYPT'97, volume 1233 of Lecture Notes in Computer Science, pages 226--238. Springer--Verlag, 1997.
• 4: Scott R. Fluhrer , David A. McGrew, Statistical Analysis of the Alleged RC4 Keystream Generator, Proceedings of the 7th International Workshop on Fast Software Encryption, p.19-30, April 10-12, 2000
• 5: Itsik Mantin , Adi Shamir, A Practical Attack on Broadcast RC4, Revised Papers from the 8th International Workshop on Fast Software Encryption, p.152-164, April 02-04, 2001
• 6: S. Paul and B. Preneel. A new weekness in the RC4 keystream generator. In B. Roy and W. Meier, editors, Fast Software Encryption 2004, volume 3017 of Lecture Notes in Computer Science, pages 245--259. Springer--Verlag, 2004.
• 7: M. Briceno, I. Goldberg, and D. Wagner. A pedagogical implementation of A5/1. Available at http://jya.com/a51-pi.htm, Accessed August 18, 2003, 1999.
• 8: Alex Biryukov , Adi Shamir , David Wagner, Real Time Cryptanalysis of A5/1 on a PC, Proceedings of the 7th International Workshop on Fast Software Encryption, p.1-18, April 10-12, 2000
• 9: A. Maximov, T. Johansson, and S. Babbage. An improved correlation attack on A5/1. In Selected Areas in Cryptography---SAC 2004, Lecture Notes in Computer Science. Springer--Verlag, 2004.
• 10: S. Vaudenay Y. Lu, W. Meier. The Conditional Correlation Attack: A Practical Attack on Bluetooth Encryption. In Advances in Cryptology---CRYPTO 2005, volume 3621 of Lecture Notes in Computer Science, pages 97--117. Springer--Verlag, 2005.
• 11: NESSIE. New European Schemes for Signatures, Integrity, and Encryption. Available at http://www.cryptonessie.org, Accessed August 18, 2003, 1999.
• 12: ECRYPT. eSTREAM: ECRYPT Stream Cipher Project, IST-2002-507932. Available at http://www.ecrypt. eu.org/stream/, Accessed September 29, 2005, 2005.
• 13: M. Hell, T. Johansson, and W. Meier. Grain - A Stream Cipher for Constrained Environments. ECRYPT/eSTREAM Archive, Report 2005/010, 2005. http://www.ecrypt.eu.org/stream/ciphers/grain/grain.pdf.
• 14: Thomas Johansson and Fredrik Jönsson. On the complexity of some cryptographic problems based on the general decoding problem. IEEE Transactions on Information Theory, 48(10):2669--2678, 2002.
• 15: Mitsuru Matsui, Linear cryptanalysis method for DES cipher, Workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.386-397, January 1994, Lofthus, Norway
• 16: T. Siegenthaler. Correlation-immunity of non-linear combining functions for cryptographic applications. IEEE Transactions on Information Theory, 30:776--780, 1984.
• 17: C.E. Shannon. Communication theory of secrecy systems. Bell System Technical Journal, 27:656--715, 1949.
• 18: Thomas Johansson , Fredrik Jönsson, Fast Correlation Attacks Based on Turbo Code Techniques, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.181-197, August 15-19, 1999
• 19: Thomas Johansson , Fredrik Jönsson, Fast Correlation Attacks through Reconstruction of Linear Polynomials, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.300-315, August 20-24, 2000
• 20: Vladimor V. Chepyzhov , Thomas Johansson , Ben Smeets, A Simple Algorithm for Fast Correlation Attacks on Stream Ciphers, Proceedings of the 7th International Workshop on Fast Software Encryption, p.181-195, April 10-12, 2000
• 21: Miodrag J. Mihaljevic , Marc P. C. Fossorier , Hideki Imai, Fast Correlation Attack Algorithm with List Decoding and an Application, Revised Papers from the 8th International Workshop on Fast Software Encryption, p.196-210, April 02-04, 2001
• 22: Philippe Chose , Antoine Joux , Michel Mitton, Fast Correlation Attacks: An Algorithmic Point of View, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.209-221, May 02, 2002
• 23: Håkan Englund and Thomas Johansson. A new simple technique to attack filter generators and related ciphers. In Selected Areas in Cryptography, pages 39--53, 2004.
• 24: W. T. Penzhorn , G. J. Kühn, Computation of Low-Weight Parity Checks for Correlation Attacks on Stream Ciphers, Proceedings of the 5th IMA Conference on Cryptography and Coding, p.74-83, December 18-20, 1995
• 25: T. Siegenthaler. Decrypting a class of stream ciphers using ciphertext only. IEEE Transactions on Computers, 34:81--85, 1985.
• 26: W. Meier , O. Staffelbach, Fast correlation attacks on stream ciphers, Lecture Notes in Computer Science on Advances in Cryptology-EUROCRYPT'88, p.301-314, April 1988, Davos, Switzerland
• 27: Willi Meier , Othmar Staffelbach, Fast correlation attacks on certain stream ciphers, Journal of Cryptology, v.1 n.3, p.159-176, 1989 [doi>10.1007/BF02252874]
• 28: Miodrag J. Mihaljevic , Jovan D. Golic, A fast iterative algorithm for a shift register initial state reconstruction given the noisy output sequence, Proceedings of the international conference on cryptology on Advances in cryptology, p.165-175, September 1990, Sydney, Australia
• 29: V. Chepyzhov and B. Smeets. On a fast correlation attack on certain stream ciphers. In D. W. Davies, editor, Advances in Cryptology---EUROCRYPT'91, volume 547 of Lecture Notes in Computer Science, pages 176--185. Springer--Verlag, 1991.
• 30: F. Jönsson. Some Results on Fast Correlation Attacks. PhD thesis, Lund University, Department of Information Technology, P.O. Box 118, SE--221 00, Lund, Sweden, 2002.

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Code breaking

General Terms:
Design, Security

Keywords:
correlation attacks, cryptanalysis, decoding problem, distinguisher, grain