Related-Key Attack on the Full HIGHT - Information Security and Cryptology-ICISC 2010 - page 49

Related-Key Attack on the Full HIGHT

Bonwook Koo, Deukjo Hong, and Daesung Kwon

The Attached Institute of ETRI
P.O. Box 1, Yuseong-Gu, Daejeon, Korea
{bwkoo,hongdj,ds_kwon}@ensec.re.kr

Abstract. 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 126 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.

Keywords: HIGHT, Block cipher, Cryptanalysis, Related-key rectangle
attack.

1 Introduction

In designing a block cipher, a strong key schedule has not been a main consid-
eration. However, for recent years, the related-key attacks exploiting a weakness
of a key schedule have provided interesting results [3, 4, 5, 7]. Most of them indi-
cate that simple structure of a key schedule causes weakness useful for certain
attacks. We have KASUMI and AES as such examples. KASUMI, known as the
A5/3 algorithm for GSM security, has a linear key schedule. It is fully broken
by the related-key rectangle attack [2] and practically broken by the related-key
sandwich attack [7]. The key schedules of AES have a lot of symmetry in their
structures and use at most four S-boxes to generate a 128-bit subkey for a round.
So the full rounds of AES-192 and AES-256 are attacked by the related-key am-
plified boomerang and the related-key boomerang attacks, respectively [4]. A