Paper 2021/856

Key Guessing Strategies for Linear Key-Schedule Algorithms in Rectangle Attacks

Xiaoyang Dong and Lingyue Qin and Siwei Sun and Xiaoyun Wang

Abstract

In building boomerang distinguishers, Murphy indicated that two independently chosen differentials for a boomerang may be incompatible. In this paper, we find that similar incompatibility also happens to key-recovery phase. When generating quartets for the rectangle attack on linear key-schedule ciphers, we find that the right quartets which may suggest key candidates have to satisfy some nonlinear relationships. However, some quartets generated always violate these relationships, so that they will never suggest any key candidates. We call those quartets as nonlinearly incompatible quartets. Inspired by previous rectangle frameworks, we find that guessing certain key cells before generating quartets may reduce the number of nonlinearly incompatible quartets. However, guessing a lot of key cells at once may lose the benefit from the guess-and-filter or early abort technique, which may lead to a higher overall complexity. To get better tradeoff from the two aspects, we build a new rectangle attack framework on linear key-schedule ciphers with the purpose of reducing the overall complexity or attacking more rounds. The first application is on SKINNY. In the tradeoff model, there are many parameters affecting the overall complexity. We build a uniform automatic model on SKINNY to identify all the optimal parameters, which includes the optimal rectangle distinguishers for key-recovery phase, the number and positions of key guessing cells before generating quartets, the size of key counters to build that affecting the exhaustive search step, etc. Based on the automatic model, we identify a 32-round key-recovery attack on SKINNY-128-384 in related-key setting, which extend the best previous attack by 2 rounds. For other versions with n-2n or n-3n, we also achieve one more round than before. In addition, using the previous rect- angle distinguishers, we achieve better attacks on reduced ForkSkinny, Deoxys-BC-384 and GIFT-64. At last, we discuss the conversion of our rectangle framework from related-key setting into single-key setting and give new single-key rectangle attack on 10-round Serpent.