DOS when run server side

[Tostino]

Hey, just wanted to let you know I've gotten reports from users of my library Nbvcxz that are getting a DOS every so often by specifically crafted passwords.

I even found a tool created by a government contractor used for issuing a DOS against programs using libraries containing the vulnerable (to combination explosion) algorithms from the original zxcvbn implementation:

• https://github.com/twosixlabs/acsploit
• acsploit GoSimpleLLC/nbvcxz#60

I've solved this by implementing a maxLength type configuration...but that isn't totally done yet as I feel like I still need to have it do dictionary checks against the full-length password without any transformations. Working on finishing that feature and putting out a release.

I know this is usually used client side...however Node.js is a thing.

[Tostino]

Just FYI, i've proved this working in your demo site. Even with just a 100 char password, causes browser to timeout while calculating for minutes. Obviously that isn't a big deal for a client side check: "don't do that and it won't freeze up dummy".

But for server side applications, this is a good way for someone to lock you up.

[MrWook]

Thanks for the report! This makes sense 🤔 What do you mean by maxLength. The length of the password or the found substitutions inside the l33t matcher?

On the demo page he l33t string is already killing the browser with only 25 characters and takes 12 seconds for 20 chars.
The string 4@8({[</369&#!1/|0$5 will create 255 substitutions which will be checked against the dictionary matcher which takes 40-50ms each

I personally would go with a maxSubstitutions with a default value of 100. Everything above it will not be checked with the l33t matcher. This would result in a maximum of like 5-6s

[Tostino]

Yes a max length index record for each dictionary, so possibly save the length of the longest string loaded into each dictionary, and only do checks against the dictionary if the part of the password we are checking is sized within what the dictionary even contains. Should short circuit a whole bunch of logic.

One of the other implementations went did it this way: formigarafa/zxcvbn-rb#7

[Tostino]

But yes, the performance of this implementation can be crippled by much smaller lengths of strings. If you fix some of the algorithmic problems that may be causing the slow-down it'll likely improve overall performance on some non-pathological data cases as well.

I was having it run 100 characters of that string run within a second prior to any modifications of Nbvcxz:

----------------------------------------------------------
Commands: estimate password (e); generate password (g); quit (q)
Please enter your command:
e
Please enter the password to estimate:
4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/
----------------------------------------------------------
Time to calculate: 928 ms
Password: 4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/
Entropy: 435.5407709570021
Your password meets the minimum strength requirement.
Time to crack: ONLINE_THROTTLED: infinite (>100000 centuries)
Time to crack: ONLINE_UNTHROTTLED: infinite (>100000 centuries)
Time to crack: OFFLINE_BCRYPT_14: infinite (>100000 centuries)
Time to crack: OFFLINE_BCRYPT_12: infinite (>100000 centuries)
Time to crack: OFFLINE_BCRYPT_10: infinite (>100000 centuries)
Time to crack: OFFLINE_BCRYPT_8: infinite (>100000 centuries)
Time to crack: OFFLINE_BCRYPT_5: infinite (>100000 centuries)
Time to crack: OFFLINE_SHA512: infinite (>100000 centuries)
Time to crack: OFFLINE_SHA1: infinite (>100000 centuries)
Time to crack: OFFLINE_MD5: infinite (>100000 centuries)
-----------------------------------

[MrWook]

Ah yes i implemented it like in the ruby code and the calcTime dropped significantly. For example
"4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/" * 5 dropped from 72s to 4s

But i think i keep the maximum of substitutions and increase the default value. I don't think there is any thing worth it if there are hundreds of substitutions for a password. It will be strong anyway

[Tostino]

I'd honestly agree with you. Maybe measure and see what threshold it starts to degrade performance vs accuracy wise and use that to decide what the limit of substitutions is, rather than just arbitrarily picking 100?

Edit: To answer my own question it looks like I have a magic value of 100 to stop at for my implementation. I forgot I did that.

private static void replaceAtIndex(final TreeMap<Integer, Character[]> replacements, Integer current_index, final char[] password, final List<String> final_passwords)
    {
        for (final char replacement : replacements.get(current_index))
        {
            password[current_index] = replacement;
            if (current_index.equals(replacements.lastKey()))
            {
                final_passwords.add(new String(password));
            }
            else if (final_passwords.size() > 100)
            {
                // Give up if we've already made 100 replacements
                return;
            }
            else
            {
                replaceAtIndex(replacements, replacements.higherKey(current_index), password, final_passwords);
            }
        }
    }

I look at it as this isn't meant to be an exhaustive search, as that would have an unbounded time requirement. We have to limit the search space by making assumptions that will hold up for the general case but may let a couple insecure passwords through thinking they are secure.

The HIBP stuff (I really need to sit down and implement that for Nbvcxz) and the LD calculations help alleviate the need for such an exhaustive search to get a good enough match (if one exists) even for edge cases.

[MrWook]

I just checked the performance with 4@8({[</369&#!1/|0$5+7%2/4@8({[</369&#!1/|0$5+7%2/" and it seems like 100 is already a good value so i will stick with it, too.

I tested it with 100 runs and calculated the avg:
100 subs => 267ms
200 subs => 443ms
300 subs => 619ms