Add Levenshtein Distance for dictionaries

[zxcvbn-ts]

Add Levenshtein Distance for dictionaries

[Tostino]

I'd take a look at what I did for the Java "port" I maintain: https://github.com/GoSimpleLLC/nbvcxz

LD calculations were extremely useful, but my god they slow things down. In nbvcxz I have it as a configuration option if we use an LD pass for our dictionary matching algorithm or not.

Here is the meat of it: https://github.com/GoSimpleLLC/nbvcxz/blob/master/src/main/java/me/gosimple/nbvcxz/matching/DictionaryMatcher.java

[Tostino]

So I optimized the LD pretty well for the common case in my implementation. For the vast majority of passwords, we don't even bother getting to that code path. Check all the cases in the DictionaryMatcher where I short circuit the LD code path because the password isn't a good candidate for it to matter. I only bother doing the LD calculation on the whole password rather than each individual part of the password, cutting down the amount of work required immensely.

But your mention of how this is usually tied directly to a field makes that less of a difference. For my Java library since it's server side, I generally just get updates from the input box it's tied to every so often, and then send my estimate back to the client to update the "password strength meter" the calculation is tied to. As a user is typing, I don't necessarily get an update every keystroke to recalculate things with my web framework, so it doesn't cause issues with how I use it.

I like the idea of having different code paths, one with very tight timing that will give some reasonably accurate result as the user is typing, and then a slower code path that is able to get things "right" once they have stopped mashing the keyboard.

[MrWook]

That's what i wanted to do anyway if i implement it :D

Actually i thought exactly the same thing that this will slow down everything extremely. So i thought about making it optional and it would be a good idea to add a debounce zxcvbn function.

Normally this library is used directly on an input field and the distance would make the input really laggy, i guess. So a debounce function which will trigger the real zxcvbn function only after a certain time after the user typed would improve this.

[JonL1]

I was checking some SO topics on this matter and I found this. It might be worth exploring.

https://github.com/gustf/js-levenshtein

[MrWook]

I finally got the time to do a little bit and added the levenshtein distance.
@Tostino i tried your function to measure the distance and ported it to JS, but it took ages to finish. Maybe i did something wrong while porting it to js but it didn't looked to complicated 🤷
But i implemented your other points like using an option and only check the whole password and not every part of it 👍

I don't like to create a dependency but this seems to be the best option for me. The library is super fast and i already saw some changes in the scoring, some comparison cases on the documentation page dropped by one point for the scoring.