Paper 2017/1063

Improved Division Property Based Cube Attacks Exploiting Algebraic Properties of Superpoly (Full Version)

Qingju Wang, Yonglin Hao, Yosuke Todo, Chaoyun Li, Takanori Isobe, and Willi Meier

Abstract

The cube attack is an important technique for the cryptanalysis of symmetric key primitives, especially for stream ciphers. Aiming at recovering some secret key bits, the adversary reconstructs a superpoly with the secret key bits involved, by summing over a set of the plaintexts/IV which is called a cube. Traditional cube attack only exploits linear/quadratic superpolies. Moreover, for a long time after its proposal, the size of the cubes has been largely confined to an experimental range, e.g., typically 40. These limits were first overcome by the division property based cube attacks proposed by Todo et al. at CRYPTO 2017. Based on MILP modelled division property, for a cube (index set) $I$, they identify the small (index) subset $J$ of the secret key bits involved in the resultant superpoly. During the precomputation phase which dominates the complexity of the cube attacks, $2^{|I|+|J|}$ encryptions are required to recover the superpoly. Therefore, their attacks can only be available when the restriction $|I|+|J|<n$ is met. In this paper, we introduced several techniques to improve the division property based cube attacks by exploiting various algebraic properties of the superpoly. 1. We propose the ``flag'' technique to enhance the preciseness of MILP models so that the proper non-cube IV assignments can be identified to obtain a non-constant superpoly. 2. A degree evaluation algorithm is presented to upper bound the degree of the superpoly. With the knowledge of its degree, the superpoly can be recovered without constructing its whole truth table. This enables us to explore larger cubes $I$'s even if $|I|+|J|\geq n$. 3. We provide a term enumeration algorithm for finding the monomials of the superpoly, so that the complexity of many attacks can be further reduced. As an illustration, we apply our techniques to attack the initialization of several ciphers. To be specific, our key recovery attacks have mounted to 839-round TRIVIUM, 891-round Kreyvium, 184-round Grain-128a and 750-round ACORN respectively.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in CRYPTO 2018
Keywords
secret-keyCube attackDivision PropertyMILPTRIVIUMKreyviumGrain-128aACORNClique
Contact author(s)
qingju wang @ uni lu
haoyonglin @ yeah net
takanori isobe1 @ gmail com
willi meier @ fhnw ch
History
2018-05-23: last of 2 revisions
2017-11-09: received
See all versions
Short URL
https://ia.cr/2017/1063
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1063,
      author = {Qingju Wang and Yonglin Hao and Yosuke Todo and Chaoyun Li and Takanori Isobe and Willi Meier},
      title = {Improved Division Property Based Cube Attacks Exploiting Algebraic Properties of Superpoly (Full Version)},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1063},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1063}},
      url = {https://eprint.iacr.org/2017/1063}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.