Cryptography Reference
In-Depth Information
m
balls
w
bins
Figure 6.5.
Experiment throwing
m
balls into
w
bins
Consider a (bizarre and pointless!) experiment where we take
m
balls and
throw them randomly into a series of
w
bins, where
w
is a much smaller number
than
m
. This situation is depicted in Figure 6.5.
What we are interested in learning is:
after how many throws is there a greater
than half chance that one of the bins contains at least two balls
?
It would be reasonable to harbour some doubts as to whether we really are
interested in learning the answer to this question! However, if we think of the
balls as messages and the bins as hashes, then this question becomes:
after how
many messages have been randomly selected is there a greater than half chance that
one of the hashes matches at least two messages
? In more familiar cryptographic
terminology, we are asking:
how many messages do we need to randomly select
before there is a greater than half chance of a hash collision
?
This is a very useful number to learn because it represents the work effort that
an attacker has to do if they conduct the following simple attack to find collisions:
1. pick a message at random, hash it and store the result in a database;
2. pick a new message at random, hash it and then check to see if that hash
already exists in the database;
3. if it does then stop, since a collision has been found; if it does not then add the
new hash to the database and repeat from step 2.
This is a simple, but powerful, attack that can be used against any hash function.
Indeed, it can be thought of as the hash function 'equivalent' of exhaustive search
for a symmetric key, since it forms the baseline attack that hash functions are
measured against, just as exhaustive key search does for symmetric key encryption.
Because its effectiveness is related to the birthday paradox, this attack is often
called a
birthday attack
.
The answer to the question that we posed is that, on average, two balls are
more likely than not to end up in the same bin (a collision is more likely than
not to be found) after approximately
the square root of w
balls have been thrown
(messages have been hashed). To interpret this properly, we note that an
n
-bit
