Paper 2018/810

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

Ling Song and Jian Guo

Abstract

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. ToSC 2018(3)
Keywords
KetjeXoodooKeccak-MACcube attackauxiliary variableMILP
Contact author(s)
songling @ ntu edu sg
History
2018-09-06: received
Short URL
https://ia.cr/2018/810
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/810,
      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.