标题：MILP-aided cube-attack-like cryptanalysis on Keccak Keyed modes
作者：Bi, Wenquan; Dong, Xiaoyang; Li, Zheng; Zong, Rui; Wang, Xiaoyun
作者机构：[Bi, Wenquan; Li, Zheng; Zong, Rui; Wang, Xiaoyun] Shandong Univ, Minist Educ, Key Lab Cryptol Technol & Informat Secur, Jinan 250100, Shandong, Peopl 更多
通讯作者：Wang, XY;Dong, XY;Wang, XY;Wang, Xiaoyun
通讯作者地址：[Wang, XY]Shandong Univ, Minist Educ, Key Lab Cryptol Technol & Informat Secur, Jinan 250100, Shandong, Peoples R China;[Dong, XY; Wang, XY]Tsinghua U 更多
来源：DESIGNS CODES AND CRYPTOGRAPHY
关键词：Keccak-MAC; Keyak; Ketje; MILP; Cube attack
摘要：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 242 from 266. 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.