Editing Birthday attack (section)

==Digital signature susceptibility==
[[Digital signature]]s can be susceptible to a birthday attack or more precisely a chosen-prefix collision attack. A message <math>m</math> is typically signed by first computing <math>f(m)</math>, where <math>f</math> is a [[cryptographic hash function]], and then using some secret key to sign <math>f(m)</math>. Suppose [[Alice and Bob|Mallory]] wants to trick [[Alice and Bob|Bob]] into signing a [[fraudulent]] contract. Mallory prepares a fair contract <math>m</math> and a fraudulent one <math>m'</math>. She then finds a number of positions where <math>m</math> can be changed without changing the meaning, such as inserting commas, empty lines, one versus two spaces after a sentence, replacing synonyms, etc. By combining these changes, she can create a huge number of variations on <math>m</math> which are all fair contracts.

In a similar manner, Mallory also creates a huge number of variations on the fraudulent contract <math>m'</math>. She then applies the hash function to all these variations until she finds a version of the fair contract and a version of the fraudulent contract which have the same hash value, <math>f(m) = f(m')</math>. She presents the fair version to Bob for signing. After Bob has signed, Mallory takes the signature and attaches it to the fraudulent contract. This signature then "proves" that Bob signed the fraudulent contract.

The probabilities differ slightly from the original birthday problem, as Mallory gains nothing by finding two fair or two fraudulent contracts with the same hash. Mallory's strategy is to generate pairs of one fair and one fraudulent contract. For a given hash function <math>2^l</math> is the number of possible hashes,  where <math>l</math> is the bit length of the hash output. 
The birthday problem equations do not exactly apply here. For a 50% chance of a collision, Mallory would need to generate approximately <math>2^{(l/2) + 1}</math> hashes, which is twice the number required for a simple collision under the classical birthday problem.

To avoid this attack, the output length of the hash function used for a signature scheme can be chosen large enough so that the birthday attack becomes computationally infeasible, i.e. about twice as many bits as are needed to prevent an ordinary [[brute-force attack]].

Besides using a larger bit length, the signer (Bob) can protect himself by making some random, inoffensive changes to the document before signing it, and by keeping a copy of the contract he signed in his own possession, so that he can at least demonstrate in court that his signature matches that contract, not just the fraudulent one.

[[Pollard's rho algorithm for logarithms]] is an example for an algorithm using a birthday attack for the computation of [[discrete logarithm]]s.

===Reverse attack===
The same fraud is possible if the signer is Mallory, not Bob.  Bob could suggest a contract to Mallory for a signature.  Mallory could find both an inoffensively-modified version of this fair contract that has the same signature as a fraudulent contract, and Mallory could provide the modified fair contract and signature to Bob.  Later, Mallory could produce the fraudulent copy.  If Bob doesn't have the inoffensively-modified version contract (perhaps only finding their original proposal), Mallory's fraud is perfect.  If Bob does have it, Mallory can at least claim that it is Bob who is the fraudster.