Paper 2019/1226

Cube Cryptanalysis of Round-Reduced ACORN

Jingchun Yang, Meicheng Liu, and Dongdai Lin

Abstract

The cube attack is one of the most powerful techniques in cryptanalysis of symmetric cryptographic primitives. The basic idea of cube attack is to determine the value of a polynomial in key bits by summing over a cube (a subset of public variables, e.g., plaintext bits or IV bits). If the degree of the polynomial is relatively low, then we can obtain a low-degree equation in key bits, thus may contribute to reducing the complexity of key recovery. In this paper, we use cube cryptanalysis to analyze the authenticated stream cipher ACORN (one of the 6 algorithms in the final portfolio of the CAESAR competition), and give some new results in both distinguishing attacks and key recovery attacks. Firstly, we give a new method of finding cube testers, which is based on the greedy algorithm of finding cubes, and the numeric mapping method for estimating the algebraic degree of NFSR-based cryptosystems. We apply it to ACORN, and obtain the best practical distinguishing attacks for its 690-round variant using a cube of size 38, and its 706-round variant using a cube of size 46. Then we theoretically analyze the security bound of ACORN via the division property based cube attack. By exploiting the embedded property, we find some new distinguishers for ACORN, so the zero-sum property of the output of its 775-round variant can be observed with a complexity of $2^{127}$. Finally, we propose a key recovery attack on ACORN reduced to 772 rounds. The time complexity to recover the linear superpoly of the 123-dimensional cube is $2^{127.46}$. As far as we know, this is the best key recovery attack on round-reduced ACORN. It is also worth noting that this work does not threaten the security of ACORN.

Metadata
Available format(s)
-- withdrawn --
Category
Secret-key cryptography
Publication info
Published elsewhere. ISC 2019
DOI
10.1007/978-3-030-30215-3_3
Keywords
cube cryptanalysisACORNdistinguishing attackkey recoverynumeric mappingdivision property based cube attack
Contact author(s)
yangjingchun @ iie ac cn
liumeicheng @ iie ac cn
History
2020-11-21: withdrawn
2019-10-21: received
See all versions
Short URL
https://ia.cr/2019/1226
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.