Cryptography Reference
In-Depth Information
Equation (11.1) is extremely important: it describes the relationship between the
number of hashed messages t needed for a collision as a function of the hash output
length n and the collision probability
. The most important consequence of the
birthday attack is that the number of messages we need to hash to find a colli-
sion is rough ly equal to the square root of the number of possible output values,
λ
i.e., about 2 n = 2 n / 2 . Hence, for a security level (cf. Section 6.2.4) of x bit, the
hash function needs to have an output length of 2 x bit. As an example, assume we
want to find a collision for a hypothetical hash function with 80-bit output. For a
success probability of 50%, we expect to hash about:
t = 2 81 / 2 ln (1 / (1
2 40 . 2
0 . 5))
input values. Computing around 2 40 hashes and checking for collisions can be done
with current laptops! In order to thwart collision attacks based on the birthday para-
dox, the output length of a hash function must be about twice as long as an output
length which protects merely against a second preimage attack. For this reason,
all hash functions have an output length of at least 128 bit, where most modern
ones are much longer. Table 11.1 shows the number of hash computations needed
for a birthday-paradox collision for output lengths found in current hash functions.
Interestingly, the desired likelihood of a collision does not influence the attack com-
plexity very much, as is evidenced by the small difference between the success
probabilities
λ
= 0 . 5 and
λ
= 0 . 9. It should be stressed that the birthday attack is a
Table 11.1 Number of hash values needed for a collision for different hash function output lengths
and for two different collision likelihoods
Hash output length
λ
128 bit
160 bit
256 bit
384 bit
512 bit
2 65
2 81
2 129
2 193
2 257
0 . 5
2 67
2 82
2 130
2 194
2 258
0 . 9
generic attack. This means it is applicable against any hash function. On the other
hand, it is not guaranteed that it is the most powerful attack available for a given
hash function. As we will see in the next section, for some of the most popular hash
functions, in particular MD5 and SHA-1, mathematical collision attacks exist which
are faster than the birthday attack.
It should be stressed that there are many applications for hash functions, e.g.,
storage of passwords, which only require preimage resistance. Thus, a hash function
with a relatively short output, say 80 bit, might be sufficient since collision attacks
do not pose a threat.
At the end of this section we summarize all important properties of hash functions
h ( x ). Note that the first three are practical requirements, whereas the last three relate
to the security of hash functions.
 
Search WWH ::




Custom Search