A ReDoS vulnerability exists in matching.coffee

[DarkTinia]

The affected code is located in matching.coffee-line321. It uses the vulnerable regular expression ^(.+?)\1+$. When the match fails, it will cause catastrophic backtracking.
I trigger the vulnerability using the javascript script below

const zxcvbn = require("zxcvbn");
attackStr = '\x00\x00' + ('\x00'.repeat(54773)) + '\n'
zxcvbn(attackStr)

I know this is usually used client side,but when run server side there has possible DOS. It is my pleasure to provide a patch to repair the ReDoS vulnerability.

[Tostino]

Thank you for the additional report. I think it would be a good idea to compile an (internal) list of these problem cases so we can take care of them in all of these libraries and deal with them in a concerted manner. I am also thinking that writing a fuzzer to test performance of edge cases and document them would be a great idea to identify more of these proactively. Would be a great idea to write a simple tool that could be used to test libraries in a whole bunch of different languages, so we don't have to reinvent the wheel over and over again.

[MrWook]

There are three regex in the regex matcher which are all vulnerable. How can we fix those? I'm not that confident with regex 🤔

[Tostino]

@DarkTinia would you mind providing a patch here? I am also not great with regex, so I'd be fumbling my way through it for sure.

[Tostino]

I can reproduce this with Zxcvbn but I cannot get it to kill Nbvcxz with the changes I put in place to have a maxLength configuration (limited to 256 characters by default). I do use the same regex, but it doesn't seem to slow my implementation down like it does to the official impl (this is attackStr = '\x00\x00' + ('\x00'.repeat(100)) + '\n'):

Compared to Nbvcxz:

[DarkTinia]

Matching time using vulnerable regex increases nonlinearly with the length of the attack string.It will cause catastrophic backtracking if a longer attack string is allowed to be used . And this vulnerability may not be exploited if the maxLength is configured.

I want to provide a more robust regex solution and I'm working on it.

[Tostino]

Hey @DarkTinia, any chance you've had any time to work on improving that regex against ReDOS?

[cherviakovtaskworld]

Good day, is there any update on fixing this vulnerability and releasing new version?

[y-nk]

it's an excellent finding, how come this is not reported as a CVE?

[Tostino]

@y-nk No idea how to report something as a CVE is why...but I tried reporting this up through Dropbox's bug report chain and went nowhere:
zxcvbn-vuln-report.pdf

[y-nk]

this a good place to start https://snyk.io/vulnerability-disclosure/