Cryptography Reference
In-Depth Information
Table 1. Summary of the attacks on HIGHT(Imp.:Impossible, Diff.:Differential,
Rel.:Related, Rec.:Rectangle, Wek.:Weak Key)
Complexities
Rounds
Attack
References
Data
Time
2 46 . 8
2 109 . 2
18
Imp. Diff.
[8]
2 62 . 04
2 118 . 71
22
Saturation
[15]
2 60
2 126 . 78
25
Imp. Diff.
[10]
2 61
2 119 . 53
26
Imp. Diff.
[13]
2 51 . 2
2 120 . 41
26
Rel.-Key Rec.
[10]
2 60
2 125 . 54
28
Rel.-Key Imp.
[10]
2 63
2 127 . 28
31
Rel.-Key Imp.
[13]
Rel.-Key Rec. for Wek. 2 57 . 84
2 123 . 17
32
This paper
2 57 . 84
2 125 . 833
32
Rel.-Key attack
This paper
To our knowledge, this is the first cryptanalytic result on the full rounds of
HIGHT. Our attack has very high complexity but clearly, it shows that HIGHT
does not reach the security goal in the related-key attack model, required for a
block cipher which has a 64-bit block and a 128-bit key. It is also an evidence
that HIGHT cannot be regarded as an instantiation of an ideal cipher. Namely,
HIGHT would not be used as a substitute for an ideal cipher in applications
which are provably secure based on ideal cipher, e.g., some block-cipher-based
hash function schemes.
This paper is organized as follows. Section 2 gives the specifications of HIGHT.
In Section 3, two types of local collisions of HIGHT and its probability are in-
troduced and a weak key space is classified. In Section 4, a 24-round related-key
rectangle distinguisher of HIGHT is presented with its separation into E 0and
E 1 and estimation of its probability. Attack procedure and complexity analysis
are shown in Section 5. Finally, Section 6 concludes this paper. In Appendix A,
some flaws in calculating a probability of differential trail include key addition
is pointed out. A complexity of exhaustive key searching in related-key model
is presented in Appendix B. An overall view of our attack is depicted in Ap-
pendix C.
2 Description of HIGHT
Throughout this paper, we use the following notations.
- : bitwise exclusive OR(XOR)
-
: addition modulo 2 8
- Δ (
) : a notation of xor-difference, an xor-difference Δx indicates that a
pair ( x, x )is defined by x = x
Δx
- Δ + (
+ ) : a notation of add-difference, an add-difference Δ + x indicates that
apair( x, x )is defined by x = x
Δ + x
 
Search WWH ::




Custom Search