Algebraic method to recover superpolies in cube attacks. (1st July 2020)

• Record Type: Journal Article
• Authors: Ye, Chen‐Dong; Tian, Tian
• Is Part Of: IET information security. Volume 14:Number 4(2020)
• Page Start: 430
• Page End: 441
• Publication Date: 2020-07-01
• Subjects: probability -- cryptography -- algebra; previous cube attacks -- division property -- correlation cube attacks -- algebraic normal form -- algebraic method -- exact algebraic normal forms -- Trivium -- key‐recovery attacks -- brute‐force attack -- key recovery attacks -- NFSR‐based cryptosystems; Computer security -- Periodicals; Cryptography -- Periodicals; Computer networks -- Security measures -- Periodicals; Database security -- Periodicals; 005.8
• DOI: 10.1049/iet-ifs.2019.0323
• Languages: English
• ISSNs: 1751-8709

Abstract

Abstract : 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.