Recently I became interested in knowing whether the passwords I used were in the list of breached passwords. One way to find out is to send your password to the link here https://haveibeenpwned.com/Passwords. However, while the owner of that website is a well respected security researcher, I still don't think it's wise to send my password to another website. So I downloaded the 24gb file, hashed my password and grepped the file for it.

That unfortunately took a long time and I realized this was the perfect opportunity to use a BloomFilter and test the inclusion of a password in a set.

With a bloomfilter, the 24gb file can be compressed down to ~2gb assuming a false positive rate of 1 in a million. You can achieve even better rates with lower false positives. Despite it dropping to 2gb, I wasn't satisfied and decided to compress the bloomfilter using golomb codes. This type of data structure is known as a golomb set and I was able to get the database down to ~1.475gb.

That makes it small enough to exist in a microservice that any company can use to test whether users are using hacked passwords. With a golomb set the time to test a password was microseconds. I made some node js bindings and put the file in a simple express app. Now anyone can create a pwned password as a micro-service! It's open source because you can audit the code and confirm no one is logging your passwords.

Anyway thought I'd share it since I'm more or less done with this. Future work could split the 2gb file into on disk files and therefore require significantly less ram to work. This would be a great use case of storing the entire list in a laptop or phone for example, where it would take 1.5gb of disk, but be able to quickly tell you if a password you are typing is in a breached list.

Anyways here's the link:

https://github.com/terencechow/PwnedPasswords

Cheers!