Why is CVE-2021-33623 vulnerable to ReDoS?

Question

CVE-2021-33623 states that the following code (fixed in this commit, which includes test cases) has issues related to ReDoS:

trimNewlines.end = string => string.replace(/[\r\n]+$/, '');

But why exactly is it vulnerable to ReDoS?

Answer 1

The time complexity of the regex is O(n²) because the regex engine tries to match the expression at every location inside the string. Mind that regex engine parses the input string from left to right, trying to match at each location after location, and the pattern sequences are also checked from left to right. So, [\r\n]+ is taken first, the regex engine tries to match at the start of string, and if there is no CR/LF chars, the pattern processing at the current location is stopped, the index is moved to the next location inside the string, [\r\n]+ is tried... until it matches CR/LF chars. Only if they are matched, $ is checked for.

So, the [\r\n]+$ does NOT find the end of string and moves back consuming one or more line break chars, rather, the regex engine checks each location in the string for the line break chars, and once found, the end of string is checked for. Thus, if the string is huge, this can cause very low performance.

In some regex flavors, there is a way to tell the regex engine to search for matches from the end of string, as, for example, in .NET (using RegexOptions.RightToLeft option), or in Python PyPi regex module (with regex.REVERSE option or (?r) inline version). Unfortunately, it is not the case in JavaScript.

Probably, the safest would be matching any chars other than linebreak chars followed with line break chars, capturing them, but keeping a long string inside a capturing group is probably not a good idea either. So, while you can consider .replace(/^([\r\n]*[^\r\n]+(?:[\r\n]+[^\r\n]+)*)[\r\n]+$/, '$1') (or .replace(/^((?:[\r\n]*[^\r\n]+)+)[\r\n]+$/, '$1')) which takes 131 (132) steps to complete a match on the given test input compared to 880 steps (needed for the [\r\n]+$ pattern), but just using string manipulation seems the best approach in these situations.