This study presents a dynamic cube attack on the algorithm Grain-v1 which has resisted all the key-recovery attacks in the single key model. The dynamic cube attack finds the secret key by using distinguishers obtained from structural weaknesses of a cipher. The main idea of the attack lies in simplifying the cipher's output function. After making it simpler, the attack is able to exploit a distinguishing attack to recover the secret key. In this study, the authors first find the appropriate simplifications for Grain-v1. Then, they apply their attack to the algorithm by using a new framework and a new smart choice technique for the classification of initial value bits. Finally, the authors simulate the attack to find the suitable attack parameters having 73% success rate. Their attack runs in a practical time and recovers all the key bits when the number of initialisation rounds in Grain-v1 is reduced to 100 of 160. The attack is faster than exhaustive search by a factor of 2³⁸.

References

1. 1)
  - 7. Dinur, I., Güneysu, T., Paar, C., et al: ‘An experimentally verified attack on full Grain-128 using dedicated reconfigurable hardware’. Advances in Cryptology – ASIACRYPT 2011, 2011, pp. 327–343.
2. 2)
  - 4. Dinur, I., Shamir, A.: ‘Cube attacks on tweakable black box polynomials’. Advances in Cryptology – EUROCRYPT 2009, 2009, pp. 278–299.
3. 3)
  - 1. Hell, M., Johansson, T., Meier, W.: ‘Grain a stream cipher for constrained environments’. eSTREAM, ECRYPT Stream Cipher Project, Report 2005/010, 2005.
4. 4)
  - 15. Graham, R.L., Shipman, G.M., Barrett, B.W., et al: ‘Open MPI: a high-performance, heterogeneous MPI’. IEEE Int. Conf. on Cluster Computing, 2006, pp. 1–9.
5. 5)
  - 2. Englund, H., Johansson, T., Sönmez Turan, M.: ‘A framework for chosen IV statistical analysis of stream ciphers’. Progress in Cryptology – INDOCRYPT 2007, 2007, pp. 268–281.
6. 6)
  - 11. Lee, Y., Jeong, K., Sung, J., et al: ‘Related-key chosen IV attacks on Grain-v1 and Grain-128’. Information Security and Privacy, 2008, pp. 321–335.
7. 7)
  - 9. Küçük, Ö.: ‘Slide resynchronization attack on the initialization of Grain 1.0’. eSTREAM, ECRYPT Stream Cipher Project, Report, 2006, vol. 44, p. 2006.
8. 8)
  - 13. Joux, A.: ‘Algorithmic cryptanalysis’ (CRC Press, 2009).
9. 9)
  - 12. Knellwolf, S., Meier, W., Naya-Plasencia, M.: ‘Conditional differential cryptanalysis of NLFSR-based cryptosystems’. Advances in Cryptology – ASIACRYPT 2010, 2010, pp. 130–145.
10. 10)
  - 5. Dinur, I., Shamir, A.: ‘Breaking Grain-128 with dynamic cube attacks’. Fast Software Encryption, 2011, pp. 167–187.
11. 11)
  - 8. Ågren, M., Hell, M., Johansson, T., et al: ‘A new version of Grain-128 with authentication’. Symmetric Key Encryption Workshop, SKEW (February 2011), 2011.
12. 12)
  - 10. De Cannière, C., Küçük, Ö., Preneel, B.: ‘Analysis of Grain's initialization algorithm’. Progress in Cryptology – AFRICACRYPT 2008, 2008, pp. 276–289.
13. 13)
  - 14. Quinn, M.: ‘Parallel programming in C with MPI and OpenMP’ (Tsinghua University Press, 2004).
14. 14)
  - 16. Kreher, D.L., Stinson, D.: ‘Combinatorial algorithms: generation, enumeration, and search’ (CRC Press series on discrete mathematics and its applications, CRC Press, 1999).
15. 15)
  - 6. Fischer, S., Khazaei, S., Meier, W.: ‘Chosen IV statistical analysis for key recovery attacks on stream ciphers’. Progress in Cryptology – AFRICACRYPT 2008, 2008, pp. 236–245.
16. 16)
  - 3. Aumasson, J.-P., Dinur, I., Meier, W., et al: ‘Cube testers and key recovery attacks on reduced-round MD6 and Trivium’. Fast Software Encryption, 2009, pp. 1–22.

Dynamic cube attack on Grain-v1

References

Related content