Cryptography Reference
In-Depth Information
Now Eve presents Alice contract
c[1]
to be signed, with the idea of later claim-
ing that Alice signed
c[2]
instead, as the same signature would be valid for both
versions. But Alice, just before signing the message, insists that
c[1]
is missing
a comma between the words “statement” and “Eve”, and makes this change to the
contract. Then Alice and Eve sign the following:
> d := StringTools:-Insert(c[1], 25, ",");
"By signing
∼
this statement,
∼
Eve
∼
agrees to
∼
pay
∼
Alice the
∼
amount of $950000
∼
(nine hundred
∼
fifty thousand
∼
dollars) for the house
∼
mentioned below"
But now the previous computation that Eve carried out in order to find a collision
between a variant of
m1
and one of
m2
is useless for her because
> Hash40(d);
"363bf9ea35"
The hash value of the new message is different from the one obtained in the
collision. So, if Eve now wants to forge the message that bears Alice's signature, she
would have to break the second preimage resistance of
Hash40
and find a collision
between
d
and a variant of
m2
. Using a generic brute-force attack, this would require
about 2
40
hash computations and, as already indicated, is not feasible for her ... Eve
does not know the reasons that led Alice to make this change at the last moment but
she is beginning to suspect that perhaps Alice is not so ignorant about cryptography
matters as she appeared to be ... might she not be the Alice whom all cryptography
topics talk about?
Remarks 5.5
1. When executing
FindCollision(m1,m2,Hash40,40)
, some versions
of Maple produce an “object too large” error. If this happens, the experiment
may still be carried out by reducing the number of collision bits and calling,
for example,
FindCollision(m1,m2,Hash36,36)
, where
Hash36
is
defined similarly to
Hash40
but takes only the first 36 bits of the MD5 hash.
This will quickly find a collision and should work in all (recent) versions.
2. Observe that the birthday attack is parallelizable. If Eve had more computers
available to parallelize the search then she could store the hash value of the
variants of the first message in several tables of manageable size and, after
generating the hashes of the variants of the second message, search for them in
these tables.
3. Note also that in this attack the hash function is used as a black box and the
attack would work the same for any other hash function with the complexity
depending only on the output length of the function.
4. The method used by Eve in her attack above is a time-memory trade-off that
reduces computing time by using a lot of memory. There are other ways of
implementing the birthday attack that decrease the amount of storage required
at the cost of increasing running time. For example, Eve could have adopted
the following approach. For the case of a hash function
h
with an
n
-bit output
and two messages
m
1 and
m
2, she could construct a function
F
from
n
{
0
,
1
}
to
