Paper 2017/306

Cube Attacks on Non-Blackbox Polynomials Based on Division Property (Full Version)

Yosuke Todo, Takanori Isobe, Yonglin Hao, and Willi Meier

Abstract

The cube attack is a powerful cryptanalytic technique and is especially powerful against stream ciphers. Since we need to analyze the complicated structure of a stream cipher in the cube attack, the cube attack basically analyzes it by regarding it as a blackbox. Therefore, the cube attack is an experimental attack, and we cannot evaluate the security when the size of cube exceeds an experimental range, e.g., 40. In this paper, we propose cube attacks on non-blackbox polynomials. Our attacks are developed by using the division property, which is recently applied to various block ciphers. The clear advantage is that we can exploit large cube sizes because it never regards the cipher as a blackbox. We apply the new cube attack to Trivium, Grain128a, ACORN and Kreyvium. As a result, the secret keys of 832-round Trivium, 183-round Grain128a, 704-round ACORN and 872-round Kreyvium are recovered. These attacks are the current best key-recovery attack against these ciphers.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2017
Keywords
Cube attackStream cipherDivision propertyHigher-order differential cryptanalysisMILPTriviumGrain128aACORN
Contact author(s)
todo yosuke @ lab ntt co jp
History
2017-10-25: last of 3 revisions
2017-04-10: received
See all versions
Short URL
https://ia.cr/2017/306
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/306,
      author = {Yosuke Todo and Takanori Isobe and Yonglin Hao and Willi Meier},
      title = {Cube Attacks on Non-Blackbox Polynomials Based on Division Property (Full Version)},
      howpublished = {Cryptology ePrint Archive, Paper 2017/306},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/306}},
      url = {https://eprint.iacr.org/2017/306}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.