Article (Scientific journals)
Improved Division Property Based Cube Attacks Exploiting Algebraic Properties of Superpoly
WANG, Qingju; Hao, Honglin; Todo, Yosuke et al.
2019In IEEE Transactions on Computers, 68 (10), p. 1470-1486
Peer Reviewed verified by ORBi
 

Files


Full Text
main.pdf
Author preprint (565.75 kB)
Download

All documents in ORBilu are protected by a user license.

Send to



Details



Keywords :
stream cipher; cube attack; division property
Abstract :
[en] At CRYPTO 2017 and IEEE Transactions on Computers in 2018, Todo et al. proposed the division property based cube attack method making it possible to launch cube attacks with cubes of dimensions far beyond practical reach. However, assumptions are made to validate their attacks. In this paper, we further formulate the algebraic properties of the superpoly in one framework to facilitate cube attacks in more successful applications: we propose the “flag” technique to enhance the precision of MILP models, which enable us to identify proper non-cube IV assignments; a degree evaluation algorithm is presented to upper bound the degree of the superpoly s.t. the superpoly can be recovered without constructing its whole truth table and overall complexity of the attack can be largely reduced; we provide a divide-and-conquer strategy to Trivium-like stream ciphers namely Trivium, Kreyvium, TriviA-SC1/2 so that the large scale MILP models can be split into several small solvable ones enabling us to analyze Trivium-like primitives with more than 1000 initialization rounds; finally, we provide a term enumeration algorithm for finding the monomials of the superpoly, so that the complexity of many attacks can be further reduced. We apply our techniques to attack the initialization of several ciphers namely 839-round Trivium, 891-round Kreyvium, 1009-round TriviA-SC1, 1004-round TriviA-SC2, 184-round Grain-128a and 750-round Acorn respectively.
Research center :
Interdisciplinary Centre for Security, Reliability and Trust (SnT) > CryptoLUX
Disciplines :
Computer science
Author, co-author :
WANG, Qingju ;  University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT)
Hao, Honglin
Todo, Yosuke
Li, Chaoyun
Takanori, Isobe
Meier, Willi
External co-authors :
yes
Language :
English
Title :
Improved Division Property Based Cube Attacks Exploiting Algebraic Properties of Superpoly
Publication date :
2019
Journal title :
IEEE Transactions on Computers
ISSN :
0018-9340
eISSN :
1557-9956
Publisher :
Institute of Electrical and Electronics Engineers, Los Alamitos, United States - New York
Volume :
68
Issue :
10
Pages :
1470-1486
Peer reviewed :
Peer Reviewed verified by ORBi
Focus Area :
Security, Reliability and Trust
Name of the research project :
FDISC
Commentary :
This is an extended verison of the conference paper at CRYPTO 2018.
Available on ORBilu :
since 17 December 2019

Statistics


Number of views
105 (4 by Unilu)
Number of downloads
123 (0 by Unilu)

OpenAlex citations
 
18
WoS citations
 
7

Bibliography


Similar publications



Contact ORBilu