Cryptology ePrint Archive: Report 2018/075

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

Wenquan Bi and Xiaoyang Dong and Zheng Li and 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.

Category / Keywords: Keccak-MAC, Keyak, Ketje, MILP, Cube attack

Original Publication (in the same form): Designs, Codes and Cryptography

Date: received 17 Jan 2018, last revised 26 Jul 2018

Contact author: biwenquan at mail sdu edu cn; xiaoyangdong@tsinghua edu cn

Available format(s): PDF | BibTeX Citation

Version: 20180727:032028 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]