Cryptography Reference
In-Depth Information
Example 5.12 The birthday attack in Maple.
Eve is going to purchase a property fromAlice and they agreed that the price that Eve
will pay is $950000, i.e., nine hundred fifty thousand dollars. The contract is going to
be digitally signed (see Chap. 9 ) and the 40-bit hash function obtained by truncating
the MD5 output to the first 40 bits will be used. This is a very weak function but
we will assume for the sake of this example—in order to make it easily computable
with Maple—that Alice and Eve live in a world with low computational resources
in which computing 2 26 hash operations is (barely) feasible but computing 2 40 such
operations is not. The digital signature algorithm used follows the 'hash-then-sign'
paradigm, which means that what is really signed is the hash value of the contract
(see Sect. 9.3 for details). Thus, if Eve is able to find another contract with the same
hash as the one they agreed and with a different content, she could later claim that
this other contract is the one that Alice signed. She only has $150000 available and
this is the amount she would like to pay for the property so she starts to think how she
can forge another contract with this amount and the same hash as the legitimate one.
She thinks about the following possibility: make a “bad contract” with the smaller
amount in it and make a lot of variants of this contract by changing nonessential
things so that the content remains the same, hoping that one of these variants will
collide with the legitimate contract.
But Eve soon realizes that this approach will lead her nowhere because this way
she has to carry out 2 40 hash operations on average. This follows from the theory
already discussed but Eve can also arrive at this conclusion with the help of Maple
as follows. Let p be the probability that a random message produces a collision
with the legitimate contract. Then p
2 40 and so, if she keeps on generating bad
contracts and we assume they behave as if they were random, then the probability
that the i th trial succeeds and all the previous trials fail is
=
) ( i 1 ) p . Thus, taking
into account the definition of expectation in Definition 2.5, the expected value of the
number of messages she would have to try until finding a collision is:
(
1
p
> sum(i*(1-p)ˆ(i-1)*p, i=1..infinity);
1/p
This is equal to 2 40 so it is not feasible for Eve to carry out this computation on
her personal computer.
Then Eve recalls the birthday attack but the problem is that she wants to forge the
legitimate contract and not a random one. But she soon realizes that if she makes a
large number of variants of both the legitimate contract and the bad one, she has a
chance of finding a collision. So she proceeds as follows.
The hash function that will be used in the signature is:
> Hash40 := str -> StringTools:-SubString(StringTools:-Hash(str), 1 .. 10):
The statement (contract) that both parties agreed to sign is (this is only an extract
but everything works the same):
> m1 := "By signing this statement Eve agrees to pay Alice the amount of $950000
(nine hundred fifty thousand dollars) for the house mentioned below"
 
Search WWH ::




Custom Search