Cryptography Reference
In-Depth Information
question for you, though: How many people would you have to gather in a room
to have a 50 percent chance that two of them share the same birthday? You might
hazard a guess that it would take about 183 — half the people, half the chance.
As it turns out, the answer is stunningly lower. If 23 people are gathered
together in a room, there's a 50 percent chance that two of them share the same
birthday. To resolve this seeming paradox, consider this: If there are
n
people
in a room, there are 365
n
possible birthdays. The fi rst person can have any of
365 birthdays; the second can have any of 365 birthdays; and so on. However,
there are only 365*364 ways that two people can have unique birthdays. The
fi rst person has “used up” one of the available birthdays. Three people can only
have 365*364*363 unique birthday combinations. In general,
n
people can have
365!
(365
365!
(365
unique
combinations of birthdays. So, there are
365
n
n)!
ways that
at least two people share a birthday — that is, that the birthday combinations are
not unique. The math is complex, but clear: With
n
poss
ib
ilities, you need
n
n)!
1
instances to guarantee a repeat, but you need ª 1.1772 n to have a 50% chance
of a repeat. This surprising result is often referred to as the
birthday paradox
.
This doesn't bode well for MD5. MD5 produces 128 bits for each input. 2
128
is
a mind-bogglingly large number. In deci
ma
l, it works out to approximately 340
million trillion trillion. However, 1.1772 2
128
ª 2.2
10
19
. That's still a lot, but quite
a few less than 2
128
. Remember that the purpose of using MD5 rather than a
simple checksum digest was that it ought to be impossible for an attacker to
engineer a collision. If I deliberately go looking for a collision with a published
hash, I have to compute for a long time. However, if I go looking for two docu-
ments that share a hash, I need to look for a much shorter time, albeit still
for a long time. And, as you saw with DES, this brute-force
birthday attack
is
infi nitely parallelizable; the more computers I can add to the attack, the faster
I can get an answer.
This vulnerability to a birthday attack is a problem that all digest algo-
rithms have; the only solution is to make the output longer and longer until
a birthday attack is infeasible in terms of computing power. As you saw with
symmetric cryptography, this is a never-ending arms race as computers get
faster and faster and protocol designers struggle to keep up. However, MD5
is even worse off than this. Researchers have found cracks in the protocol's
fundamental design.
In 2005, security researchers Xiaoyan Wang and Hongbo Yu presented their
paper “How to break MD5 and other hash functions” (
http://merlot.usc.
edu/csac-s06/papers/Wang05a.pdf
), which detailed an exploit capable of
producing targeted MD5 collisions in 15 minutes to an hour using commodity
hardware. This is not a theoretical exploit; Magnus Daum and Stefaun Lucks
illustrate an actual real-world MD-5 collision in their paper
http://th.informatik
.uni-mannheim.de/people/lucks/HashCollisions/
.
Search WWH ::
Custom Search