Home | | Cryptography and Network Security | Birthday Attacks

# Birthday Attacks

Suppose that a 64-bit hash code is used. One might think that this is quite secure. For example, if an encrypted hash code C is transmitted with the corresponding unencrypted message M, then an opponent would need to find an M' such that H(M') = H(M) to substitute another message and fool the receiver.

Birthday Attacks

Suppose that a 64-bit hash code is used. One might think that this is quite secure. For example, if an encrypted hash code C is transmitted with the corresponding unencrypted message M, then an opponent would need to find an M' such that H(M') = H(M) to substitute another message and fool the receiver.

On average, the opponent would have to try about 263 messages to find one that matches the hash code of the intercepted message. However, a different sort of attack is possible, based on the birthday paradox The source, A, is prepared to "sign" a message by appending the appropriate m-bit hash code and encrypting that hash code with A's private key.

1.     The opponent generates 2m/2 variations on the message, all of which convey essentially the same meaning. (fraudulent message

2.     The two sets of messages are compared to find a pair of messages that produces the same hash code. The probability of success, by the birthday paradox, is greater than 0.5. If no match is found, additional valid and fraudulent messages are generated until a match is made.

3.     The opponent offers the valid variation to A for signature. This signature can then be attached to the fraudulent variation for transmission to the intended recipient. Because the two variations have the same hash code, they will produce the same signature; the opponent is assured of success even though the encryption key is not known.

Thus, if a 64-bit hash code is used, the level of effort required is only on the order of 232 .

Block Chaining Techniques

Divide a message M into fixed-size blocks M1,M2,..., MN and use a symmetric encryption system such as DES to compute the hash code G as follows:

Ho = initial value

Hi  = EMi [Hi-1 ]

G      = HN

This is similar to the CBC technique, but in this case there is no secret key. As with any hash code, this scheme is subject to the birthday attack, and if the encryption algorithm is DES and only a 64-bit hash code is produced, then the system is vulnerable.

Furthermore, another version of the birthday attack can be used even if the opponent has access to only one message and its valid signature and cannot obtain multiple signings.

Here is the scenario; we assume that the opponent intercepts a message with a signature in the form of an encrypted hash code and that the unencrypted hash code is m bits long:

1.     Use the algorithm defined at the beginning of this subsection to calculate the unencrypted hash code G.

2.     Construct any desired message in the form Q1, Q2,..., QN2.

3.     Compute for Hi = EQi [Hi-1 ]for 1 ≤i ≤(N-2).

4.     Generate 2m/2 random blocks; for each block X, compute EX[HN-2.] Generate an additional 2m/2 random blocks; for each block Y, compute DY[G], where D is the decryption function corresponding to E.

5.     Based on the birthday paradox, with high probability there will be an X and Y such that EX [HN-2 ] = DY[ G].

6.     Form the message Q1, Q2,..., QN-2, X, Y. This message has the hash code G and therefore can be used with the intercepted encrypted signature.

This form of attack is known as a  meet-in-the-middle attack.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Cryptography and Network Security : Birthday Attacks |