Cryptography Reference
In-Depth Information
3 Local Collisions in HIGHT
Local collision is firstly introduced by Chabaud et al. in [6] for finding collisions
in SHA-0 hash function using differential cryptanalysis. In block cipher crypt-
analysis, if a difference caused only by a subkey difference is eliminated by other
subkey differences with some probability a few rounds later, we call this property
a local collision in block cipher. In HIGHT, we observe that there are two types
of local collision which are depicted in Fig. 1.
'
6.>L@
'
6.>L@
(
(
(
(
E
D
'
6.>L@
E
'
6.>L@
D
(
(
(
(
E
'
6.>L@
D
'
6.>L@
(
(
(
(
(
(
(
(
(a)
Local collision type A
(b)
Local collision type B
Fig. 1.
Local collisions in HIGHT
3.1
Probabilities of Local Collisions
Fig. 1-(a) shows how the only nonzero differences
Δ
+
SK
[
i
],
Δ
+
SK
[
i
+5], and
Δ
+
SK
[
i
+ 9] in the form of the local collision type A lead to zero output dif-
ferences of the round. Its probability is computed as
r
=
α
r
1
(
α
)
r
2
(
α
)
r
3
(
α
)
where
(
Y
+
Δ
+
SK
[
i
])) +
Z
)=
α
)
,
r
1
(
α
) = Pr(((
X
⊕
Y
)+
Z
)
⊕
((
X
⊕
F
0
(
α
)) + (
Y
+
Δ
+
SK
[
i
+5]))=0)
,
r
2
(
α
)=Pr((
X
+
Y
)
⊕
((
X
⊕
(
X
+(
Y
+
Δ
+
SK
[
i
+9]))=
α
)
.
r
3
(
α
)=Pr((
X
+
Y
)
⊕
Similarly, Fig. 1-(b) shows how the only nonzero differences
Δ
+
SK
[
i
],
Δ
+
SK
[
i
+
5], and
Δ
+
SK
[
i
+ 9] in the form of the local collision type B lead to zero output
differences of the round. Its probability is computed as
s
=
β
s
1
(
β
)
s
2
(
β
)
s
3
(
β
)
where
Search WWH ::
Custom Search