MILP-based Related-Key Rectangle Attack and Its Application to GIFT, Khudra, MIBS

The rectangle attack is the extension of the traditional differential attack and is evolved from the boomerange attack. It has been widely used to attack several existing ciphers. In this article, we study the security of lightweight block ciphers GIFT, Khudra and MIBS against related-key rectangle attack. We use Mixed-Integer Linear Programming-aided cryptanalysis to search rectangle distinguishers by taking into account the effect of the ladder switch technique. For GIFT, we build a 19-round related-key rectangle distinguisher and attack on 23-round GIFT-64, which requires 2⁶⁰ chosen plaintexts and 2¹⁰⁷ encryptions. For Khudra, a 14-round related-key rectangle distinguisher can be built, which leads us to a 17-round rectangle attack. Our attack on 17-round Khudra requires a data complexity of 2^62.9 chosen plaintexts and a time complexity of 2^73.9 encryptions. For MIBS, we construct a 13-round related-key rectangle distinguisher and propose an attack on 15-round MIBS-64 with time complexity of 2⁵⁹ and data complexity of 2⁴⁵. Compared to the previous best related-key rectangle attack, we can attack one more round on Khudra and MIBS-64 than before.