Exploiting Strong Key Bridges: Full-Fledged Automatic Rectangle Attacks on Deoxys-BC and SKINNY

Ling Song; Yincen Chen; Qianqian Yang; Huimin Liu; Lei Wang; Lei Hu; Jian Weng

Paper 2026/1110

Exploiting Strong Key Bridges: Full-Fledged Automatic Rectangle Attacks on Deoxys-BC and SKINNY

Ling Song

, College of Cyber Security, Jinan University, Guangzhou, China

Yincen Chen

, College of Cyber Security, Jinan University, Guangzhou, China, Telecom Paris, Institut Polytechnique de Paris, Palaiseau, France

Qianqian Yang

, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Huimin Liu

, College of Cyber Security, Jinan University, Guangzhou, China

Lei Wang

, School of Computer Science, Shanghai Jiao Tong University, Shanghai, China

Lei Hu

, State Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Jian Weng

, Cyberspace Institute of Advanced Technology, Guangzhou University, Guangzhou 510006, China

Abstract

Abstract. The TWEAKEY framework provides a generic construction for designing tweakable block ciphers. Prominent instances are Deoxys-BC and SKINNY, which have been standardized by ISO/IEC. In this paper, we analyze the tweakey schedules of these ciphers and identify strong dependencies between certain subtweakeys, which we call strong key bridges. We then exploit these dependencies in rectangle attacks under the related-tweakey setting. Moreover, we develop a comprehensive constraint programming model to search for rectangle attacks. Our model not only unifies the distinguisher and the key-recovery part while permitting arbitrary key-guessing strategies, but also integrates three new components, i.e., the state-test technique, explicit last-step computation, and the strong key bridges. As a result, we obtain significantly improved cryptanalytic results on both Deoxys-BC and SKINNY. For Deoxys-BC-384 and Deoxys-BC-256, we reduce the time complexity by a factor of $2^{40}$ and $2^{32}$, respectively, yielding the best attacks to date. Moreover, we extend the longest existing attacks on the authenticated encryption schemes Deoxys-I-256 and Deoxys-I-128 by one round. For SKINNY, we improve upon prior best attacks by one more round for SKINNY-128-384 and by two more rounds for SKINNY-64-192.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: A major revision of an IACR publication in CRYPTO 2026
Keywords: TWEAKEY framework Rectangle attack Automatic search Deoxys-BC SKINNY
Contact author(s): songling qs @ gmail com
yincenc @ gmail com
yangqianqian @ iie ac cn
liuhuimin301 @ gmail com
wanglei_hb @ sjtu edu cn
hulei @ iie ac cn
cryptjweng @ gmail com
History: 2026-06-02: approved; 2026-05-30: received; See all versions
Short URL: https://ia.cr/2026/1110
License: CC BY

BibTeX

@misc{cryptoeprint:2026/1110,
      author = {Ling Song and Yincen Chen and Qianqian Yang and Huimin Liu and Lei Wang and Lei Hu and Jian Weng},
      title = {Exploiting Strong Key Bridges: Full-Fledged Automatic Rectangle Attacks on Deoxys-{BC} and {SKINNY}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1110},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1110}
}