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

5. Guess MSB 4 ( K 1[15]) to compute MSB 4 ( SK 1[126]) and its related keys.
For each key and remained quartet, check (a) MSB 4 ( l X 29 [3]

u X 29 [3]) = 0

⊕

j w X 29 [3]) = 0.
6. Guess LSB 4 ( K 1[9]) to compute LSB 4 ( SK 1[120]) and its related keys. For
each key and remained quartet, check (a) LSB 4 ( l X 30 [1]

and (b) MSB 4 ( v X 29 [3] ⊕

u X 30 [1]) = 0 and

⊕

w X 30 [1]) = 0.
7. Guess MSB 4 ( K 1[9]) to compute MSB 4 ( SK 1[120]) and its related keys. For
each key and remained quartet, check (a) MSB 4 ( l X 30 [1]

(b) LSB 4 ( v X 30 [1]

j

⊕

u X 30 [1]) = 0 and

⊕

j w X 30 [1]) = 0.
8. Without key guessing, check if l X 28 [0] ⊕

(b) MSB 4 ( v X 30 [1] ⊕

u X 28 [0] ∈G and v X 28 [0] ⊕ j w X 28 [0] ∈

G .
9. Without key guessing, check if l X 28 [1]

u X 28 [1] = 0 and v X 28 [1] j w X 28 [1] =

⊕ ⊕

0.
10. Guess LSB 4 ( K 1[3]) and LSB 4 ( K 1[11]) to compute LSB 4 ( SK 1[122]) and its
relatedkeys.Foreachkeyandremainedquartet,check(a) LSB 4 ( l X 30 [5]

⊕

j w X 30 [5]) = 0.
11. Guess MSB 4 ( K 1[3]) and MSB 4 ( K 1[11]) to compute MSB 4 ( SK 1[122]) and
its related keys. For each key and remained quartet, check (a) MSB 4 ( l X 30 [5]

u X 30 [5]) = 0 and (b) LSB 4 ( v X 30 [5]

⊕

⊕

j w X 30 [5]) = 0.
12. Guess K 1[8] to compute SK 1[127] and its related keys. For each key and re-
mained quartet, check (a) l X 31 [7] ⊕

u X 30 [5]) = 0 and (b) MSB 4 ( v X 30 [5]

⊕

u X 31 [7] = 0 and (b) v X 31 [7] ⊕ j w X 31 [7] = 0.

0 0 0 0 0 0 0 ࣡

10

9

8

28r

ͷ ͡ ͷ ͢ ͷ ͡ ͷ ͢

0 0 0 0 0 0

68

4,5

29r

ͷ ͡ ͷ ͢ ͷ ͡ ͷ ͢

: Guessed key bytes

0 0 0

0 0

10

10,11

6,7

: Newly guessed key bytes

30r

ͷ ͡ ͷ ͢ ͷ ͡ ͷ ͢

: Check points

0 ࣠ 0 0

12

31r

ͷ ͡ ͷ ͢ ͷ ͡ ͷ ͢

10

ࣟ 0

0

Fig. 4. Key counting procedure. The numbers nearby the check points indicate the
corresponding steps from 4 to 12.

Searching with the list
13. If there exist a recorded K 1[0 , 1 , 2 , 3 , 5 , 6 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15] who have
3 or more remaining quartets ( l C, v C ∗ , u C , j w C ∗ ), then exhaustively search
the remaining two key bytes for K 1[4] and K 1[7] with more than two known
plaintexts and its corresponding ciphertexts. If a 128-bit key is suggested,
output it and its related keys as the keys of encryption oracles of the full
rounds of HIGHT, otherwise go to Step 2 with another guess.
An overall view of our related-key rectangle attack is shown in Fig. 5 in Ap-
pendix C.