Marked: REDOS vulnerability - Snyk.io found something

[joshbruce]

Hey there Josh,

I'm Karen, a security analyst for snyk.io.
I saw you've done a ton of work to revive the marked package, and fix the vulnerabilities in it. I wanted to check in with you regarding a different vulnerability, which I believe was not fixed and might've just been missed (according to the advisory, an email was sent to the original maintainer but a public GH issue was never opened).

The vulnerability is a ReDoS, found by Checkmarx, and was assigned the CVE-2017-17461.
You can see the details here. I've ran their PoC and the process indeed crashes.

If you'd like, I could open an issue on github to help monitor the issue, but that's up to you :)

As the vulnerability is already public, am planning to add it to our vulnerability database today, as I would like to notify our users of this issue.

Cheers,
Karen
Security Analyst @ snyk.io

Taggin @Feder1co5oave, @UziTech, @KostyaTretyak

[joshbruce]

https://www.checkmarx.com/advisories/regular-expression-denial-service-redos-vulnerability-marked-npm-package/

[joshbruce]

I double-checked. The highlighted line in the Checkmarx output is still the same regex as what's in master - unless my eyes crossed while I was reading it (quite possible).

Thoughts??

[Feder1co5oave]

Several things don't check out:

1. 37000000 characters are about 30 megabytes, not kilo. That's a huge string.
2. The highlighted regex is for headings, and should fail matching as early as it reaches the '>' in the source string, since the #{1,6} token doesn't match.
   The test string is something like > blockquoteeeeeeeeeee@@@@@...(several @)}. ReDOS usually works for regexes that perform backtracking, which result in exponential time complexity for some specific inputs. This does not seem the case. Maybe it is the blockquote regex at fault here.
3. in the PoC, parsing times are measured including the generation of the 37-megabytes-huge string. This should't be.
4. node fails with the following message:

<--- Last few GCs --->

[2250:0x2be2a30]    19765 ms: Mark-sweep 1414.3 (1459.0) -> 1414.3 (1459.0) MB, 8482.8 / 0.0 ms  allocation failure GC in old space requested
[2250:0x2be2a30]    28182 ms: Mark-sweep 1414.3 (1459.0) -> 1414.3 (1443.0) MB, 8415.6 / 0.0 ms  last resort 
[2250:0x2be2a30]    36534 ms: Mark-sweep 1414.3 (1443.0) -> 1414.0 (1443.0) MB, 8351.0 / 0.0 ms  last resort 


<--- JS stacktrace --->

==== JS stack trace =========================================

