Cryptography Reference
In-Depth Information
(e)
Pay eight thousand dollars to Mr Fred Piper
(f) etc.
3. He calculates the hash of all 2000 of these different messages. Since there are
only 1000 different possible values of the hash, there is a very good chance
(although it is not 100%) that he will discover that the hash for one of the
$200 messages is the same as the hash for one of the $8000 messages.
We will assume that he is successful (and he almost certainly will be) and he
discovers that:
h
(
Pay Fred Piper the sum of $200
)
=
h
(
We agree to pay F. C. Piper $8000
)
.
4. He presents the clerk with a request
Pay Fred Piper the sum of $200
. The clerk
agrees to authorise the payment by digitally signing this request (which involves
hashing the request message and then signing it).
5. Fred now sends his bank the digital signature on the hash of
Pay Fred Piper the
sum of $200
but claims that it is on the message
We agree to pay F. C. Piper
$8000
. Fred has a valid digital signature on this message.
There are two reasons why this attack was successful:
• In this example there are many potentially meaningful collisions. The nature
of the example is more illustrative than realistic. A good way to reduce the
number of meaningful collisions would be to insist, as many organisations do,
that payment orders are formatted in a particular way and not left as open as
this one was.
• The length of the hash is still too short. Even though 'getting lucky' with the hash
is now a little bit more difficult than for our first example, it is still easy to find
collisions by conducting a relatively small amount of work (in this case 2000
hash function computations).
So the lesson is that a hash must be sufficiently long that finding collisions is
'infeasible'. We now consider how many bits long a hash needs to be for this to
be true.
BIRTHDAY ATTACKS
The output length of practical hash functions is formally determined by a well-
known statistical result that is often referred to as the
birthday paradox
. It gets
this name because it is often presented in terms of the number of people required
in a room before it becomes more likely than not that two of them share the same
birthday. The 'paradox' is that the number is smaller than most people expect
(although this is really a 'surprise' rather than a paradox).
Wewill not worry ourselves with themathematics behind the birthday paradox,
but we do need to know what it tells us about finding collisions in hash functions.
Thus, rather than people and birthdays, we will present the problem in a more
general way.
