Cryptography Reference
In-Depth Information
key Ky,δ as
Ky,δ[y]
= K[y] + δ,
Ky,δ[y + 1]
= K[y + 1]−δ,
and Ky,δ[x]
= K[x] + δ,
for x = y,y + 1.
A given key K and its modified key Ky,δ are expected to generate similar
initial states. So when the collision check fails for the pair (K
1
,K
2
), one
can try with the pair (K
1
y,δ), instead of restarting the search
with another random pair. Which candidate pair is closer to collision can be
measured by the function MCS(K
1
,K
2
) that returns the maximal step r such
that the distance between K
1
and K
2
is at most 2 at all steps up to r. For a
colliding or near-colliding key pair, MCS(K
1
,K
2
) = N.
Algorithm CollisionSearch is invoked with a random key pair (K
1
,K
2
),
each of length l, that are related as follows.
y,δ,K
2
8
<
:
K
2
[y]−1, if y = d;
K
1
[y] =
K
2
[y] = l−d−1, if y = d + 1;
K
2
[y],
(3.4)
otherwise,
where 0 ≤d ≤l−1.
The variable maxc is assigned a predefined value.
Three colliding key pairs of lengths 64, 43 and 24 bytes respectively are
reported in [111].
64-byte colliding key pairs:
K
1
=
45 3d 7d 3d c9 45 57 12 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
K
2
=
45 3d 7e 3d c9 45 57 12 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
