Support a bloom filter version of the HIBP list

[Caligatio]

I recently stumbled onto this plugin and was super excited about it until I realized the storage requirements for the HIBP list. Have you looked into supporting some sort of bloom filter version of the HIBP list? I am certainly not the first person to think about doing this but, if your plugin supported it, this could be the first implementation that was actually usable.

I'm happy to try to help!

Quick Edit: You would lose the password count but gain like a 30x storage savings plus potentially a faster lookup.

[mihaifm]

Thanks for the suggestion, interesting idea. I'll look into it.

[Caligatio]

I have some fun ideas how to distribute a possible bloom filter version of HIBP via IPFS+Cloudflare and I'm also happy to produce the actual filter output if it's helpful.

[mihaifm]

I'm thinking to add a button in the options to calculate the bloom filter locally, it shouldn't be too difficult.

[Caligatio]

I don't think code-wise it would be too bad but it does take a significant amount of compute time. Quoting one of the Python implementation comments:

Currently, a k=16 filter with 320M entries (~924MB filter) takes 4 hours to build on my machine (on a ramdisk), which isn't terribly fast, but it's a one-time operation.

I believe the ingest/build time is linear to number of entries so we'd be looking at ~6 hours to build the filter.

[mihaifm]

Hi

It took a while to implement your suggestion, but I finally managed to get something working. Check out the new release, and maybe help test it if you have the time.

https://github.com/mihaifm/HIBPOfflineCheck#bloom-filter

You can generate the filter from the plugin settings. It doesn't take too long to generate it, I tested this on 2 systems:

• older i7 2600k with HDD storage: 40 minutes
• i7 6770HQ with SSD: 15 minutes

[Caligatio]

Just tried it out and it appears to work! 24x space savings isn't too bad at all :)

[mihaifm]

Great, thanks a lot!