Cryptography Reference
In-Depth Information
same hash value so that Alice's signature is valid for this contract, too. Canting
Mallory goes to court. Alice cannot prove that Mallory's contract is forged.
How does Mallory fabricate such a contract? Suppose the hash value is only
20 bits long. Mallory is not at all interested in the complicated structure of the
hash function; instead he replaces the agreed amount of 10 000 dollars by five
times that amount. Then he marks 20 or more places in the contract which may
be changed without influencing the content: there could be eleven or twelve
blanks at one place, or another place could either read 'this' or 'that', or there
could be one or two blanks in another place, and so on. Twenty variable places
result in 2
20
, or about one million, possibilities. He calculates the hash values
for this million easily modifiable text parts. The hash value sought is among
them with high probability. Otherwise, Mallory will just have to keep changing
some more harmless places.
Sufficiently long hash values can protect you against this. However, there is a
method that can break 40-bit hash functions as easily as 20-bit hash functions.
The method is called
birthday attack
, and its original name comes from a
technique often used in statistics. The question is: how many people do you
need in a group before the probability of having two people with the same
birthday exceeds 50 %? You may think of 366
/
2
=
183 people or something
along that line. Wrong: it takes only 23 people. If you look for somebody with
his birthday on the same day as yours, this will be the case with about every
365th person on average. But in a group of 23 people, there are 22
∗
23
/
2
=
253 pairs so that the probability for said duplicity is much higher. This is
what Mallory exploits in an attack against a 40-bit hash value: he constructs
2
20
benign and 2
20
malign contracts in the manner outlined above, i.e., by
introducing small variations. The probability is then high that there is one pair
of a benign and a malign contract that have the same hash values. Now Mallory
(who is in reality female and Alice's secretary) foists the benign contract on
Alice. Alice unsuspectingly signs the contract, and Mallory sends it out by
email before her eyes — naturally just pretending. After work, Mallory puts
Alice's signature on the malign contract and then really sends it, perhaps even
with a falsified timestamp.
This birthday attack works even when the benign and malign contracts have
nothing to do with one another, and Mallory uses them to create 2
20
variations
of each version separately.
It is apparently very easy to protect yourself against this type of attack: Alice
inserts a blank in a trivial place before Mallory's eyes. Mallory has great trouble
not to lose her temper at that, because the probability is 1 to 1 000 000 that the
