A cryptographic attack on a one-way function (e.g, a secure hash.) The attack is named after the statistical property of birthday duplication - you only need 23 people to have a larger than 50% chance that they are born on the same day of the year.

This is due to the fact that each time you adding one person to the set of people you are looking for duplicates in, you are looking for duplicates against all the people already in the set, not just one of them.

The same technique can be used to look for conflicts in one-way functions. Instead of taking one output of the one-way function, you create or aquire a set of values (let's call this a) that have a some property, and then create another set of other values that have different properties (let's call this b), and try to find any value that is in both a and b. This is a much smaller problem that finding a value that match a particular value in a.

The properties in a and b might for instance be

  • ... a contains secure hashes of an innocent message and b contains one of a less innocent message, so the attacker can substitute the messages at a later date.
  • ... a is the password hashes of a system the attacker wants to get an account on, and b is a set of password hashes that the attacker knows the passwords for.
  • ... a is the set of public keys from a Discrete Logarithms based cryptosystem where g and p are static, while b is the set of g^e mod p functions that the attacker knows e for.

Resistance against this attack is why the Unix password hashes use a salt.

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:

Dear Bob,

I would like to recommend Fred for the job of regional manager here at ConHuge Co. Ltd. Fred is an excellent employee...

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:

Dear Bob,

I think that Fred is a poor choice for regional manager at ConHuge Co. Ltd. His work record is terrible, he is frequently late...

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:

Dear (Bob|Robert),

I (feel|think) that (Fred|Fred Smith) (is not|isn't) a (good|fair) choice for the (position|job) of regional manager. He is (frequently|often) late...

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.

Log in or register to write something here or to contact authors.