A Chosen IV Related Key Attack on Grain-128a

详细信息    查看全文

• 作者：Subhadeep Banik (17)
  Subhamoy Maitra (17)
  Santanu Sarkar (18)
  Turan Meltem S?nmez (18)
  
• 关键词：Cryptanalysis ; eStream ; Grain ; 128a ; Related Keys ; Stream Cipher
• 刊名：Lecture Notes in Computer Science
• 出版年：2013
• 出版时间：2013
• 年：2013
• 卷：7959
• 期：1
• 页码：27-40
• 全文大小：219KB
• 参考文献：1. The ECRYPT Stream Cipher Project. eSTREAM Portfolio of Stream Ciphers (Revised on September 8, 2008)
  2. ?gren, M., Hell, M., Johansson, T., Meier, W.: A New Version of Grain-128 with Authentication. In: Symmetric Key Encryption Workshop 2011, DTU, Denmark (February 2011)
  3. ?gren, M., Hell, M., Johansson, T., Meier, W.: Grain-128a: A New Version of Grain-128 with Optional Authentication. IJWMC?5(1), 48-9 (2011); This is the journal version of [2] CrossRef
  4. Aumasson, J.P., Dinur, I., Henzen, L., Meier, W., Shamir, A.: Efficient FPGA Implementations of High-Dimensional Cube Testers on the Stream Cipher Grain-128. In: SHARCS - Special-purpose Hardware for Attacking Cryptographic Systems (2009)
  5. Aumasson, J.P., Henzen, L., Meier, W., Naya-Plasencia, M.: Quark: A Lightweight Hash. Journal of Cryptology?26(2), 313-39 (2013) CrossRef
  6. Banik, S., Maitra, S., Sarkar, S.: Some Results on Related Key-IV Pairs of Grain. In: Bogdanov, A., Sanadhya, S. (eds.) SPACE 2012. LNCS, vol.?7644, pp. 94-10. Springer, Heidelberg (2012) CrossRef
  7. Berbain, C., Gilbert, H., Maximov, A.: Cryptanalysis of Grain. In: Robshaw, M. (ed.) FSE 2006. LNCS, vol.?4047, pp. 15-9. Springer, Heidelberg (2006) CrossRef
  8. Bj?rstad, T.E.: Cryptanalysis of Grain using Time/Memory/Data tradeoffs (v1.0 / February 25, 2008), http://www.ecrypt.eu.org/stream
  9. De Cannière, C., Kü?ük, ?., Preneel, B.: Analysis of Grain’s Initialization Algorithm. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol.?5023, pp. 276-89. Springer, Heidelberg (2008) CrossRef
  10. De Cannière, C., Dunkelman, O., Kne?evi?, M.: KATAN and KTANTAN -A family of small and efficient hardware-oriented block ciphers. In: Clavier, C., Gaj, K. (eds.) CHES 2009. LNCS, vol.?5747, pp. 272-88. Springer, Heidelberg (2009) CrossRef
  11. Dinur, I., Güneysu, T., Paar, C., Shamir, A., Zimmermann, R.: An Experimentally Verified Attack on Full Grain-128 Using Dedicated Reconfigurable Hardware. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol.?7073, pp. 327-43. Springer, Heidelberg (2011) CrossRef
  12. Dinur, I., Shamir, A.: Breaking Grain-128 with Dynamic Cube Attacks. In: Joux, A. (ed.) FSE 2011. LNCS, vol.?6733, pp. 167-87. Springer, Heidelberg (2011) CrossRef
  13. Englund, H., Johansson, T., S?nmez Turan, M.: A Framework for Chosen IV Statistical Analysis of Stream Ciphers. In: Srinathan, K., Rangan, C.P., Yung, M. (eds.) INDOCRYPT 2007. LNCS, vol.?4859, pp. 268-81. Springer, Heidelberg (2007) CrossRef
  14. Fischer, S., Khazaei, S., Meier, W.: Chosen IV Statistical Analysis for Key Recovery Attacks on Stream Ciphers. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol.?5023, pp. 236-45. Springer, Heidelberg (2008) CrossRef
  15. Fredricksen, H.: A Survey of Full Length Nonlinear Shift Register Cycle Algorithms. SIAM Rev.?24, 195-21 (1982) CrossRef
  16. Hell, M., Johansson, T., Meier, W.: Grain - A Stream Cipher for Constrained Environments. ECRYPT Stream Cipher Project Report 2005/001 (2005), http://www.ecrypt.eu.org/stream
  17. Hell, M., Johansson, T., Maximov, A., Meier, W.: A Stream Cipher Proposal: Grain-128. In: IEEE International Symposium on Information Theory, ISIT 2006 (2006)
  18. Khazaei, S., Hassanzadeh, M., Kiaei, M.: Distinguishing Attack on Grain. ECRYPT Stream Cipher Project Report 2005/071 (2005), http://www.ecrypt.eu.org/stream
  19. Knellwolf, S., Meier, W., Naya-Plasencia, M.: Conditional Differential Cryptanalysis of NLFSR-based Cryptosystems. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol.?6477, pp. 130-45. Springer, Heidelberg (2010) CrossRef
  20. Lee, Y., Jeong, K., Sung, J., Hong, S.: Related-Key Chosen IV Attacks on Grain-v1 and Grain-128. In: Mu, Y., Susilo, W., Seberry, J. (eds.) ACISP 2008. LNCS, vol.?5107, pp. 321-35. Springer, Heidelberg (2008) CrossRef
  21. Soos, M.: CryptoMiniSat-2.9.5, http://www.msoos.org/cryptominisat2/
  22. Stankovski, P.: Greedy Distinguishers and Nonrandomness Detectors. In: Gong, G., Gupta, K.C. (eds.) INDOCRYPT 2010. LNCS, vol.?6498, pp. 210-26. Springer, Heidelberg (2010) CrossRef
  23. Stein, W.: Sage Mathematics Software. Free Software Foundation, Inc. (2009), http://www.sagemath.org (Open source project initiated by W. Stein and contributed by many)
  24. Zhang, B., Li, Z.: Near Collision Attack on the Grain v1 Stream Cipher. To appear in FSE 2013 (2013)
  25. Zhang, H., Wang, X.: Cryptanalysis of Stream Cipher Grain Family. IACR Cryptology ePrint Archive 2009: 109 (2009), http://eprint.iacr.org/2009/109
  
• 作者单位：Subhadeep Banik (17)
  Subhamoy Maitra (17)
  Santanu Sarkar (18)
  Turan Meltem S?nmez (18)
  
  17. Applied Statistics Unit, Indian Statistical Institute Kolkata, 203, B.T. Road, Kolkata, 108, India
  18. National Institute of Standards and Technology, 100 Bureau Drive, Stop 8930, Gaithersburg, MD, 20899-8930, USA
  
• ISSN：1611-3349

文摘

Due to the symmetric padding used in the stream cipher Grain v1 and Grain-128, it is possible to find Key-IV pairs that generate shifted keystreams efficiently. Based on this observation, Lee et al. presented a chosen IV related Key attack on Grain v1 and Grain-128 at ACISP 2008. Later, the designers introduced Grain-128a having an asymmetric padding. As a result, the existing idea of chosen IV related Key attack does not work on this new design. In this paper, we present a Key recovery attack on Grain-128a, in a chosen IV related Key setting. We show that using around γ·232 (γ is a experimentally determined constant and it is sufficient to estimate it as 28) related Keys and γ·264 chosen IVs, it is possible to obtain 32·γ simple nonlinear equations and solve them to recover the Secret Key in Grain-128a.