Paper 2018/075

MILP-aided Cube-attack-like Cryptanalysis on Keccak Keyed Modes

Wenquan Bi, Xiaoyang Dong, Zheng Li, Rui Zong, and Xiaoyun Wang

Abstract

Cube-attack-like cryptanalysis was proposed by Dinur et al. at EUROCRYPT 2015, which recovers the key of Keccak keyed modes in a divide-and-conquer manner. In their attack, one selects cube variables manually, which leads to more key bits involved in the key-recovery attack, so the complexity is too high unnecessarily. In this paper, we introduce a new MILP model and make the cube attacks better on the Keccak keyed modes. Using this new MILP tool, we find the optimal cube variables for Keccak-MAC, Keyak and Ketje, which makes that a minimum number of key bits are involved in the key-recovery attack. For example, when the capacity is 256, we find a new 32-dimension cube for Keccak-MAC that involves only 18 key bits instead of Dinur et al.'s 64 bits and the complexity of the 6-round attack is reduced to $2^{42}$ from $2^{66}$. More impressively, using this new tool, we give the very first 7-round key-recovery attack on Keccak-MAC-512. We get the 8-round key-recovery attacks on Lake Keyak in nonce-respected setting. In addition, we get the best attacks on Ketje Major/Minor. For Ketje Major, when the length of nonce is 9 lanes, we could improve the best previous 6-round attack to 7-round. Our attacks do not threaten the full-round (12) Keyak/Ketje or the full-round (24) Keccak-MAC. When comparing with Huang et al.'s conditional cube attack, the MILP-aided cube-attack-like cryptanalysis has larger effective range and gets the best results on the Keccak keyed variants with relatively smaller number of degrees of freedom.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Designs, Codes and Cryptography
DOI
10.1007/s10623-018-0526-x
Keywords
Keccak-MACKeyakKetjeMILPCube attack
Contact author(s)
biwenquan @ mail sdu edu cn
xiaoyangdong @ tsinghua edu cn
History
2018-07-27: last of 3 revisions
2018-01-18: received
See all versions
Short URL
https://ia.cr/2018/075
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/075,
      author = {Wenquan Bi and Xiaoyang Dong and Zheng Li and Rui Zong and Xiaoyun Wang},
      title = {MILP-aided Cube-attack-like Cryptanalysis on Keccak Keyed Modes},
      howpublished = {Cryptology ePrint Archive, Paper 2018/075},
      year = {2018},
      doi = {10.1007/s10623-018-0526-x},
      note = {\url{https://eprint.iacr.org/2018/075}},
      url = {https://eprint.iacr.org/2018/075}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.