Birthday attack (idea)

How to perform a Birthday Attack on Digital Signatures

NOTE: This example is based on one used in the third edition of Computer Networks by Andrew S. Tanenbaum.

The birthday attack on digital signatures allows a third party to replace one digitally signed message with a different one without altering the signature. Consider the following situation between Alice, Bob, and Trudy. (As in most cryptography examples, messages go from Alice to Bob, while Trudy is an "Intruder" attempting to disrupt or intercept communication.)

Alice writes an e-mail to Bob with the following text:

etc, etc. Assume the message is at least a few paragraphs long. Now, Alice digitally signs the message (using PGP for example), then hands it to her secretary Trudy, and tells her to send it to Bob tomorrow. (Alternately, Trudy could intercept the message using more technical means, but we assume simply that Trudy simply has the message and can stop Bob from receiving it verbatim.) Let's say Trudy was also trying to get the regional manager job, and in any case does not want Bob to get it. She could write a message like this:

etc, etc. The problem, of course, is that Trudy's message won't be digitally signed by Alice, because Trudy doesn't have access to Alice's private key, and it is computationally infeasable to get it from the signature. So how can Trudy forge the digital signature?

Very quickly, digital signatures work as follows. The message goes through what is called a One-Way Hash, such as MD5. This produces a hash value. Then, the hash value is encrypted using Alice's private key. Anyone can use Alice's public key to decrypt the signature and get the hash value. Then, they re-hash the message using the same algorithm. If the receiver's hash value matches the hash value in Alice's signature, then the message is assumed to be intact. If not, the message has been altered and should be discarded. Trudy can generate hash values on her messages, but she cannot generate the signature that is decryptable with Alice's public key. So what can Trudy do?

Well, Trudy writes a message like this:

The words marked with (a|b) are alternatives. Either a or b is acceptable in producing a message with the same meaning. Now, Trudy writes a Perl script that generates all possible combinations of her message using all the alternative pairs. If there are n alternative words, then there are 2^n messages, which is quite a lot. The Perl script also verifies each of the 2^n messages against Alice's digital signature. It may take a few hours of computation, but given enough possible messages, eventually one will produce the same one-way hash, and thus will be valid with the same signature! (See EE's writeup for the mathematical reasons behind this.)

When Trudy has found a message that is valid, she can substitute it in Alice's message, and then put the digital signature on the end. When Bob receives the message, he will not be able to tell it's been altered.

How to protect yourself against the birthday attack

One way to protect yourself against the Birthday Attack is to ensure the security of the transmission medium. For instance, you can send your messages through an SSH tunnel, and it will be much harder to intercept, (though not impossible). In some cases this is impossible. For instance, some e-mail servers won't support SSH, or if the mail is forwarded through multiple servers, you may not be able to guarantee the connections will always be secure.

You could also encrypt the message. If Bob had a an asymmetric key (as used in PGP), then Alice could have encrypted the message and signature and had it sent to Bob. In such a case, the only way Trudy could alter the message is if she had Bob's private key. This fails, however, if Bob does not use PGP or similar programs.