Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Internal state recovery of Grain v1 employing guess-and-determine attack

  • Author(s): Zhen Ma 1, 2 1, 2 ; Tian Tian 2 1 ; Wen-Feng Qi 2 1
    • View affiliations
    • Affiliations: 1: State Key Laboratory of Cryptology, Beijing, People's Republic of China ;
      2: National Digital Switching System Engineering and Technological Research Center, 62 Kexue Road, Zhengzhou, People's Republic of China
  • Source: Volume 11, Issue 6, November 2017, p. 363 – 368
    DOI:  10.1049/iet-ifs.2017.0232 , Print ISSN 1751-8709, Online ISSN 1751-8717
© The Institution of Engineering and Technology
Received 09/05/2017, Accepted 24/06/2017, Revised 23/06/2017, Published 29/06/2017

The well-known stream cipher Grain v1 is one of the finalists of European eSTREAM project. In this study, a novel guess-and-determine attack on Grain v1 is introduced. The attack primarily employs a new conditional BSW sampling technique and the main creative idea is that the conditions are set not only on state bits but also on the updates of the registers for the BSW sampling technique. It is shown that using this technique we can further reduce the sampling resistance of Grain v1 to which is the best result so far. The attack leads to an efficient internal state recovery of Grain v1 with only online time employing a memory of , requiring keystreams each of length and preprocessing time. It is shown that these figures are obviously better compared with the previous results. This is also the first attempt to control the updates of the registers of Grain v1 in the guess-and-determine attack and hopefully this provides new insights for cryptanalysis on such compact stream ciphers.

Inspec keywords: system recovery; sampling methods; cryptography

Other keywords: sampling resistance reduction; stream cipher Grain v1; internal state recovery; cryptanalysis; European eSTREAM project; conditional BSW sampling technique; guess-and-determine attack

Subjects: Other topics in statistics; Cryptography; Other topics in statistics; Cryptography theory

References

    1. 1)
      • 15. Briyukov, A., Shamir, A., Wagner, D.: ‘Real time cryptanalysis of A5/1 on a PC’. 7th Int. Workshop Proc. Fast Software Encryption,(FSE 2000), New York, USA, April 2000 (LNCS, 1978), pp. 1–18.
    2. 2)
      • 7. Banik, S., Maitra, S., Sarkar, S.: ‘A differential fault attack on the Grain family of stream ciphers’. Proc. Cryptographic Hardware and Embedded Systems (CHES 2012), Leuven, Belgium, September 2012 (LNCS, 7428), pp. 122–139.
    3. 3)
      • 14. Biryukov, A., Shamir, A.: ‘Cryptanalytic Time/Memory/Data Tradeoffs for stream ciphers’. Proc. Advances in Cryptology – ASIACRYPT 2000, Kyoto, Japan, December 2000 (LNCS, 1976), pp. 1–13.
    4. 4)
      • 9. Banik, S., Maitra, S., Sarkar, S.: ‘Differential fault attack against Grain family with very few faults and minimal assumptions’, IEEE Trans. Comput., 2016, 64, (6), pp. 1647–1657.
    5. 5)
      • 8. Banik, S., Maitra, S., Sarkar, S.: ‘A differential fault attack on the Grain family under reasonable assumptions’. Proc. Progress in Cryptology – INDOCRYPT 2012, Kolkata, India, December 2012 (LNCS, 7668), pp. 191–208.
    6. 6)
      • 5. Mihaljević, M.J., Gangopadhyay, S., Paul, G., et al: ‘Internal state recovery of Grain v1 employing normality order of the filter function’, IET Inf. Secur., 2012, 6, (2), pp. 55–64.
    7. 7)
      • 1. Hell, M., Johansson, T., Meier, W.: ‘Grain: a stream cipher for constrained environments’, Int. J. Wirel. Mobile Comput. (IJWMC), 2007, 2, (1), pp. 86–93.
    8. 8)
      • 10. Lee, Y., Jeong, K., Sung, J., et al: ‘Related-key chosen IV attacks on Grain v1 and Grain-128’. Proc. Information Security and Privacy, 13th Australasian Conf. (ACISP 2008), Wollongong, Australia, July 2008 (LNCS, 5107), pp. 321–335.
    9. 9)
      • 12. Babbage, S.: ‘Improved ‘exhaustive search’ attacks on stream ciphers’. Proc. European Convention on Security and Detection, Brighton, UK, May 1995, pp. 161–166.
    10. 10)
      • 6. Jiao, L., Zhang, B., Wang, M.: ‘Two generic methods of analyzing stream ciphers’. Proc. Information Security Conf. (ISC 2015), Trondheim, Norway, September 2015 (LNCS, 9290), pp. 379–396.
    11. 11)
      • 4. Bjørstad, T.E.: ‘Cryptanalysis of Grain using Time/Memory/Data tradeoffs’. Available at http://www.ecrypt.eu.org/stream/papersdir/2008/012.pdf, accessed June 2017.
    12. 12)
      • 3. Ma, Z., Tian, T., Qi, W.: ‘Improved conditional differential attacks on Grain v1’, IET Inf. Secur., 2017, 11, (1), pp. 46–53.
    13. 13)
      • 11. Hellman, M.: ‘A cryptanalytic time-memory trade-off’, IEEE Trans. Inf. Theory, 1980, 26, (4), pp. 401–406.
    14. 14)
      • 13. Golić, J.D.: ‘Cryptanalysis of alleged A5 stream cipher’. Proc. Advances in Cryptology – EUROCRYPT 1997, Konstanz, Germany, May 1997 (LNCS, 1233), pp. 239–255.
    15. 15)
      • 2. Knellwolf, S., Meier, W., Naya-Plasencia, M.: ‘Conditional Differential Cryptanalysis of NLFSR-based Cryptosystems’. Proc. Advances in Cryptology – ASIACRYPT 2010, Singapore, December 2010 (LNCS, 6477), pp. 130–145.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2017.0232
Loading

Related content

content/journals/10.1049/iet-ifs.2017.0232
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address