Can you check if a password is compromised in the browser fast

Ages ago @brson wrote

While I’m thinking about it, I came up with a seemingly good use case for wasm over the weekend, but don’t expect I can carry the project to completion, if somebody else wanted to.

This blog post laid out simple rules for validating the complexity of passwords, and one if it’s biggest points is that people should deny users the ability to use known common passwords. Basically, these days it is best practice to use the many leaked password lists as a blacklist, since users employing these passwords are trivially targeted.

So the idea here is to take the fst crate and encode that giant password list into a hopefully small FST, and do the search fast and compactly. Create a C interface so anybody can use it server-side, then bind that C interface to a JS interface via wasm so anybody can use it client-side. Package it up to produce builds for common platforms and do a ‘Show HN’ to get some karma.

I did a prototype over the weekend but seems likely won’t get much farther any time soon: https://github.com/brson/pwrabs

I mis-remembered the quote and thought he'd suggested phf, which uses hashing, produces bigger binaries, but checks in O(1) (because hashing). Anyway thanks to this fix landing you can build a PHF of all passwords in the rockyou list in a tractable (but very long) time. I've implemented this in common-passwords (there is a limit on the number of passwords set to 1_000_000 but you can just comment out that line in build.rs to build the whole lot). For 1_000_000 passwords the wasm file is about 17M and runs queries instantaneously. If we assume linear increase, that would be at least 272M file for the whole lot, so not mega practical, but was fun anyway :slight_smile:.

Here is the fst version: https://github.com/derekdreery/common-passwords/pull/1
There is a reason Brian suggested the fst crate! This compiles 12× faster on my machine and produces a wasm file that is 3.9× smaller.

1 Like

Haha much better. I'll have a go with the full password list and see how it all plays out :slight_smile:

edit marked as solution because I was basically describing a mistake that I made that the patch fixes haha