Links between Division Property and Other Cube Attack Variants

  • Yonglin Hao State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878, China
  • Lin Jiao State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878, China
  • Chaoyun Li imec - Computer Security and Industrial Cryptography (COSIC) research group, Department of Electrical Engineering (ESAT), KU Leuven, Leuven, Belgium
  • Willi Meier University of Applied Sciences and Arts Northwestern Switzerland (FHNW), Windisch, Switzerland
  • Yosuke Todo NTT Secure Platform Laboratories, Tokyo 180-8585, Japan
  • Qingju Wang Interdisciplinary Centre for Security, Reliability and Trust (SnT), University of Luxembourg, Esch-sur-Alzette, Luxembourg
Keywords: Stream ciphers, Division property, Dynamic cube attack, Cube tester, MILP, Grain-128, Kreyvium, ACORN

Abstract

A theoretically reliable key-recovery attack should evaluate not only the non-randomness for the correct key guess but also the randomness for the wrong ones as well. The former has always been the main focus but the absence of the latter can also cause self-contradicted results. In fact, the theoretic discussion of wrong key guesses is overlooked in quite some existing key-recovery attacks, especially the previous cube attack variants based on pure experiments. In this paper, we draw links between the division property and several variants of the cube attack. In addition to the zero-sum property, we further prove that the bias phenomenon, the non-randomness widely utilized in dynamic cube attacks and cube testers, can also be reflected by the division property. Based on such links, we are able to provide several results: Firstly, we give a dynamic cube key-recovery attack on full Grain-128. Compared with Dinur et al.’s original one, this attack is supported by a theoretical analysis of the bias based on a more elaborate assumption. Our attack can recover 3 key bits with a complexity 297.86 and evaluated success probability 99.83%. Thus, the overall complexity for recovering full 128 key bits is 2125. Secondly, now that the bias phenomenon can be efficiently and elaborately evaluated, we further derive new secure bounds for Grain-like primitives (namely Grain-128, Grain-128a, Grain-V1, Plantlet) against both the zero-sum and bias cube testers. Our secure bounds indicate that 256 initialization rounds are not able to guarantee Grain-128 to resist bias-based cube testers. This is an efficient tool for newly designed stream ciphers for determining the number of initialization rounds. Thirdly, we improve Wang et al.’s relaxed term enumeration technique proposed in CRYPTO 2018 and extend their results on Kreyvium and ACORN by 1 and 13 rounds (reaching 892 and 763 rounds) with complexities 2121.19 and 2125.54 respectively. To our knowledge, our results are the current best key-recovery attacks on these two primitives.

Published
2020-05-07
How to Cite
Hao, Y., Jiao, L., Li, C., Meier, W., Todo, Y., & Wang, Q. (2020). Links between Division Property and Other Cube Attack Variants. IACR Transactions on Symmetric Cryptology, 2020(1), 363-395. https://doi.org/10.13154/tosc.v2020.i1.363-395
Section
Articles