Blooming Password

A program that implements the NIST 800-63-3b Banned Password Check using a bloom filter built from the Have I been pwned 2.0 SHA1 password hash list. The Have I Been Pwned 2.0 SHA1 password hash list contains more than 500 million hashes and is 30GB uncompressed (as of June 2018). The bloom filter of these SHA1 password hashes is only 860MB and will fit entirely into memory on a virtual machine or Docker container with 2GB of RAM.

Partial SHA1 Hashes

SHA1 hashes are 20 bytes of raw binary data and thus typically hex encoded for a total of 40 characters. Blooming Password uses just the first 16 hex encoded characters of the hashes to build the bloom filter and to test the filter for membership. The program rejects complete hashes if they are sent.

False positive rates in the bloom filter are not impacted by the shortening of the SHA1 password hashes. The cardinality of the set is unchanged. The FP rate is .001 (1 in 1,000).

Why a Bloom Filter?

It's the simplest, smallest and fastest way to accomplish this sort of check. It can easily handle billions of banned password hashes with very modest resources. When a test for membership returns 404 then it's safe to use that password.

How to Construct the Partial SHA1 Hash List
        $ cut -c 1-16 pwned-passwords-2.0.txt > 16.txt

        $ wc -l pwned-passwords-2.0.txt 
        501636842 pwned-passwords-2.0.txt

        $ sort -T /tmp/ -u 16.txt | wc -l
        501636842

        $ head 16.txt 
        7C4A8D09CA3762AF
        F7C3BC1D808E0473
        B1B3773A05C0ED01
        ...
How to Create the Bloom Filter Test the Bloom Filter for Membership

Send the first 16 characters of the hex encoded SHA1 hash to the Blooming Password program. Some examples using curl:

Return Codes Notes