What is a birthday attack in cryptography?

A birthday attack is a type of brute-force collision attack that exploits the mathematics behind the birthday problem in probability theory. It allows an attacker to find a hash function collision with a fifty percent chance in roughly the square root of the total number of possible hash values. While it introduces vulnerabilities in digital signatures, it cannot break an encryption scheme any faster than a standard brute-force attack.

What we know

• A birthday attack is a brute-force collision attack exploiting the mathematics of the birthday problem. [1, 2]
• It can find a hash function collision with a 50% chance in the square root of the total possible hash values. [2, 5]
• Quantum computers are theorized to perform birthday attacks to break collision resistance in the cube root of the hash space. [2] · medium confidence
• A birthday attack cannot break an encryption scheme any faster than a regular brute-force attack. [2]

Still open

• There is a general, though disputed, result regarding how quickly quantum computers can perform birthday attacks.

Where to go next

• how it workedHow does a collision attack work?
• compared withWhat is a preimage attack?
• the bigger pictureHow do cryptographic hash functions operate?
• what followedWhat digital signature vulnerabilities exist?
• what caused itHow does the birthday problem probability work?
• an unexpected connectionWhy do shared birthdays relate to cryptographic cracks?The surprising mathematical overlap is that probability theory guarantees a 50% chance of a collision among just 23 people, which translates directly to cutting the security bits of hash functions in half.

Sources

• [1]birthday attack (Wikidata Q615485) · CC0 1.0
• [2]Birthday attack · CC BY-SA 4.0
• [3]Preimage attack · CC BY-SA 4.0
• [4]Collision attack · CC BY-SA 4.0
• [5]Cryptographic hash function · CC BY-SA 4.0