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 2^{63} 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^{32} .

**Block Chaining Techniques**

Divide a
message M into fixed-size blocks M_{1},M_{2},..., M_{N}
and use a symmetric encryption system such as DES to compute the hash code G as
follows:

**H _{o}**

**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_{1},
Q_{2},..., 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_{1}, Q_{2},...,
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**.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Cryptography and Network Security : Birthday Attacks |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.