Lion Cipher Lab
Build a Bloom filter for breached-password screening, and measure its false-positive rate
- Foundations
- Intermediate
- ~75 min (about 25 of it is your computer crunching)
- Free · no account required
Why it matters
NIST's password guidance says that when someone sets or changes a password, the service SHALL compare it against a blocklist of commonly used, expected or compromised passwords, and make them pick another if it is on the list. That list can be big. The obvious ways to hold it are a database or an in-memory set, and a set of one million passwords took 86 MB in this lab. A BLOOM FILTER holds the same million in 1.2 MB and answers in one of two ways: 'definitely not on the list' or 'probably on the list'. It is a classic tool, and it shows up in browsers, databases and caches. But it only works…
What you'll learn
- building a Bloom filter from scratch in about 60 lines of standard-library Python: a bytearray of m bits and k positions per item from one SHA-256 digest by double hashing
- deriving m and k from a target false-positive rate with the standard formulas (1,000,000 passwords at 1% needs 9,585,059 bits, 1.20 MB, and k=7)
- measuring a false-positive rate on a disjoint test set and comparing it to theory (real run: 1.0325% measured vs 1.0039% predicted; 0.0930% vs 0.1000%; 0.0070% vs 0.0100%)
- proving the one-sided guarantee: zero false negatives across all 1,000,000 inserted passwords, for every size
- showing what mis-sizing costs: the wrong k at the right m (k=1 gave 9.89%, k=25 gave 14.70%) and overfilling 4x past design (1% became 68.0%)
- comparing memory honestly: 1.2 MB for the filter vs 86.1 MB for a Python set and 60.6 MB for a sorted list, and noticing the pure-Python filter is the slowest lookup of the three
- measuring why you cannot delete from a plain filter (4,974 other breached passwords became misses) and what a counting filter costs instead (8x the memory)
- showing that an unkeyed filter file is not a secret (anyone holding it confirmed all 5,000 breached guesses offline), that an HMAC key stops that, and pairing the filter with an exact second-stage check so a fine password is never wrongly rejected
Steps in this lab
- The problem: screen new passwords against a big blocklist without holding the whole list
- Set up: a terminal, Python, and a lab folder
- Generate a synthetic 'breach' and a disjoint clean set
- Build the filter: m bits, k positions, double hashing
- Size it from a target false-positive rate, then measure the real rate
- Mis-size it on purpose: the wrong k, and an overfilled filter
- Memory and speed: the filter vs a set vs a sorted list
- Honest negative 1: a false positive is a person told their fine password is breached
- Honest negative 2: you cannot delete from a plain Bloom filter
- Honest negative 3: the filter file is not a secret
- Do it better: where a Bloom filter fits in a real password check