Cryptology ePrint Archive: Report 2017/306

Cube Attacks on Non-Blackbox Polynomials Based on Division Property

Yosuke Todo, Takanori Isobe, Yonglin Hao, Willi Meier

Abstract: The cube attack is one of powerful cryptanalytic techniques 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 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 number of cube size because it never regards the cipher as a blackbox. We apply the new cube attack to Trivium, Grain128a, and ACORN. As a result, the secret keys of 832-round Trivium, 183-round Grain128a, and 704-round ACORN are recovered. These attacks are the current best key-recovery attack.

Category / Keywords: secret-key cryptography / Cube attack, Stream cipher, Division property, Higher-order differential cryptanalysis, MILP, Trivium, Grain128a, ACORN

Original Publication (with minor differences): IACR-CRYPTO-2017

Date: received 7 Apr 2017, last revised 19 Sep 2017

Contact author: todo yosuke at lab ntt co jp

Available format(s): PDF | BibTeX Citation

Version: 20170920:003751 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]