Cryptography Reference
In-Depth Information
Table 6.1:
Hash lengths with respect to attacker work effort
Attacker's work effort
Hash length to stay secure against attacker
2
64
128
2
80
160
2
112
224
2
256
512
hash function has a total of 2
n
possible hashes. This means that
w
=
2
n
. So the
above result states that a collision is more likely than not to be found after
the
square root of
2
n
messages have bee
n
tried. The square root of 2
n
is normally
written in mathematical notation as 2
2
.
What this tells us is that, on average, an attacker who can conduct around 2
2
hash computations can expect to find a collision. So the length of a practical hash
function needs to be sufficiently long that this work effort is deemed unacceptable.
Table 6.1 indicates what thismeans in terms of the length of the hash. For example,
a well-designed 160-bit hash function (in other words, one that is believed to
satisfy all the properties that we identified in Section 6.2.1) only requires an
attacker to conduct an average of:
2
16
2
2
80
=
hash function computations before they are more likely than not to have found a
collision.
The issue of how many hash function computations are needed before a hash
function is regarded as secure against a birthday attack is closely related to the
similar question regarding how long a symmetric key should be in order to be
secure against exhaustive key search. The similarity comes from the fact that both
hash function and encryption operations are regarded as fast computations. We
explore this issue further in Section 10.2. As we will discuss shortly, modern hash
functions tend not to be designed with hashes of less than 160 bits, and in fact
much longer hashes are widely recommended.
The original birthday paradox can also be solved using a similar argument. In
this case the balls are people and the bins are birthdays. Since there are 365 possible
birthdays, we can expect that around the square root of 365 (about 19) people will
be required before two are more likely than not to share the same birthday. This is
in fact a rather crude estimate, and a more accurate calculation reveals the answer
to be closer to 23. Either way, it is not intuitive and seems surprisingly few. The
surprise tends to arise because, rather than wondering how likely it is that
any
two people in the room share a birthday, we tend to focus on the chances that
two of them have a
specific
birthday (such as our own one). What this tells us
