birthday-bound · shipping · also Birthday collision bound

Birthday bound

The birthday bound describes how the probability of any hash collision grows with the number of distinct inputs sharing an output space.

For n distinct inputs with independent uniform b-bit digests, the probability of at least one collision is 1 - product(1 - i/2^b), for i from 0 to n-1 and n <= 2^b. It is one when n exceeds the output-space size. The upper bound min(1, n(n-1)/(2*2^b)) follows by counting unordered pairs. The expression 1 - exp(-n(n-1)/(2*2^b)) is an approximation, not the exact product. [1]

This is not a measured storage failure rate. One specified pair, repeated comparisons against a fixed target, and all pairs in an archive are different events. The random-function model does not require random file contents, but it does assign independent outputs only to distinct inputs. Rehashing identical bytes adds no new distinct input. [1]

Hesela's exact four-input, two-bit example has 232 colliding assignments out of 256, giving 29/32. The downloadable code checks small spaces exhaustively and labels its large-population calculations as approximations. A billion distinct inputs with ideal 64-bit outputs give about 2.67410e-2 for any collision, not the one-pair value 2^-64. These are hypothetical arithmetic results, not cryptanalysis. [3]

Historical papers discussing SHA-1 are not current algorithm recommendations. Collision resistance and second-preimage resistance concern different attack goals; digest width alone does not establish a concrete function's security. [2]

Relations

related
Hash collision, Data deduplication, Cryptographic hash function

Limitations

  • An all-pairs archive calculation is inappropriate for a system that compares only selected corresponding pairs; the comparison namespace and horizon must be specified. [1]
  • Ideal random-output arithmetic does not account for chosen-input attacks, implementation errors, stale metadata or hardware faults. [1, 2]

Citations

  1. J. Black. Compare-by-Hash: A Reasoned Analysis. USENIX ATC 2006, pp. 85-90; sections 2-3 and appendix A. (accessed 2026-11-20)
  2. NIST CSRC: Hash Functions, security strengths and SHA-1 transition. (accessed 2026-11-20)
  3. Hesela: archive-wide collision populations, exact toy oracle and ideal-hash arithmetic. (accessed 2026-11-20)
Sources & caveats
  • Primary-source synthesis and original arithmetic, not a new theorem or an empirical collision sample.
  • Reproducible model, tests, limitations and source metadata: https://hesela.dev/research/birthday/README.md

JSON: /data/terms/birthday-bound.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Birthday bound. Hesela. 2026-11-20. https://hesela.dev/terms/birthday-bound/