Related-key attack on the full HIGHT

HIGHT is a lightweight block cipher, proposed in CHES 2006, and on the process of ISO/IEC 18033-3 standardization. It is a 32-round Feistel-like block cipher with 64-bit block and 128-bit key. In this paper, we present the first attack on the full HIGHT using related-key rectangle attack with 2^123.169 encryptions, 2^57.84 data, and 4 related keys. Our related-key rectangle attack is valid for 2¹²⁶ weak keys and this attack can be easily extended to an attack for the full key space faster than an exhaustive key searching using 4 related keys. We observe that an “add-difference” of master keys is propagated to an add-difference of subkeys with probability 1, so we can find 3-round local collisions of HIGHT by considering an add-difference as a relation of keys. Exploiting these local collisions and “over-simplified” structure of key-schedule, we construct a new 15.5-round related-key differential trail with relatively high probability. We construct a 24-round related-key rectangle distinguisher with probability 2^−117.68 from an 8.5-round and a 15.5-round related-key truncated differential trail with local collisions by applying the ladder switch technique, and then suggest an attack on full rounds of HIGHT with this distinguisher. Our result implies that HIGHT cannot be regarded as an instantiation of the ideal cipher used in some provably secure schemes.