Potential catastrophic backtracking regex vulnerability

[msporny]

From @davisjam via email::

Forge has a regex vulnerable to catastrophic backtracking, which may lead to poor performance (if used client-side) or a REDOS vulnerability (if used server-side, esp. on attacker-controlled input).

I am not sure how likely this is in your case, but given the popularity of your module (6.8M downloads/month!) I thought I would let you know.

Regex:

lib/form.js

var _regex = /(.*?)\[(.*?)\]/g;

(introduced in 2011, 6d4e32e)

Here is a sample attack string:

{"pumpPairs":[{"pump":"[","prefix":"a"}],"suffix":"["}

i.e. "prefix" + "pump a bunch of times" + "suffix".

The catastrophic backtracking follows a power law: f(x) ~= a * x^2.58, where x is the number of pumps. On my machine, about 3K pumps (about 3K chars) blocks the node event loop for 10 seconds.

Fix advice
If you want to fix it, you can refactor the regex (the problem lies in the adjacent overlapping quantified classes .* ... .*) . You could also replace it with custom parsing. If legitimate input strings should be no longer than, say, a few hundred characters you could also simply trim the input.

Let me know if you have any questions.

If you are not familiar with REDOS, here are some good starting points for information:

• https://docs.microsoft.com/en-us/dotnet/standard/base-types/backtracking-in-regular-expressions
• https://docs.microsoft.com/en-us/dotnet/standard/base-types/best-practices#Backtracking
• https://snyk.io/blog/redos-and-catastrophic-backtracking

[davidlehn]

The issue title is perhaps a bit too dramatic. The form.js part of this library is ancient, unrelated to the crypto parts, probably not used by anyone including the authors, and likely to be purged at some point.

[murgatroid99]

I hope I didn't miss something, but I think this problem can be solved without changing the functionality by changing the regex to /([^[]*?)\[(.*?)\]/g. The use of the lazy star quantifier in the first capturing group in the original regex indicates that for any successful match, the first capturing group should never contain a [. So, if we enforce that explicitly, we should be able to avoid this catastrophic backtracking. Does that look right?

[davisjam]

The pattern you propose is safe because it removes the ambiguity of the current pattern. Once a [ is seen the engine can't backtrack back to the first group.

As to regressions/language consistency: if the input has one pair of braces then the pattern is unquestionably a good fit. If the input might have multiple braces, might want to check some sample cases.

[murgatroid99]

It looks like I got it almost right. Normally in a regex, the . does not match newline characters, so to be consistent, the character class there should actually be [^[\n]. With that change, I can't find a string that produces different results with the different regexes.

[davidlehn]

For anyone who wants to capture the infinite glory of fixing this issue, and therefore many snyk nag emails, please submit a PR. I'm not sure how to test this. No one likely uses it. Maybe no one ever has? There is a "legacy" test page you can load up on the test server:

npm run build
npm run test-server

[davisjam]

I can fix this if someone can tell me how to add a test to the suite to invoke the APIs defined in lib/form.js.

[davidlehn]

There are no test suite tests for the form code. There is a manual thing in tests/legacy/form* that can perhaps be used to test changes? You may have to guess what the expected output should be. Run that as I mentioned earlier. Please don't add a serious test suite or spend too much effort on a patch for this. A better solution is to just yank that form code entirely, but a one-liner fix would be a nice short term fix.

[davisjam]

I tweaked the regex in #570 to be safe.

[davidlehn]

Fix published in 0.7.4.

Inquiring minds want to know if there could be a redos regex bug in the regex snyk uses to scan for redos regex bugs.

[davisjam]

Inquiring minds want to know if there could be a redos regex bug in the regex snyk uses to scan for redos regex bugs.

The scanning tools are my work, not Snyk's. They use the babel/babylon/whatever parser for JavaScript code. I haven't scanned that repo for vulnerabilities -- sounds like an interesting query to run once my machines are free.

[davidlehn]

@davisjam Ah, ok, my apologies. Yeah, would be interesting if bug finding tools can find bugs in themselves.