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

( X +( Y + Δ + SK [ i ])) = β ) , s 1 ( β )=Pr(( X + Y ) ⊕

( Y + Δ + SK [ i +5]))+ Z )=0) , s 2 ( β ) = Pr((( X ⊕ Y )+ Z ) ⊕ ((( X ⊕ F 1 ( β )) ⊕

( Y + Δ + SK [ i +9]))+( Z s 3 ( β ) = Pr((( X ⊕ Y )+ Z ) ⊕ (( X ⊕ ⊕ β )) = 0) .

By an exhaustive computation, we can see the expected values of r and s when
( Δ + SK [ i ] ,Δ + SK [ i +5] ,Δ + SK [ i +9]) = (

)are2 − 5 . 1420 and
2 − 8 , respectively, and we the following 8 possibilities of ( Δ + SK [ i ] ,Δ + SK [ i +
5] ,Δ + SK [ i + 9]) yielding the same probabilities:

, ,

0x10 0x68 0x10

( , , ) , ( , , ) , ( , , ) , ( , , ) ,

0x10 0x68 0x10 0x10 0x68 0xf0 0xf0 0x68 0x10 0xf0 0x68 0xf0

( , , ) , ( , , ) , ( , , ) , ( , , ) .

0x10 0x98 0x10 0x10 0x98 0xf0 0xf0 0x98 0x10 0xf0 0x98 0xf0

We observed that the probability r that the local collision type A with ( Δ + SK [ i ] ,
Δ + SK [ i +5] ,Δ + SK [ i +9])=( 0x10 , 0x68 , 0x10 ) occurs is nonzero only when
α = 0x10 or 0x30 . Under the observation, the probability r is actually 2 − 4 . 67807 ,
2 − 5 . 41504 ,or2 − 6 . 41504 . So, we regard 2 − 6 . 41504 as a lower bound of r .
Similarly, we observed that the probability s that the local collision type
Bwith( Δ + SK [ i ] ,Δ + SK [ i +5] ,Δ + SK [ i +9]) = ( , , ) occurs is

0x10 0x68 0x10

nonzero only when β = .Especially,for β = , s 2 ( β ) is nonzero only

0x70 0x70

when

GF(2 8 ) SK [ i +5] ∈ T = { x ∨ 0x18 | x ∈ } .

When SK [ i +5] T , the local collision of type B occurs with the probability

s =2 − 6 . Otherwise, it does not occur. Note that the fraction of T in GF(2 8 )is
1/4.

∈

3.2 Local Collisions to a Long Differential Trail

We can use a sequence of local collisions, 'type A - type B - type A' to construct
a 12-round related-key differential trail. Let i be a multiple of 4(i.e. Δ + SK [ i ]be
the right most subkey difference of round i/ 4). If Δ + SK [ i ], Δ + SK [ i +5], and
Δ + SK [ i +9] are induced by the only nonzero add-differences Δ + K [ j 1 ], Δ + K [ j 2 ],
and Δ + K [ j 3 ] of master-key bytes, then by rotational property of key schedule,

Δ + K [ j 1 ]= Δ + SK [ i ]= Δ + SK [ i + 17] = Δ + SK [ i + 34] ,
Δ + K [ j 2 ]= Δ + SK [ i +5]= Δ + SK [ i + 22] = Δ + SK [ i + 39] ,
Δ + K [ j 3 ]= Δ + SK [ i +9]= Δ + SK [ i + 26] = Δ + SK [ i + 43] ,

and differences of other subkeys are all zero if differences of other master key
bytes are zero.
Therefore, if there exist nonzero add-differences Δ + K [ j 1 ], Δ + K [ j 2 ], and
Δ + K [ j 3 ] such that the probabilities p 1 , p 2 ,and p 3 of local collisions from i/ 4
to ( i/ 4 + 3)-th round, from ( i/ 4+4) to ( i/ 4 + 7)-th round, and from ( i/ 4+8)
to ( i/ 4 + 11)-th round are all nonzero, then we can find a 12-round related-key
differential trail of HIGHT with probability p 1 ×

p 2 × p 3 by combining them

sequentially.