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

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.