International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Xiaoyang Dong , Institute for Advanced Study, BNRist, Tsinghua University, Beijing, China
Lingyue Qin , Institute for Advanced Study, BNRist, Tsinghua University, Beijing, China
Siwei Sun , School of Cryptology, University of Chinese Academy of Sciences, Beijing, China
Xiaoyun Wang , Institute for Advanced Study, BNRist, Tsinghua University, Beijing, China
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2022
Abstract: When generating quartets for the rectangle attack on ciphers with linear key-schedule ciphers, we find 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. Inspired by previous rectangle frameworks, we find that guessing certain key cells before generating quartets may reduce the number of those invalid quartets. However, guessing a lot of key cells at once may lose the benefit from the early abort technique, which may lead to a higher overall complexity. To get better tradeoff, we build a new rectangle attack framework on ciphers with linear key-schedule with the purpose of reducing the overall complexity or attacking more rounds. In the tradeoff model, there are many parameters affecting the overall complexity, especially for the choices of the number and positions of key guessing cells before generating quartets. To identify optimal parameters, we build a uniform automatic tool on SKINNY as an example, 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 tool, we identify a 32-round key-recovery attack on SKINNY-128-384 in the related-key setting, which extends 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 rectangle distinguishers, we achieve better attacks on round-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.
Video from EUROCRYPT 2022
BibTeX
@inproceedings{eurocrypt-2022-31831,
  title={Key Guessing Strategies for Linear Key-Schedule Algorithms in Rectangle Attacks},
  publisher={Springer-Verlag},
  author={Xiaoyang Dong and Lingyue Qin and Siwei Sun and Xiaoyun Wang},
  year=2022
}