标题：MILP-aided cube-attack-like cryptanalysis on Keccak Keyed modes
作者：Bi W.; Dong X.; Li Z.; Zong R.; Wang X.
作者机构：[Bi, W] Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, 250100, China;[ Dong, X] 更多
通讯作者地址：[Wang, X] Institute for Advanced Study, Tsinghua UniversityChina;
来源：Designs, Codes, and Cryptography
关键词：Cube attack; Keccak-MAC; Ketje; Keyak; MILP
摘要：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. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.