Paper 2018/1082

An Algebraic Method to Recover Superpolies in Cube Attacks

Chen-Dong Ye and Tian Tian

Abstract

Cube attacks are an important type of key recovery attacks against NFSR-based cryptosystems. The key step in cube attacks closely related to key recovery is recovering superpolies. However, in the previous cube attacks including original, division property based, and correlation cube attacks, the algebraic normal form of superpolies could hardly be shown to be exact due to an unavoidable failure probability or a requirement of large time complexity. In this paper, we propose an algebraic method aiming at recovering the exact algebraic normal forms of superpolies practically. Our method is developed based on degree evaluation method proposed by Liu in Crypto-2017. As an illustration, we apply our method to Trivium. As a result, we recover the algebraic normal forms of some superpolies for the 818-, 835-, 837-, and 838-round Trivium. Based on these superpolies, on a large set of weak keys, we can recover at least five key bits equivalently for up to the 838-round Trivium with a complexity of about $2^{37}$. Besides, for the cube proposed by Liu in Crypto-2017 as a zero-sum distinguisher for the 838-round Trivium, it is proved that its superpoly is not zero-constant. Hopefully, our method would provide some new insights on cube attacks against NFSR-based ciphers.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
Triviumcube attackskey recovery attackdeterministic algorithms
Contact author(s)
ye_chendong @ 126 com
History
2019-09-20: revised
2018-11-09: received
See all versions
Short URL
https://ia.cr/2018/1082
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1082,
      author = {Chen-Dong Ye and Tian Tian},
      title = {An Algebraic Method to Recover Superpolies in Cube Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1082},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1082}},
      url = {https://eprint.iacr.org/2018/1082}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.