Digital Signature Susceptibility
Digital signatures can be susceptible to a birthday attack. A message is typically signed by first computing, where is a cryptographic hash function, and then using some secret key to sign . Suppose Mallory wants to trick Bob into signing a fraudulent contract. Mallory prepares a fair contract and a fraudulent one . She then finds a number of positions where 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 which are all fair contracts.
In a similar manner, Mallory also creates a huge number of variations on the fraudulent contract . 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, . 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. The birthday problem equations apply where is the number of pairs. The number of hashes Mallory actually generates is .
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.
Pollard's rho algorithm for logarithms is an example for an algorithm using a birthday attack for the computation of discrete logarithms.
Birthday attacks are often discussed as a potential weakness of the Internet's domain name service system.
Read more about this topic: Birthday Attack
Famous quotes containing the word signature:
“The childless experts on child raising also bring tears of laughter to my eyes when they say, “I love children because they’re so honest.” There is not an agent in the CIA or the KGB who knows how to conceal the theft of food, how to fake being asleep, or how to forge a parent’s signature like a child.”
—Bill Cosby (20th century)