Paper 2016/790

Conditional Cube Attack on Reduced-Round Keccak Sponge Function

Senyang Huang, Xiaoyun Wang, Guangwu Xu, Meiqin Wang, and Jingyuan Zhao

Abstract

The security analysis of Keccak, the winner of SHA-3, has attracted considerable interest. Recently, some attention has been paid to the analysis of keyed modes of Keccak sponge function. As a notable example, the most efficient key recovery attacks on Keccak-MAC and Keyak were reported at EUROCRYPT'15 where cube attacks and cubeattack- like cryptanalysis have been applied. In this paper, we develop a new type of cube distinguisher, the conditional cube tester, for Keccak sponge function. By imposing some bit conditions for certain cube variables, we are able to construct cube testers with smaller dimensions. Our conditional cube testers are used to analyse Keccak in keyed modes. For reduced-round Keccak-MAC and Keyak, our attacks greatly improve the best known attacks in key recovery in terms of the number of rounds or the complexity. Moreover, our new model can also be applied to keyless setting to distinguish Keccak sponge function from random permutation.We provide a searching algorithm to produce the most efficient conditional cube tester by modeling it as an MILP (mixed integer linear programming) problem. As a result, we improve the previous distinguishing attacks on Keccak sponge function significantly. Most of our attacks have been implemented and verified by desktop computers. Finally we remark that our attacks on the the reduced-round Keccak will not threat the security margin of Keccak sponge function.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in EUROCRYPT 2017
Keywords
Keccak-MACKeyakcube testerconditional cube variableordinary cube variable
Contact author(s)
xiaoyunwang @ mail tsinghua edu cn
History
2017-01-26: last of 3 revisions
2016-08-20: received
See all versions
Short URL
https://ia.cr/2016/790
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/790,
      author = {Senyang Huang and Xiaoyun Wang and Guangwu Xu and Meiqin Wang and Jingyuan Zhao},
      title = {Conditional Cube Attack on Reduced-Round Keccak Sponge Function},
      howpublished = {Cryptology ePrint Archive, Paper 2016/790},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/790}},
      url = {https://eprint.iacr.org/2016/790}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.