Cryptography Reference
In-Depth Information
n
, where
b
is the leading bit of
x
and
t
an
=
||
∈{
,
}
itself as follows. Let
x
b
t
0
1
(
−
)
n
1
-bit string. Then define:
h
(
variant
(
t
,
m
1
))
if
b
=
0
,
F
(
x
)
=
h
(
variant
(
t
,
m
2
))
if
b
=
1
.
where
variant
is like the Maple function of the same name defined above
which computes the variant of the message corresponding to a given number
and we assume that the output of the hash function is given as a binary string.
Then Floyd's cycle-finding algorithm can be used in the way described, for
example, in [106, 7.5] to look for a collision of
h
. Half of the time, on average,
the collision found will not be useful because it will be either a collision between
two variants of
m
1 or two variants of
m
2, but the remaining cases will give a
collision between a variant of
m
1 and one of
m
2 and this can be done with very
low memory requirements at the cost of more computing time.
5. The attack in Example 5.12 was carried out in a restricted computing environ-
ment but we can easily extrapolate from it to the real world. Since computing
over 2
64
hash operations is regarded as feasible, this attack shows that a hash
function with a 128-bit output does not offer security anymore and this is why
such hash functions are regarded as 'broken'. Even a 160-bit hash function like
SHA-1 would probably be within reach of a massive birthday attack but, as
we have mentioned, there are improved attacks for this function that require
about 2
63
hash operations, thus SHA-1 is also regarded as broken. The cur-
rently recommended hash function is SHA-256 and this is the one we use in our
implementations.
