English
Menu

What is Birthday attack?

An attack that looks for collisions by exploiting the birthday paradox: in a group of 23 people, the chance that two share a birthday exceeds 50%. When n-bit values are generated at random, the chance that a pair of equal values appears becomes significant after about 2^(n/2) of them. For this reason the collision resistance of an n-bit hash function is taken to be about n/2 bits. With a block cipher whose block is 64 bits, ciphertext blocks start to coincide after about 2^32 blocks (32 GiB) under one key, which is one reason AES with its 128-bit block is used. The same reasoning sets the usage limits when nonces are chosen at random.

Japanese name: 誕生日攻撃

Birthday attack appears in 2 practice questions across 2 topics, including Applied Cryptography, Information Security Basics.

Field: Applied Cryptography

Try it: questions about Birthday attack

Let 1 GiB = 2³⁰ bytes and 1 EiB = 2⁶⁰ bytes. A block cipher with a 64-bit block (such as 3DES) is used in CBC mode to encrypt a large amount of data under one key. Treating the ciphertext blocks as random 64-bit values, which of the following is the approximate amount of data at which, by the birthday paradox, the probability that a pair of identical ciphertext blocks appears can no longer be ignored?

  1. AAbout 4 GiB
  2. BAbout 32 GiB
  3. CAbout 128 EiB
Show answer and explanation

Answer: B. About 32 GiB

A 64-bit block can take 2⁶⁴ values, so by the birthday paradox the probability that a pair of equal values appears can no longer be ignored after encrypting about 2^(64/2) = 2³² blocks (about 39% at 2³² blocks). One block is 8 bytes, so the amount of data is 2³² × 8 = 2³⁵ bytes = 32 GiB. In CBC mode, when two ciphertext blocks match, the XOR of the two corresponding plaintext blocks is revealed, and the Sweet32 attack published in 2016 showed that cookies could be extracted from long HTTPS sessions protected with 3DES. For AES with its 128-bit block, the threshold extends to 2⁶⁴ blocks.

Birthday attack in the explanations

Questions that mention Birthday attack (2)

  1. Let 1 GiB = 2³⁰ bytes and 1 EiB = 2⁶⁰ bytes. A block cipher with a 64-bit block (such as 3DES) is used in CBC mode to encrypt a large amount of data under one key. Treating the ciphertext blocks as random 64-bit values, which of the following is the approximate amount of data at which, by the birthday paradox, the probability that a pair of identical ciphertext blocks appears can no longer be ignored?
  2. For an ideal hash function with a 256-bit output, which combination gives the approximate number of computations needed for a brute-force attack in two cases: finding an input that produces a given hash value (a preimage attack), and finding any two different inputs that produce the same hash value (a collision attack)?

Books on Applied Cryptography Ad

As an Amazon Associate I earn from qualifying purchases.

Related terms

Block cipher mode of operation Cookie (HTTP cookie) AES (Advanced Encryption Standard) Hash function Authenticated encryption (AEAD) Certificate authority Crypto agility Diffie–Hellman key exchange Elliptic-curve cryptography Envelope encryption

Back to the glossary