CVE-2019-25103: Inefficient Regular Expression Complexity (CWE-1333)
value: A vulnerability has been found in simple-markdown 0.5.1 and classified as problematic. Affected by this vulnerability is an unknown functionality of the file simple-markdown.js. The manipulation leads to inefficient regular expression complexity. The attack can be launched remotely. Upgrading to version 0.5.2 is able to address this issue. The patch is named 89797fef9abb4cab2fb76a335968266a92588816. It is recommended to upgrade the affected component. The associated identifier of this vulnerability is VDB-220639.
CWE description: The product uses a regular expression with an inefficient, possibly exponential worst-case computational complexity that consumes excessive CPU cycles.
CVSS v3 base score: 7.5
Published: 2023-02-12T15:15Z
Repository: https://github.com/ariabuckles/simple-markdown
Language: JavaScript
Files changed: __tests__/simple-markdown-test.js, simple-markdown.js
Commit date: 2019-08-31 15:17:58 -0700
Commit message: inlineCode: Fix ReDoS & improve escape semantics

Our inline code regex had overlapping parts in the case of spaces;
spaces could be parsed as part of the `\s*`s or as part of the
`[\S\s]*`, which leads to catastrophic backtracking in the case of
a string with many spaces.

The `\s*` parts were attempting to allow for escaping of backticks
within the start/end of inline code blocks, so this commit removes
the `\s*` parts of the regex, and then after parsing the code block,
checks for the case where a single space is being used to escape
a backtick, and removes that space.

Test plan:

1. Added a test for the semantics change.
2. Added a test for the exponential backtracking to match the test
   case in issue #71

Diff: diff --git a/__tests__/simple-markdown-test.js b/__tests__/simple-markdown-test.js
index dbe7855..869a25d 100644
--- a/__tests__/simple-markdown-test.js
+++ b/__tests__/simple-markdown-test.js
@@ -548,10 +548,30 @@ describe("simple markdown", function() {
                 type: "inlineCode",
                 content: "const int * const * const p; // _hi_"
             }]);
         });
 
+        it("should ignore a single space at the start and end of an inline code block separating a '`'", function() {
+            var parsed1 = inlineParse(
+                "test `` ` `` escaping a code block"
+            );
+            validateParse(parsed1, [
+                {type: "text", content: "test "},
+                {type: "inlineCode", content: "`"},
+                {type: "text", content: " escaping a code block"},
+            ]);
+
+            var parsed1 = inlineParse(
+                "test ``  `  `` escaping a code block"
+            );
+            validateParse(parsed1, [
+                {type: "text", content: "test "},
+                {type: "inlineCode", content: " ` "},
+                {type: "text", content: " escaping a code block"},
+            ]);
+        });
+
         it("should allow you to escape special characters with \\", function() {
             var parsed = inlineParse(
                 "\\`hi\\` \\*bye\\* \\~\\|\\<\\[\\{"
             );
             validateParse(parsed, [
diff --git a/simple-markdown.js b/simple-markdown.js
index 2380fe8..8161e0e 100644
--- a/simple-markdown.js
+++ b/simple-markdown.js
@@ -638,10 +638,11 @@ var LIST_ITEM_R = new RegExp(
     "[^\\n]*(?:\\n" +
     "(?!\\1" + LIST_BULLET + " )[^\\n]*)*(\n|$)",
     "gm"
 );
 var BLOCK_END_R = /\n{2,}$/;
+var INLINE_CODE_ESCAPE_BACKTICKS_R = /^ ( *` *) $|^ ( *`)|(` *) $/g;
 // recognize the end of a paragraph block inside a list item:
 // two or more newlines at end end of the item
 var LIST_BLOCK_END_R = BLOCK_END_R;
 var LIST_ITEM_END_R = / *\n+$/;
 // check whether a list item has paragraphs: if it does,
@@ -1579,14 +1580,14 @@ var defaultRules /* : DefaultRules */ = {
             return htmlTag("del", output(node.content, state));
         }
     },
     inlineCode: {
         order: currOrder++,
-        match: inlineRegex(/^(`+)\s*([\s\S]*?[^`])\s*\1(?!`)/),
+        match: inlineRegex(/^(`+)([\s\S]*?[^`])\1(?!`)/),
         parse: function(capture, parse, state) {
             return {
-                content: capture[2]
+                content: capture[2].replace(INLINE_CODE_ESCAPE_BACKTICKS_R, "$1")
             };
         },
         react: function(node, output, state) {
             return reactElement(
                 'code',

Vulnerable code:         match: inlineRegex(/^(`+)\s*([\s\S]*?[^`])\s*\1(?!`)/),
                content: capture[2]
Fixed code:         it("should ignore a single space at the start and end of an inline code block separating a '`'", function() {
            var parsed1 = inlineParse(
                "test `` ` `` escaping a code block"
            );
            validateParse(parsed1, [
                {type: "text", content: "test "},
                {type: "inlineCode", content: "`"},
                {type: "text", content: " escaping a code block"},
            ]);

            var parsed1 = inlineParse(
                "test ``  `  `` escaping a code block"
            );
            validateParse(parsed1, [
                {type: "text", content: "test "},
                {type: "inlineCode", content: " ` "},
                {type: "text", content: " escaping a code block"},
            ]);
        });

var INLINE_CODE_ESCAPE_BACKTICKS_R = /^ ( *` *) $|^ ( *`)|(` *) $/g;
        match: inlineRegex(/^(`+)([\s\S]*?[^`])\1(?!`)/),
                content: capture[2].replace(INLINE_CODE_ESCAPE_BACKTICKS_R, "$1")