redos in es5-ext

[GAP-dev]

Test Environment:

Apple M1 macbook air, 2020 (ventura 13.3.1)

node module

name : es5-ext

node js

version : v18.16.0

2023_09_26

이동하 ( Lee Dong Ha of ZeroPointer Lab )

강성현    ( kang seonghyeun )

박성진    ( sungjin park )

김찬호    ( Chanho Kim )

이수영    ( Lee Su Young )

김민욱    ( MinUk Kim )

Team : For CVE

Subject : ReDoS_Vulnerability_Report_in_the_es5-ext_Module_copy.js_2023-09-26 011618.041116.txt

Dear es5-ext team,
I am writing to report a potential ReDoS (Regular Expression Denial of Service) vulnerability in your es5-ext module. It has come to my attention that the current regex implementation for parsing values in the module is susceptible to excessive backtracking, leading to potential DoS attacks.The regex implementation in question is as follows:

/^\sfunction\s([\0-')-\uffff]+)\s(([\0-(-\uffff]))\s*{/

This vulnerability can be exploited when there is an imbalance in parentheses, which results in excessive backtracking and subsequently increases the CPU load and processing time significantly. This vulnerability can be triggered using the following input:

'function{' + 'n'.repeat(31) + '){'

Here is a simple PoC code to demonstrate the issue:

const protocolre = /^\sfunction\s([\0-')-\uffff]+)\s(([\0-(-\uffff]))\s*{/;

const startTime = Date.now();
const maliciousInput = 'function{' + 'n'.repeat(31) + '){'

protocolre.test(maliciousInput);

const endTime = Date.now();

console.log("process time: ", endTime - startTime, "ms");

Modification adds a limit to the number of digits, thereby preventing the ReDoS vulnerability from occurring.
I believe it is crucial to address this issue promptly to ensure the security of your module for all users. Please let me know if you need any further information or assistance with this matter.

https://www.npmjs.com/package/es5-ext

[medikoo]

@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.

[GAP-dev]

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.

[medikoo]

@GAP-dev what solution do you propose?

[GAP-dev]

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

[medikoo]

@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

[GAP-dev]

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]);
}

[medikoo]

@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

[GAP-dev]

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

[medikoo]

@GAP-dev

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

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

Prints false

[GAP-dev]

sorry...

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

[medikoo]

@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

[medikoo]

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

[SCH227]

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);

[medikoo]

@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

[SCH227]

@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)

[medikoo]

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.

[SCH227]

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.

[medikoo]

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)

[SCH227]

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

[medikoo]

@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

[SCH227]

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

[medikoo]

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

Fixed with:

• 3551cdd
• a52e957

Published with v0.10.63

[SCH227]

@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

[medikoo]

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