Security context: 0x379274c29891 <JS Object>
    2: genstr [/home/federico/marked/redos.js:~4] [pc=0xac1dff4c84f](this=0x3c864958bd31 <JS Global Object>,len=37000000,chr=0x1995dc4ae481 <String[1]: @>)
    3: /* anonymous */ [/home/federico/marked/redos.js:19] [pc=0xac1dff42cff](this=0x140e992c4479 <an Object with map 0x3b38247831d1>,exports=0x140e992c4479 <an Object with map 0x3b38247831d1>,require=0x140e992c4431 <JS Function require (Sha...

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory
   ```
   it looks to me that's a heap memory allocation error, generated in the `genstr` function, i.e. even before calling marked. It might be that I don't have the required RAM to run this kind of task (4GiB installed).

5. the same failure happend on my machine when running the PoC with commonmark instead of marked:

LENGTH: 35000044
[ 1, 123444846 ]

<--- Last few GCs --->

[2419:0x3902a30] 40835 ms: Mark-sweep 1399.7 (1427.8) -> 1399.7 (1426.8) MB, 2309.2 / 0.0 ms allocation failure GC in old space requested
[2419:0x3902a30] 44047 ms: Mark-sweep 1399.7 (1426.8) -> 1399.7 (1426.8) MB, 2340.2 / 0.0 ms allocation failure GC in old space requested
[2419:0x3902a30] 47443 ms: Mark-sweep 1399.7 (1426.8) -> 1399.7 (1426.8) MB, 2535.5 / 0.0 ms last resort
[2419:0x3902a30] 50599 ms: Mark-sweep 1399.7 (1426.8) -> 1399.7 (1426.8) MB, 3156.0 / 0.0 ms last resort

<--- JS stacktrace --->

==== JS stack trace =========================================

Security context: 0x20a5fda9891
2: genstr [/home/federico/marked/redos.js:~8] [pc=0x2d5103562eaf](this=0x385270390831 ,len=35000002,chr=0x308785aae481 3: /* anonymous */ [/home/federico/marked/redos.js:22] [pc=0x2d5103542d6d](this=0x35adde70721 ,exports=0x35adde70721 ,require=0x35adde70589

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory
```

[Feder1co5oave]

It seems that the error is indeed caused by the genstr loop. That result = result + chr is expensive when repeated millions of times and allocates lots of heap space.

When replaced with

var genstr = function (len, chr) {
    var result = chr;
    for (i=1; i<=len; i *= 2) {
        result += result;
    }
    return result;
}

(notice the i *= 2, this needs log(len) steps in fact)

The same string is parsed by marked in fairly reasonable times and does not crash node. It even reaches 134 mb in length without any problem:

LENGTH: 67108907
TIME: [ 5, 516866896 ]
LENGTH: 134217771
TIME: [ 10, 635624980 ]

In fairness, commonmark does better:

LENGTH: 67108907
TIME: [ 0, 781964070 ]
LENGTH: 134217771
TIME: [ 1, 739979868 ]

In other words, the PoC crashed on itself, not marked.

[KostyaTretyak]

It's more like a joke, not a real vulnerability report. The code is written clearly unprofessional, it is completely absurd. I think we should not pay attention to this.

[joshbruce]

https://snyk.io/vuln/npm:marked:20171207 - Snyk is kind of a big deal. So, I'm not sure we are in a position to ignore it.

I'm going to try and loop in someone from the Snyk team - this is actually a service used by the US Gov't to verify security on packages as well; so, again, kind of a big deal.

I'm definitely not understanding why this is classified as a "vulnerability"...what makes a consumer vulnerable if someone does this?

[karenyavine]

Hey,

Our vulnerability lead generator surfaced this recently and I realized it wasn’t covered in the 0.3.9 release (where a few of the vulnerabilities were fixed in). The Checkmarx Vulnerability report states they tried to contact the maintainer at the time, (i’m only assuming email) and there was no reply, so I assumed it fell between the chairs.

Meanwhile, we’re reaching out to the folks at Checkmarx and see if we can get them to input more information on this.

[UziTech]

I ran their PoC on the current master branch using String.repeat() instead of their genstr function and removed the string generation from the time reported and i'm not seeing an exponential increase in time.

I got all the way up to 300,000,000 characters without crashing and that only took 7 seconds to parse, That is about a 280MB string

I'm thinking the string generation was what they were seeing increase the time exponentially.

var marked = require('./');
var renderer = new marked.Renderer();

renderer.blockquote = function (text) {
  var escapedText = text.toLowerCase().replace(/[^\w]+/g, '-');
  return escapedText;
}

for (i=37000000;i<=300000000;i=i+10000000) {
  var str = '> blockquoteeeeeeeeeeeeeeeeeeeeeë@@@@@@@@@' + '@'.repeat(i) + '}';
  console.log("LENGTH: " + str.length);
  var start = process.hrtime();
  marked(str, { renderer: renderer });
  var end = process.hrtime(start);
  console.log(end);
}

[joshbruce]

@karenyavine: Thanks for jumping in and sending the intiial email. I also had the question regarding version numbers when I saw the initial finding - that's why I went to the highlighted code, which I assumed was the part of the call stack that failed because that is still the same in the current master branch.

[joshbruce]

ps. Thanks for continuing to chase it down. The community did some really good work over December to get the vulnerabilities taken care of and we're pretty sure we got them all...but definitely want to make sure as we don't have the knowledge, skills, or tools to run these types of scans ourselves for various reasons.

[joshbruce]

Downgrading to annoying pending furthe discussion with @karenyavine. They're swamped right now; so, maybe be a couple of weeks.

[joshbruce]

ps. @Feder1co5oave and @UziTech - I'm kinda with y'all - this seems like an odd test and I'm still not sure what this makes someone "vulnerable" to exactly. Crashing an app can make someone vulnerable to something...I'm not a security guy; so, yeah, totally at a loss here but would love to learn something new.

[Feder1co5oave]

Well, if for example you use marked on a server a malicious user can take
out your service with a simple DOS attack based on vulnerable regexes.

And about that, I'm pretty sure marked is full of them. It just takes a
willing attacker to find another vulnerable rule. I think there are
automated scans for it too. I certainly cannot claim it is 100% safe from
ReDOS. In fact I'm inclined to do the opposite. If you use complex regexes
chances are you're vulnerable to ReDOS. We either switch off from regexes
or we accept that they can be unsafe and keep driving down this road.
I think we should recommend users that use marked in "production" server
environments to limit the input size to a reasonable threshold, say few
megabytes. That should be enough to avoid running out of heap space and
hanging for more than a few seconds.

[joshbruce]

Fair and thanks.

Maybe this is why other libraries have moved away from regex. Would giving folks the ability to set a character - if they're using it to render on the fly be enough to satisfy the "keepers of all things vulnerabilities"?? (Like a config option.)

Part of Marked's marketing in the README is to allow the parsing of large md files; so, what are we trading off here. Maybe Marked is geared more toward the desktop transformation and static site generator crowds - like a Jekyll or something??

[ErezYalon]

Hello all,

This is Erez from Checkmarx.
Let me start from the bottom line: There is no ReDoS vulnerability in the marked package.
As a result of this thread, we double checked and found It was our mistake.

The advisory was already removed from our website and I will contact MITRE to delete the CVE.
If there is anything else that can/should be done, please let me know.

The way the code was written was indeed problematic. This is to be expected to some extent since the research team members are usually breakers and not builders. The lesson learned here is to double check ReGex PoCs and to quadruple check every PoC when we do not get a response from the developer, before submitting for a CVE.

Sorry about that.

Erez Yalon
Checkmarx AppSec Research Group Manager

[joshbruce]

@ErezYalon: Thank you so much for letting us know.

Also, I work for the gov't as a contractor; therefore, get introduced to a lot of acronyms that collide, can you help me out?

MITRE?
CVE?
PoCs?

Just want to make sure I'm not translating them incorrectly.

Closing.

[UziTech]

@ErezYalon Thank you for all the hard work you guys do at Checkmarx. Finding vulnerabilities is a difficult and absolutely necessary job. I'm sure we have all been a little too eager to get some answers at times.

@joshbruce
CVE - Common Vulnerabilities and Exposures
MITRE - is the company that manages the CVE list https://cve.mitre.org/
PoCs - Proof of concepts

[joshbruce]

@UziTech: Thanks! PoCs was really hanging me up - that's Point of Contact in my world - and given the surrounding context it could have kinda worked. ;)

[karenyavine]

Awesome,
I'll remove the advisory from snyk.io database as well.
cc @joshbruce @UziTech @ErezYalon

[joshbruce]

Working on some things behind the scenes to gain more flexibility in our decisions and collaboration efforts. Going to be adding things that are tied directly to the revival and progress of the project to #956 - unfortunately, I don't think there's a way to remove the other mentioned completely.