Exercise 2: Is 2^64 Collision Resistance Still Safe? — Possible Solution
====================================================================

2^64 is approximately 1.8 x 10^19 -- a huge number in absolute terms,
but the relevant question isn't "is this a big number," it's "is this
a big number relative to what modern computing hardware can actually
attempt."

Modern GPU and ASIC hardware can compute hash functions at rates of
many billions of hashes per second. At even a modest rate of, say,
10 billion (10^10) hashes per second across a modest cluster of
hardware, exhausting a 2^64 search space would take on the order of
1.8 x 10^19 / 10^10 = 1.8 x 10^9 seconds -- still a large number, but
FEASIBLE well within reach of a well-resourced attacker (nation-state,
large criminal operation, or academic research budget) using
distributed/parallelized hardware, especially given that real
collision attacks don't need to brute-force the full birthday bound at
all if the underlying hash has genuine structural weaknesses to
exploit -- which is exactly what happened with MD5.

Why MD5 is "fully broken" rather than "a bit weak":

The chapter distinguishes two separate problems stacking on top of
each other for MD5:

1. Its 128-bit output ALREADY only gives ~2^64 theoretical collision
   resistance via the birthday paradox alone -- a real, calculable
   weak point purely from having too short an output, even under
   perfect design.

2. On top of that, the 2004 Wang et al. attacks found REAL structural
   weaknesses in MD5's internal design that let attackers find
   collisions dramatically faster than the theoretical 2^64 figure --
   not just approaching the birthday bound through brute force, but
   beating it entirely through cryptanalysis.

Combining an already-marginal 128-bit output with a genuine
algorithmic weakness on top of it is why MD5 collisions are practical
today (demonstrated concretely by the 2012 Flame malware), rather than
merely theoretically weaker than modern 256-bit hashes.

WHY THIS WORKS AS AN ANSWER
------------------------------
This directly uses the chapter's own claim that SHA-2/SHA-3 use
256+ bits specifically "because it's a direct, calculable consequence
of the birthday paradox," and applies the same reasoning in reverse to
show why MD5's 128 bits (and resulting ~2^64 theoretical bound) was
already a comparatively weak starting point -- one that the 2004
attacks then broke through decisively rather than just narrowing.