Cryptography Reference
In-Depth Information
number of guessed keys is 2
40
and the number of remaining quartets is 2
31
.
02
,so
we expect
2
31
.
02
−
40
=2
−
8
.
98
quartets are remained for a key in average while more than 3 quartets are re-
mained if guessed key is right key. Thus we have to test quartets until step 12,
and the computational complexity from step 4 to step 12 is 2
50
.
9001
.
Therefore, the computational complexity of our related-key rectangle attack
for a quarter of key space is
2
122
.
425
+2
121
.
425
+2
69+50
.
9001
<
2
123
.
169
,
and since the computational complexity of exhaustive key searching for the re-
maining part of key space is 3
2
124
=2
125
.
585
, the total computational com-
×
plexity of our related-key attack is
2
123
.
169
+2
125
.
585
=2
125
.
833
.
6 Conclusions
In this paper, we find a 24-round related-key rectangle distinguisher using a
local-collision property of 4 rounds of HIGHT and extremely deep ladder switch
technique when add-differences are used for a relations of keys. This distinguisher
can be regards as a 25-round distinguisher because the distinguisher is followed
by one round truncated differential trail with probability 1. Based on this distin-
guisher, we present a related-key rectangle attack on the full rounds of HIGHT
for a large weak key space and we consider a related-key attack which is valid
for whole key space faster than 2
126
encryptions required for the exhaustive key
searching with 4 related keys. Time complexity of our attack is very marginal
and seems to be hard to realize to extract the secret key bits. However, our result
gives an evidence for the fact that HIGHT cannot be regarded as an instantiation
of the ideal cipher.
References
1. Biham, E.: How to Forge DES-Enhanced Messages in 2
28
Steps. CS 884 (August
1996)
2. Biham, E., Dunkelman, O., Keller, N.: A Related-Key Rectangle Attack on the
Full KASUMI. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 443-461.
Springer, Heidelberg (2005)
3. Biryukov, A., Dunkelman, O., Keller, N., Khovratovich, D., Shamir, A.: Key Re-
covery Attacks of Practical Complexity on AES Variants With Up To 10 Rounds.
To appear in EUROCRYPT 2010, Available at Cryptology ePrint Archive, Report
2009/374 (2010),
http://eprint.iacr.org/2009/374
4. Biryukov, A., Khovratovich, D.: Related-key cryptanalysis of the full AES-192 and
AES-256. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 1-18.
Springer, Heidelberg (2009)
Search WWH ::
Custom Search