birthday attack

A class of attacks against cryptographic functions, including both encryption functions and hash functions. The attacks take advantage of a statistical property: Given a cryptographic function having an N-bit output, the probability is greater than 1/2 that for 2**(N/2) randomly chosen inputs, the function will produce at least two outputs that are identical. (See: Tutorial under "hash function".)

Derivation: From the somewhat surprising fact (often called the "birthday paradox") that although there are 365 days in a year, the probability is greater than 1/2 that two of more people share the same birthday in any randomly chosen group of 23 people.

Birthday attacks enable an adversary to find two inputs for which a cryptographic function produces the same cipher text (or find two inputs for which a hash functions produces the same hash result) much faster than a brute-force attack can; and a clever adversary can use such a capability to create considerable mischief. However, no birthday attack can enable an adversary to decrypt a given cipher text (or find a hash input that results in a given hash result) any faster than a brute-force attack can.