Birthday attack

A birthday attack is a cryptanalytic 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.

• For a cryptographic hash or message digest function, if an enemy can find two inputs that hash to the same output, then he may be able to subvert the authentication that these functions are intended to provide. See collision resistance for details.
• If a challenge-response authentication system produces the same challenge twice then an enemy who has kept careful records could 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. A code book attack is based on accumulating such information.

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 $1.18*{\sqrt {365}}\approx 23$ people. For cryptography, a looser approximation is used; we say that for an object of size $b$ bits, the attack cost is about ${\sqrt {2^{b}}}$ or $2^{b/2}$. To find a collision in a 128-bit hash, the attacker needs to perform, on average, about 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 about 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 brute force attack on a block cipher with a 128-bit key, for example, needs on average 2¹²⁷ encryptions. 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.