Paper 2023/1870

An Improved Method for Evaluating Secret Variables and Its Application to WAGE

Weizhe Wang, Shanghai Jiao Tong University
Haoyang Wang, Shanghai Jiao Tong University
Deng Tang, Shanghai Jiao Tong University

The cube attack is a powerful cryptanalysis technique against symmetric ciphers, especially stream ciphers. The adversary aims to recover secret key bits by solving equations that involve the key. To simplify the equations, a set of plaintexts called a cube is summed up together. Traditional cube attacks use only linear or quadratic superpolies, and the size of cube is limited to an experimental range, typically around 40. However, cube attack based on division property, proposed by Todo et al. at CRYPTO 2017, overcomes these limitations and enables theoretical cube attacks on many lightweight stream ciphers. For a given cube $I$, they evaluate the set $J$ of secret key bits involved in the superpoly and require $2^{|I|+|J|}$ encryptions to recover the superpoly. However, the secret variables evaluation method proposed by Todo et al. sometimes becomes unresponsive and fails to solve within a reasonable time. In this paper, we propose an improvement to Todo's method by breaking down difficult-to-solve problems into several smaller sub-problems. Our method retains the efficiency of Todo's method while effectively avoiding unresponsive situations. We apply our method to the WAGE cipher, an NLFSR-based authenticated encryption algorithm and one of the second round candidates in the NIST LWC competition. Specifically, we successfully mount cube attacks on 29-round WAGE, as well as on 24-round WAGE with a sponge constraint. To the best of our knowledge, this is the first cube attack against the WAGE cipher, which provides a more accurate characterization of the WAGE's resistance against algebraic attacks.

Note: This is the version accepted by INSCRYPT 2023.

Available format(s)
Attacks and cryptanalysis
Publication info
Published elsewhere. INSCRYPT 2023
Cube attackDivision propertyWAGEMILP
Contact author(s)
SJTUwwz @ sjtu edu cn
haoyang wang @ sjtu edu cn
dtang @ foxmail com
2023-12-06: approved
2023-12-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Weizhe Wang and Haoyang Wang and Deng Tang},
      title = {An Improved Method for Evaluating Secret Variables and Its Application to WAGE},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1870},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.