This leaves us with a very simple expression that we can solve
directly for k.
We see that we just need a little more than the square root of the number
of digests.
As a sanity check for D equals 365 days,
we get 22.5 people, which is in excellent agreement with our previous results.
So we can have very good confidence that we haven't done anything wrong.
For a hash function, we can write D in terms of the size of the digest.
The key observation is that the number of hashes that must be computed is on
the order of the square root of the number of possible digests.
It also means that while the difficulty of a hash collision attack is still
exponential in the size of the hash, the effective number of bits is
only half compared to the difficulty of a preimage or second preimage attack.
This is extremely significant.
An example in a prior module described the related key attack against the original
WIFI WEP encryption which had a 64-bit key, but
only 24 bits of it actually changed with each message.
This meant that the effective number of keys were about 16 million.
But since it was only necessary to find two packets that used the same key,
a birthday attack only required about 5,000 packets in order to recover the key.
An attack that could be carried out in real time.
Recall from another example, that if we calculate a million digests a second,
then it would take half a million years to carry out an exhaustive preimage or
second preimage attack against a 64-bit hash function,
though we would have an even chance of finding a solution in about 400,000 years.
A birthday attack, on the other hand,
would have an even chance of finding a collision in less than an hour and a half.
This is why adversaries go to great lengths to figure out ways to perform
birthday attacks against cryptosystems, and
why some form of birthday attack is often the first successful crack into a system.
The first hash collision involving SHA-1 was published in early 2017, and
was the result of finding weaknesses that reduced the expected number of digests
that needed to be calculated from the 2 to the 80th needed against a random oracle,
down to about 2 to the 63rd,
which still cost about $100,000 worth of computer time to carry out.
While expensive, however, this is well within the reach
of large criminal organizations, not to mention national intelligence agencies.
Whether this capability is worth the cost for either is debatable.
And for the foreseeable future,
it is still highly unlikely that anyone will actually be able to benefit from it.
But security specialists don't think in these terms if they don't have to.
And thus, the use of SHA-1 is very quickly on the way out.
For instance, most major Internet browsers announced several years ago,
well before the first and so far only actual break,
that they will no longer accept SHA-1 signed certificates by the end of 2017.
Present best practices recommend that a 160-bit hash function
is the smallest that should be used if any kind of birthday attack is conceivable,
but 256-bit is required for most classified cryptosystems.