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.

On average, the opponent would have to try about 2⁶³ 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 2^m/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 2³² .

Block Chaining Techniques

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

H_o = initial value

Hi  = EMi [Hi-1 ]

G      = H_N

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 Q₁, Q₂,..., Q_N2.

3.     Compute for H_i = EQ_i [H_i-1 ]for 1 ≤i ≤(N-2).

4.     Generate 2^m/2 random blocks; for each block X, compute E_X[H_N-2.] Generate an additional 2^m/2 random blocks; for each block Y, compute D_Y[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 E_X [H_N-2 ] = D_Y[ G].

6.     Form the message Q₁, Q₂,..., Q_N-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.