eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2018/810

Cube-Attack-Like Cryptanalysis of Round-Reduced Keccak Using MILP

Ling Song and Jian Guo


Cube-attack-like cryptanalysis on round-reduced Keccak was proposed by Dinur et al. at EUROCRYPT 2015. It recovers the key through two phases: the preprocessing phase for precomputing a look-up table and online phase for querying the output and getting the cube sum with which the right key can be retrieved by looking up the precomputed table. It was shown that such attacks are efficient specifically for Keccak-based constructions with small nonce or message block size. In this paper, we provide a mixed integer linear programming (MILP) model for cube-attack-like cryptanalysis on keyed Keccak, which does not impose any unnecessary constraint on cube variables and finds almost optimal cubes by balancing the two phases of cube-attack-like cryptanalysis. Our model is applied to Ketje Jr, Ketje Sr, a Xoodoo-based authenticated encryption and Keccak-MAC-512, all of which have a relatively small nonce or message block size. As a result, time complexities of 5-round attacks on Ketje Jr and 7-round attacks on Ketje Sr can be improved significantly. Meanwhile, 6-round attacks, one more round than the previous best attack, are possible if the key size of Ketje V1 (V2) is reduced to 72 (80) bits. For Xoodoo-based AE in Ketje style, the attack reaches 6 rounds. Additionally, a 7-round attack of Keccak-MAC-512 is achieved. To verify the correctness of our attacks, a 5-round attack on Ketje V1 is implemented and tested practically. It is noted that this work does not threaten the security of any Keccak-based construction.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. ToSC 2018(3)
KetjeXoodooKeccak-MACcube attackauxiliary variableMILP
Contact author(s)
songling @ ntu edu sg
2018-09-06: received
Short URL
Creative Commons Attribution


      author = {Ling Song and Jian Guo},
      title = {Cube-Attack-Like Cryptanalysis of Round-Reduced Keccak Using MILP},
      howpublished = {Cryptology ePrint Archive, Paper 2018/810},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/810}},
      url = {https://eprint.iacr.org/2018/810}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.