Bruteforce and suboptimal scoring chains

[llamadonica]

In my example lucky_buster_duke is chunked into lucky_, buster, _, duke with an overall number of guesses of approximately 10^13, mostly due to lucky_ being scored as a bruteforce segment with.

Using your own scoring methods, breaking it up into lucky, _, buster, _duke would have a much lower guesses score of around 10^12, but this pattern is not evaluated for some reason. It's the same number of chunks: I know the scoring methods give factorial growth to the guesses score, but that would not matter in this case.

I think there might be an bug in the bruteforce segment generator or the scoring segment back-tracker.

[Tostino]

That was something I noticed was off with the matching algorithm when I re-implemented zxcvbn in Java. I ended up doing a bunch of work and coming up with a couple new algorithms to find matches and what to consider brute force or not. One of those algorithms is slow and correct, but with a large enough problem space will continue matching until the heat death of the universe, the other is faster but much less correct. I have a heuristic to know that if too much time has elapsed, I should stop using the slow / correct one and switch to the fast one.

The algorithms I came up with can be found here: https://github.com/GoSimpleLLC/nbvcxz/blob/master/src/main/java/me/gosimple/nbvcxz/Nbvcxz.java

Here is the output using console mode from my port:

PS E:\Downloads> java -jar .\nbvcxz-1.4.0.jar
Commands: estimate password (e); generate password (g); quit (q)
Please enter your command:
e
Please enter the password to estimate:
lucky_buster_duke
----------------------------------------------------------
Time to calculate: 10 ms
Password: lucky_buster_duke
Entropy: 30.872189174548
Your password does not meet the minimum strength requirement.
Warning: This is a top-100 common password.
Suggestion: All-uppercase is almost as easy to guess as all-lowercase.
Suggestion: Capitalization doesn't help very much.
Suggestion: Predictable substitutions like '@' instead of 'a' don't help very much.
Suggestion: Reversed words aren't much harder to guess.
Suggestion: Add another word or two. Uncommon words are better.
Time to crack: ONLINE_THROTTLED: 31 years
Time to crack: ONLINE_UNTHROTTLED: 7 months
Time to crack: OFFLINE_BCRYPT_14: 3 months
Time to crack: OFFLINE_BCRYPT_12: 27 days
Time to crack: OFFLINE_BCRYPT_10: 6 days
Time to crack: OFFLINE_BCRYPT_5: 5 hours
Time to crack: OFFLINE_SHA512: instant
Time to crack: OFFLINE_SHA1: instant
Time to crack: OFFLINE_MD5: instant
-----------------------------------
Match Type: DictionaryMatch
Entropy: 8.566054038171092
Token: lucky
Start Index: 0
End Index: 4
Length: 5
Dictionary: passwords
Dictionary Value: lucky
Rank: 379
Length: 5
Leet Substitutions: false
Reversed: false
Distance: 0
-----------------------------------
Match Type: SeparatorMatch
Entropy: 3.3219280948873626
Token: _
Start Index: 5
End Index: 5
Length: 1
-----------------------------------
Match Type: DictionaryMatch
Entropy: 5.426264754702098
Token: buster
Start Index: 6
End Index: 11
Length: 6
Dictionary: passwords
Dictionary Value: buster
Rank: 43
Length: 6
Leet Substitutions: false
Reversed: false
Distance: 0
-----------------------------------
Match Type: SeparatorMatch
Entropy: 3.3219280948873626
Token: _
Start Index: 12
End Index: 12
Length: 1
-----------------------------------
Match Type: DictionaryMatch
Entropy: 10.236014191900086
Token: duke
Start Index: 13
End Index: 16
Length: 4
Dictionary: passwords
Dictionary Value: duke
Rank: 1206
Length: 4
Leet Substitutions: false
Reversed: false
Distance: 0