Open AccessAlgebraic method to recover superpolies in cube attacks
Author(s) -
Ye ChenDong,
Tian Tian
Publication year - 2020
Publication title -
iet information security
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.308
H-Index - 34
eISSN - 1751-8717
pISSN - 1751-8709
DOI - 10.1049/iet-ifs.2019.0323
Subject(s) - cube (algebra) , algebraic number , computer science , key (lock) , cryptosystem , algorithm , theoretical computer science , mathematics , cryptography , combinatorics , computer security , mathematical analysis
Cube attacks are an important type of key recovery attacks against nonlinear feedback shift register (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 study, the authors propose an algebraic method aiming at recovering the exact algebraic normal forms of superpolies practically. The proposed method is developed based on the degree of evaluation method proposed by Liu in Crypto 2017. As an illustration, the authors apply the proposed method to Trivium. As a result, they recover the algebraic normal forms of some superpolies for the 818‐, 835‐, 837‐ and 838‐round Trivium. Based on these superpolies, the authors could mount key‐recovery attacks on 818‐, 835‐, 837‐ and 838‐round Trivium with the worst complexity slightly lower than a brute‐force attack. 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, the proposed method would provide some new insights on cube attacks against NFSR‐based ciphers.