redos in es5-ext about es5-ext HOT 24 CLOSED

Hi everyone!
I also found the inefficient regex issue in copy.js from my side.
It is recommended to disclose this type of security issues privately. However, as this was already made public, I will share here a PoC I discovered which triggers the ReDoS by abusing copy.js usage directly:

const copy = require('es5-ext/function/#/copy');
var payload = function CRASHCRASHCRASHCRASHCRASHCRASHCRASHCRASHCRASHCRASHCRASHCRASHCRASH(consoleLog = () => console.log("bu")) {consoleLog();}
var copiedFunction = copy.call(payload);

from es5-ext.

@SCH227 Thanks for putting light on that. So, apparently, there's a real-world case where this issue can be triggered.

I will work this week on fixing that. I don't think there's a reliable way to fix the regexp (if you feel otherwise, I'll be grateful for a hint). The solutions I see:

• In function/#/copy - we can simplify regex just to retrieve the function name. Other logic can be easily refactored to not rely on parsed-out arguments input
• In function/#/to-string-tokens - there's no simple solution. I think I should switch from regex to a state machine based parser as esniff

from es5-ext.

@medikoo, thank you for the prompt response, and for this awesome project!

Your proposed solutions make sense to me. I believe they will narrow the attack surface, complex regexes are hard to debug so prone to errors. But if you want to keep them, I have these ideas:

• The root cause of the exponential complexity in copy.js regex seems to be the nested quantifier. Does a regex like ^\s*function\s*([\0-')-\uffff]*)\s*\(([\0-(*-\uffff]*)\)\s*\{ fails in any corner case you know?
• The previous proposed fix (and also the regex in to-string-tokens.js) is still vulnerable to a lesser complexity backtracking. If it is not mandatory to allow arbitrary whitespaces, a mitigation to this issue is to limit them: ^\s{0,10}function\s{0,10}([\0-')-\uffff]*)\s{0,10}\(([\0-(*-\uffff]*)\)\s{0,10}\{ . That, together with limiting the maximum length of the function declaration to parse to a reasonable value, may make exploitation unfeasible.
• Another possibility would be to implement another function stripWhitespaces(), in charge of filtering out unnecessary sequences of whitespaces before String().match(re)

from es5-ext.

@SCH227 very good point. I've created it: GHSA-4gmj-3p3h-gm8h

from es5-ext.

The root cause of the exponential complexity in copy.js regex seems to be the nested quantifier.

Indeed, great find 👍 I didn't notice that quirk there. I believe (and as I tested) changing (x+)* into (x*) won't make any functional difference, and is cleaner.

If it is not mandatory to allow arbitrary whitespaces, a mitigation to this issue is to limit them

This is more controversial, as functions can be defined with absurd whitespace gaps, and its stringified form will reflect that. Still, as I test, we don't have to restrict too much, e.g., we can do \s{0,100}, and then putting the process on a stall should no longer be possible. WDYT?

I believe I can go with that, and in the unlikely event of a real-world case where it appears to be breaking, I'll probably revert to a state-machine-based idea.

from es5-ext.

Yes, str1 case was only meant for timing purposes.

I agree, that would be the best quality solution.

Actually, my PoCs rely on the fact that the regex doesn't match some valid function cases. You can see that if there's a match, backtracking does not occurs:

• No match and backtracking: https://regex101.com/r/75qvPb/1
• Match and no backtracking: https://regex101.com/r/692I41/1

from es5-ext.

@GAP-dev and @SCH227 big thanks in helping coining that issue

Fixed with:

• 3551cdd
• a52e957

Published with v0.10.63

from es5-ext.

@medikoo thank you for the fix!
Do you believe this issue applies for creating a repository security advisory? If so, please include @GAP-dev and me as reporters/analysts

from es5-ext.

@GAP-dev, thanks for opening that.

Have you approached the real-world scenario when that happened?

In normal circumstances, I believe ReDos cannot happen, as this regex is run only on function string representations where, by design, we cannot get into excessive backtracking (see that first group excludes ( character, which in all cases will follow the group (e.g., 'function ' + 'n'.repeat(31) + ' (){} which is a valid representation match on the spot.

Your test example ('function{' + 'n'.repeat(31) + '){') doesn't show a valid function string representation

Such an attack would require overriding toString on a function instance first (so it returns an invalid string that triggers the issue). Still, this should be out of scope as if an attacker can manipulate the objects in the process. Similarly, we can just run an infinite loop to block the process.

from es5-ext.

Yes, This vulnerability can't exploit right now.

It seems that the input string is being sanitized. However, this is a potential vulnerability. If combined with another vulnerability, it could be exploited in a real-world service.

It should be implemented to further protect the system from potential attacks.

It's always a good practice to assume that attackers can and will find and exploit vulnerabilities, so a defense-in-depth approach, employing multiple layers of security controls and measures, is highly recommended.

from es5-ext.

@GAP-dev what solution do you propose?

from es5-ext.

/^\sfunction\s+[a-zA-Z_$][0-9a-zA-Z_$]\s*([^\)])\s{/
like this

from es5-ext.

@GAP-dev Version you propose is broken:

const re = /^\sfunction\s+[a-zA-Z_$][0-9a-zA-Z_$]\s*([^\)])\s{/

console.log(re.test(String(function myFuńctión() { })))

Logs false

from es5-ext.

oh, sorry
/function\s+([\p{L}$][\p{L}\p{N}$])\s()\s*{\s*}/gu
how about this?

const regex = /function\s+([\p{L}_$][\p{L}\p{N}_$]*)\s*\(\)\s*\{\s*\}/gu;
const str = `
function myFuńctión() { }
function myfunciton() { }
function F() { }
function add() { }
`;
let m;
while ((m = regex.exec(str)) !== null) {
    console.log(m[1]);
}

from es5-ext.

@GAP-dev what you test above is not a valid function string representation, also in this package we need to support all ES5+ engines, while u flag was introduced with ES2018

from es5-ext.

or
/^\sfunction\s(.)?\s((.))?\s*{/
😅

from es5-ext.

@GAP-dev

const re = /^\sfunction\s(.)?\s((.))?\s*{/

console.log(re.test(String(function myFuńctión() { })))

Prints false

from es5-ext.

sorry...

const re =  /^\s*function\s*(.)*\s*\(([\0-(*-\uffff]*)\)\s*\{/
console.log(re.test(String(function myFuńctión() { })))

from es5-ext.

@GAP-dev this also won't work, as matching groups need to properly capture function name and its arguments, with what you've proposed we get n in function name matching group

from es5-ext.

@GAP-dev Ideally would be if you propose change as PR, as then tests will automatically pick issues for you

from es5-ext.

Mostly I agree.
On my tests, the regex /^\s{0,100}function\s{0,100}([\0-')-\uffff]*)\s{0,100}\(([\0-(*-\uffff]*)\)\s{0,100}\{/ executes in around 1 second for a backtracking payload of length 20,000 (vs. ∼0.2 ms for a no backtracking one).
If you believe that limiting functions length to something in the order of 10,000 will not break real-world use-cases, I would go for adding that too so to avoid the chance of abusing the regex with loong payloads.

from es5-ext.

executes in around 1 second for a backtracking payload of length 20,000

By "backtracking payload," do you mean backtracking function body? If so, we can skip that in regex (so keep regex as you pasted in the last comment)

On my side, this regex executes in 11ms for function with a string length of 30,000, and it doesn't seem to get greater for more extensive functions (I got same result for 200,000 length)

from es5-ext.

Sorry if I was not clear enough, let me explain.
After fixing the nested quantifier, the regex is still vulnerable to a lesser complexity catastrophic backtracking but with a different payload. I compared the times of execution for a payload causing backtracking and for another one that does not, seeing how they grow with the payload length:

const regex = /^\s{0,100}function\s{0,100}([\0-')-\uffff]*)\s{0,100}\(([\0-(*-\uffff]*)\)\s{0,100}\{/;

// String known to NOT cause catastrophic backtracking
const str1 = 'a'.repeat(5000);

// String known to cause catastrophic backtracking
const str2 = 'function' +' '.repeat(5000) + '(consoleLog = () => console.log("bu")) {consoleLog();}';

console.time('Execution Time - No Backtracking');
const result1 = regex.test(str1);
console.timeEnd('Execution Time - No Backtracking');

console.time('Execution Time - Backtracking');
const result2 = regex.test(str2);
console.timeEnd('Execution Time - Backtracking');

Output:

Execution Time - No Backtracking: 0.187ms
Execution Time - Backtracking: 253.638ms

For a payload length of 20,000:

Execution Time - No Backtracking: 0.192ms
Execution Time - Backtracking: 1.036s

For a payload length of 200,000:

Execution Time - No Backtracking: 0.358ms
Execution Time - Backtracking: 10.456s

from es5-ext.

@SCH227, thanks for the explanations.

I don't think it makes sense to take into account the str1 case, as it doesn't reflect a valid function string.

Concerning other cases, after thinking it through, I think the best would be to switch to a state-machine approach, as even if we improve regex with proposed suggestions, it'll remain invalid for some ES2015+ function cases (which were not around when this utility was originally written).

e.g. it'll fail for: function (foo = function () {}) {}, and this cannot be handled with regex (at least not with one we have in JS engine).

Therefore, I think the ultimate solution would be to refactor this to esniff based version, I'll take care of it in next days

from es5-ext.