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

practical key recovery attack on 13 out of 14 rounds of AES-256, which has been
recently proposed, also uses related keys [5].
HIGHT [8] is a block cipher which has a linear(in a modular addition point
of view) key schedule with few propagations. It was proposed at CHES 2006
for lightweight computing environments such as radio frequency identifications
(RFID). Also, HIGHT is a block cipher standard approved by Telecommuni-
cations Technology Association (TTA) of Korea and international standardiza-
tion activities are in progress to include the HIGHT into ISO/IEC 18033-3 [9].
HIGHT is a 32-round block cipher in 8-branch type II generalized Feistel struc-
ture with 64-bit block and 128-bit key. The round functions of HIGHT is designed
with bit-wise exclusive OR, addition modulo 2 8 , and rotations. Such design as-
pects make HIGHT more ecient than most existing block ciphers including
AES-128 on hardware implementation. The designers of HIGHT analyzed its se-
curity against various attacks including related-key attacks and they concluded
that at least 20 rounds of HIGHT is secure against these attacks. But at ICISC
2007, Lu et al. presented some cryptanalytic results on the HIGHT reduced to 25,
26, and 28 rounds with or without initial and final whitening key additions, using
impossible differential, related-key rectangle, related-key impossible differential
attacks [10]. Moreover, at ACISP 2009, Ozen et al. improved the attack results
of ICISC 2007 into an impossible differential attack on 26 rounds of HIGHT
and a related-key impossible differential attack on 31 rounds of HIGHT [13].
At CANS 2009, Zhang et al. pointed out an error in the 12-round saturation
distinguisher introduced by designers of HIGHT and gave a saturation attack
on 22 rounds of HIGHT with initial and final whitening keys using 17-round
saturation distinguisher [15].
In this paper, we present a related-key attack on the full HIGHT slightly
faster than the exhaustive key search. The attack consists of a related-key rect-
angle attack for a quarter of key space and an exhaustive key searching for the
rest three-quarter of key space in the related-key attack model. Our related-key
rectangle attack uses a 24-round related-key rectangle distinguisher with prob-
ability 2 − 117 . 68 . This distinguisher is constructed from an 8.5-round( E 0) and a
15.5-round( E 1) related-key truncated differential trail by combining them with
the ladder switch technique and E 1 is a combination of three local collisions. The
local collision is a related-key differential trail whose input and output differences
are zero and in our attack, and we find two types of 4-round local collision and
combine them alternately by using the byte-wise rotational property of subkey
positioning. Every subkey byte is defined by a modular addition of a byte of
encryption key and a predefined constant, so we give an add-difference for re-
lation of keys to avoid paying probability for generating subkey differences by
key schedule. For E 0, we modify a known related-key differential trail [10,11] to
avoid a flaw shown in Appendix A and transform it into related-key truncated
differential trail to reduce data complexity. So we construct a related-key rect-
angle attack for a quarter of key space with 2 123 . 17 time and 2 57 . 84 data and an
attack for whole key space with 2 125 . 833 time and 2 57 . 84 data. The time and data
complexities for attacking HIGHT is given in the Table 1.