Checking 800M Leaked Passwords in 2MB of RAM with Bloom Filters

When users register or change their passwords, security guidelines (like NIST SP 800-63B) recommend checking their chosen password against a database of known breached passwords.

Data feeds like HaveIBeenPwned contain over 800 million leaked password hashes.

Storing 800 million SHA-1 hashes (20 bytes each) in a standard Hash Map or Redis set requires at least 16 GB of RAM. Performing a SQL database query on every password change adds unnecessary latency to your authentication pipeline.

In this post, we’ll explore how to use a probabilistic data structure—the Bloom Filter—to check hundreds of millions of leaked passwords in under 2 MB of RAM with constant O(k) lookup time.

The Problem: Why Hash Sets Don't Scale in Memory