Cryptography Reference
In-Depth Information
issue SSL certificates (the ones used for secure web browsing) to any website they
like, including rogue websites claiming to be legitimate ones.
It is important to notice that, even if these stronger attacks were not known, a
generic birthday attack is sufficient today to break the collision resistance of MD5
and of any hash function with a 128-bit output. This imposes a lower bound on the
output length of any cryptographic hash function and 160 bits is a bare minimum
that is already starting to look insufficient. The most widely used hash function
today is SHA-1, introduced in 1995 and currently specified in [74]. SHA-1 is also
obtained from the Merkle-Damgård iterative construction and has an output length
of 160 bits, which means that a generic birthday attack would require just over 2
80
hash operations. This seems achievable in the near future and, moreover, a collision
attack requiring only 2
69
operations—improved later to require just 2
63
operations
—was announced already in 2005, in [195]. This attack should be certainly regarded
as feasible and other improved attacks have also been announced. Thus, although no
actual collisions have been found so far, it is only a matter of time and SHA-1 is also
regarded as broken. It is clear that a 160-bit output is no longer adequate for future
use and so the hash functions that are currently being recommended are those in
the SHA-2 family, such as SHA-256 implemented above. These functions have not
shown noticeable weaknesses so far and are secure against generic birthday attacks
because their minimum output length is 224 bits for SHA-224 which would put the
cost of such an attack at over 2
112
operations, which is currently infeasible. Even so,
NIST has set up an open contest to design the new SHA-3 standard whose winner
Keccak, was announced in October 2012.
Exercise 5.16
Suppose that
h
is a hash function with a 128-bit output. Use Maple's
function
ep
defined in Example 5.11 to compute numerical estimates of the proba-
bility that a collision for
h
will be found in case 2
65
or 2
66
hash values are computed.
Obtain similar estimates in case
h
has a 256-bit output and the number of hash values
computed is one of the following: 2
66
,2
129
or 2
130
.
The preceding discussion of birthday attacks should not be viewed as implying
that a hash function which is not vulnerable to a birthday attack is collision resis-
tant. On the contrary, resistance to birthday attacks is only a necessary condition
that is far from sufficient for collision resistance. For example, we may consider a
hash function that assigns to each string its first 256 bits. This function is immune
to a birthday attack for the same reason that SHA-256 is: the attack would require
the computation of over 2
128
hash operations. However, finding collisions for this
function is entirely trivial.
As we have mentioned, the birthday attack is not efficient against (second) preim-
age resistance and so it might seem that its applicability is very limited because in
applications such as authentication and digital signatures an adversary would not
be interested in a collision with a random message but, rather, in a collision with a
specific message, namely, the one that is being authenticated or signed. This is, how-
ever, a naive misconception as we are going to showwith an example that shows how
a birthday attack can be used to obtain a collision between 'meaningful' messages
which are far from random.
