The Square Root Rule

There is an elegant shortcut for birthday-type problems: a collision becomes likely when you have roughly the square root of the total possibilities. Birthdays have 365 options; the square root of 365 is about 19 — and indeed collisions become likely around 23 people, close to that estimate.

This shortcut scales to any domain. A hash function with 2^128 possible outputs? Expect a collision after about 2^64 attempts — still enormous, but the security margin just got cut in half. A database with 1 million possible IDs? Expect a duplicate after about 1,000 entries.