Birthday attack

A birthday attack is a cryptographic attack based on the mathematics exemplified by the birthday paradox. This math turns up whenever the question of two cryptographic operations producing the same result becomes an issue.

The best-known example is collisions in cryptographic hash or message digest functions. An enemy may be able to subvert the authentication that these functions are intended to provide if he can find two inputs that hash to the same output. See collision resistance for details.

Another issue arises when a challenge-response authentication system produces the same challenge twice. An enemy who has kept careful records might then break in by looking up the correct response and giving it.

When two output blocks from a block cipher are identical, the enemy gains some information. Assuming the key has not changed, he then knows the two input blocks were identical. There are attacks based on accumulating such information; see block size.

A good approximation for the number of instances required to find a collision is $1.18*{\sqrt {n}}$. For example, to have a 50% chance of finding two birthdays the same, you need about $1.18*{\sqrt {365}}\approx 23$ people. For cryptography, a simpler approximation is used; we say that for an object of size $b$ bits, the attack cost is $2^{b/2}$. To find a collision in a 128-bit hash, the attacker needs to perform, on average, 2⁶⁴ hash operations, to find a repeated ciphertext for a 64-bit block cipher or a repetition of a 64-bit challenge, he needs to collect and store 2³² samples, and so on.

Hashes are therefore routinely designed for output twice as large as the key size of the ciphers they are intended for use with. A block cipher with a 128-bit key, for example, needs 2¹²⁷ encryptions to break by brute force. To provide authentication in a system that uses such a block cipher, or to hash a passphrase to produce a key for it, a hash algorithm with comparable strength is needed. A 256-bit hash is required to give 2¹²⁸ resistance to a birthday attack.

In US government standards, for example, the current block cipher standard is AES with key sizes of 128, 192 or 256 bits. The corresponding standard for a cryptographic hash is SHA-2 which specifies 256-bit, 384-bit and 512-bit hashes for use with AES, plus a 224-bit hash for use with Triple DES.