Paper 2017/1030

New MILP Modeling: Improved Conditional Cube Attacks on Keccak-based Constructions

Ling Song, Jian Guo, Danping Shi, and San Ling

Abstract

In this paper, we propose a new MILP modeling to find better or even optimal choices of conditional cubes, under the general framework of conditional cube attacks. These choices generally find new or improved attacks against the keyed constructions based on Keccak permutation and its variants, including Keccak-MAC, KMAC, Keyak, and Ketje, in terms of attack complexities or the number of attacked rounds. Interestingly, conditional cube attacks were applied to round-reduced Keccak-MAC, but not to KMAC despite the great similarity between Keccak-MAC and KMAC, and the fact that KMAC is the NIST standard way of constructing MAC from SHA-3. As examples to demonstrate the effectiveness of our new modeling, we report key recovery attacks against KMAC128 and KMAC256 reduced to 7 and 9 rounds, respectively; the best attack against Lake Keyak with 128-bit key is improved from 6 to 8 rounds in the nonce-respected setting and 9 rounds of Lake Keyak can be attacked if the key size is of 256 bits; attack complexity improvements are found generally on other constructions. Our new model is also applied to Keccak-based full-state keyed sponge and gives a positive answer to the open question proposed by Bertoni et al. whether cube attacks can be extended to more rounds by exploiting full-state absorbing. To verify the correctness of our attacks, reduced-variants of the attacks are implemented and verified on a PC practically. It is remarked that this work does not threaten the security of any full version of the instances analyzed in this paper.

Note: full version

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in ASIACRYPT 2018
Keywords
KeccakSHA-3KMACKeyakKetjeFull-stateConditional cube attackMILP
Contact author(s)
songling @ ntu edu sg
History
2018-09-14: last of 4 revisions
2017-10-28: received
See all versions
Short URL
https://ia.cr/2017/1030
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1030,
      author = {Ling Song and Jian Guo and Danping Shi and San Ling},
      title = {New MILP Modeling: Improved Conditional Cube Attacks on Keccak-based Constructions},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1030},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1030}},
      url = {https://eprint.iacr.org/2017/1030}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.