Pathological worstcase when password is a hex string

[Mjolnir42]

Hi,

I think I hit an algorithmic pathological worst case, if the supplied password string is a hex encoded string. I have not been able to reproduce this behavior with other, way longer passphrases.

I've created a gist with a testcase: Gist

At the point where I aborted (password length 32 characters), it is was consuming around 7GBytes of RAM.

[Mjolnir42]

Since the initial data came from my laptop, I've also tried it on my workstation. It could not complete the 32 characters before it ran out of memory:

swap_pager: out of swap space
swap_pager_getswapspace(16): failed
pid 1403 (zxcvbn), uid 1001, was killed: out of swap space

I've updated the data comment in the gist, including top output from shortly before it ended. Memory consumption was around 14.5GByte for the 32 character string at that time.

[nbutton23]

hmmm. Ill have to play with it and see if I can figure out where its spending the most time, and why its eating so much memory.

[nbutton23]

So I found where its spending the time. Im not sure if this is where the memory issue is.

https://gist.github.com/nbutton23/b11f57561c6471890bd95ac5a3b52a75

[nbutton23]

Okay after some more digging. I have found that the issue is not in the above code. using pprof I can see that it is in matching.leet.go:getAllPermutationsOfLeetSubstitutions. Since the the string has an abnormally hi number of leet characters (0, 1, 2, 3, 4, 5, 6, 7) it is generating an insane number of permutations.

[t3h2mas]

I ran into this when running against a MD5 hash. Is there a workaround or an option to skip the leet permutations?

[nbutton23]

So @TheMacies just added the ability to filter out matchers.

the call would look like zxcvbn.PasswordStrength(password, nil, matching.FilterL33tMatcher)

[sahib]

Hello @nbutton23,

I'm using your library to an interactive password check in a commandline application Sadly, it's pretty slow with longer inputs (>= 12 characters), due to the code you already posted:

https://gist.github.com/nbutton23/b11f57561c6471890bd95ac5a3b52a75

I'm not sure if all permutations of the string need to be checked there. Maybe it's sufficient enough to only an exact match?

Alternatively one could also try to call this function less often (still n^2 though) and/or make the number of checks depending on the string length (i.e. do exact match if length >= 10, only prefix check if length >= 6)

Sorry for hijacking the issue, just wanted to ask if this is a valid way to go. If so I could also prepare a PR.

[cerlestes]

I ran into the same issue with a similiar string. For testing purposes, I've used UUIDs as passwords, like so:

zxcvbn.PasswordStrength("ce59f9ce-c1ca-4929-ad94-a494c7fbe032", nil)

After a few minutes I've noticed I still had no response from the API only to find that it was consuming nearly 11 GByte of RAM.

This issue needs to be addressed, as it allows for pretty trivial DoS attacks against any software using this library.

[TheMacies]

As a temporary solution, try out the feature I added a while ago. https://github.com/nbutton23/zxcvbn-go/pull/24

[cerlestes]

@TheMacies I've seen that and it works, thank you. But this bug needs to be fixed, not worked around. The obvious quick fix would be to remove L33tMatcher (and others, if the problem exists in more than this one) from the list of matchers enabled by default, and release a bugfix version of this library.

[TheMacies]

Yes. Although i did not want to change the behaviour of this lib after someone updates vendor. That was my primary goal

[edwincarlo]

@TheMacies , @cerlestes , @sahib ,

It was created a pull request ( #28 ) aiming to solve this issue. It would be great if you could check.

[cerlestes]

@edwincarlo Very nice work, thank you. Code is looking good. I'll give the patch a try next week and report back.

[sahib]

@edwincarlo: Great work, I see definite improvements. For a hash string like 68b329da9893e34099c7d8ad5cb9c940 the time has gone from ~7s to a few milliseconds. This finally allows using this library for checking passwords while typing without any crude workarounds.

For reference, the pprof output I made while testing the change: Before applying @edwincarlo's changes and after (second pprof was with a longer password than first to have some more samples, actual timing is 5.37s vs 4ms with same password).

[cerlestes]

Awesome! Instead of killing the process after 60 seconds and 14GB of RAM consumed, my tests are now running through in ~0.1s, when the patch was applied (taken from current master branch).

@edwincarlo Thanks again! @nbutton23 Please release asap :) Thanks!

[dcormier]

Is this still an issue? The last couple of comments suggest that it's been resolved.