CVE-2022-21680: Inefficient Regular Expression Complexity (CWE-1333)
value: Marked is a markdown parser and compiler. Prior to version 4.0.10, the regular expression `block.def` may cause catastrophic backtracking against some strings and lead to a regular expression denial of service (ReDoS). Anyone who runs untrusted markdown through a vulnerable version of marked and does not use a worker with a time limit may be affected. This issue is patched in version 4.0.10. As a workaround, avoid running untrusted markdown through marked or run marked on a worker thread and set a reasonable time limit to prevent draining resources.
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: 2022-01-14T17:15Z
Repository: https://github.com/markedjs/marked
Language: HTML
Files changed: src/rules.js, test/specs/redos/cubic_def.cjs, test/specs/redos/reflink_redos.html, test/specs/redos/reflink_redos.md
Commit date: 2022-01-12 19:53:48 -0600
Commit message: Merge pull request from GHSA-rrrm-qjm4-v8hf

* fix: fix reflink redos

Co-authored-by: MakeNowJust <make.just.on@gmail.com>

* fix: fix def redos

Co-authored-by: MakeNowJust <make.just.on@gmail.com>

* fix block label for multiple slashes

Co-authored-by: MakeNowJust <make.just.on@gmail.com>
Diff: diff --git a/src/rules.js b/src/rules.js
index d8b60c7d..bb8b3848 100644
--- a/src/rules.js
+++ b/src/rules.js
@@ -23,20 +23,20 @@ export const block = {
     + '|<!\\[CDATA\\[[\\s\\S]*?(?:\\]\\]>\\n*|$)' // (5)
     + '|</?(tag)(?: +|\\n|/?>)[\\s\\S]*?(?:(?:\\n *)+\\n|$)' // (6)
     + '|<(?!script|pre|style|textarea)([a-z][\\w-]*)(?:attribute)*? */?>(?=[ \\t]*(?:\\n|$))[\\s\\S]*?(?:(?:\\n *)+\\n|$)' // (7) open tag
     + '|</(?!script|pre|style|textarea)[a-z][\\w-]*\\s*>(?=[ \\t]*(?:\\n|$))[\\s\\S]*?(?:(?:\\n *)+\\n|$)' // (7) closing tag
     + ')',
-  def: /^ {0,3}\[(label)\]: *\n? *<?([^\s>]+)>?(?:(?: +\n? *| *\n *)(title))? *(?:\n+|$)/,
+  def: /^ {0,3}\[(label)\]: *(?:\n *)?<?([^\s>]+)>?(?:(?: +(?:\n *)?| *\n *)(title))? *(?:\n+|$)/,
   table: noopTest,
   lheading: /^([^\n]+)\n {0,3}(=+|-+) *(?:\n+|$)/,
   // regex template, placeholders will be replaced according to different paragraph
   // interruption rules of commonmark and the original markdown spec:
   _paragraph: /^([^\n]+(?:\n(?!hr|heading|lheading|blockquote|fences|list|html|table| +\n)[^\n]+)*)/,
   text: /^[^\n]+/
 };
 
-block._label = /(?!\s*\])(?:\\[\[\]]|[^\[\]])+/;
+block._label = /(?!\s*\])(?:\\.|[^\[\]\\])+/;
 block._title = /(?:"(?:\\"?|[^"\\])*"|'[^'\n]*(?:\n[^'\n]+)*\n?'|\([^()]*\))/;
 block.def = edit(block.def)
   .replace('label', block._label)
   .replace('title', block._title)
   .getRegex();
@@ -160,12 +160,12 @@ export const inline = {
     + '|^<[a-zA-Z][\\w-]*(?:attribute)*?\\s*/?>' // open tag
     + '|^<\\?[\\s\\S]*?\\?>' // processing instruction, e.g. <?php ?>
     + '|^<![a-zA-Z]+\\s[\\s\\S]*?>' // declaration, e.g. <!DOCTYPE html>
     + '|^<!\\[CDATA\\[[\\s\\S]*?\\]\\]>', // CDATA section
   link: /^!?\[(label)\]\(\s*(href)(?:\s+(title))?\s*\)/,
-  reflink: /^!?\[(label)\]\[(?!\s*\])((?:\\[\[\]]?|[^\[\]\\])+)\]/,
-  nolink: /^!?\[(?!\s*\])((?:\[[^\[\]]*\]|\\[\[\]]|[^\[\]])*)\](?:\[\])?/,
+  reflink: /^!?\[(label)\]\[(ref)\]/,
+  nolink: /^!?\[(ref)\](?:\[\])?/,
   reflinkSearch: 'reflink|nolink(?!\\()',
   emStrong: {
     lDelim: /^(?:\*+(?:([punct_])|[^\s*]))|^_+(?:([punct*])|([^\s_]))/,
     //        (1) and (2) can only be a Right Delimiter. (3) and (4) can only be Left.  (5) and (6) can be either Left or Right.
     //        () Skip orphan delim inside strong    (1) #***                (2) a***#, a***                   (3) #***a, ***a                 (4) ***#              (5) #***#                 (6) a***a
@@ -228,10 +228,15 @@ inline.link = edit(inline.link)
   .replace('title', inline._title)
   .getRegex();
 
 inline.reflink = edit(inline.reflink)
   .replace('label', inline._label)
+  .replace('ref', block._label)
+  .getRegex();
+
+inline.nolink = edit(inline.nolink)
+  .replace('ref', block._label)
   .getRegex();
 
 inline.reflinkSearch = edit(inline.reflinkSearch, 'g')
   .replace('reflink', inline.reflink)
   .replace('nolink', inline.nolink)
diff --git a/test/specs/redos/cubic_def.cjs b/test/specs/redos/cubic_def.cjs
new file mode 100644
index 00000000..eb3110bc
--- /dev/null
+++ b/test/specs/redos/cubic_def.cjs
@@ -0,0 +1,4 @@
+module.exports = {
+  markdown: `[x]:${' '.repeat(1500)}x ${' '.repeat(1500)} x`,
+  html: `<p>[x]:${' '.repeat(1500)}x ${' '.repeat(1500)} x</p>`,
+};
diff --git a/test/specs/redos/reflink_redos.html b/test/specs/redos/reflink_redos.html
new file mode 100644
index 00000000..2815c0f7
--- /dev/null
+++ b/test/specs/redos/reflink_redos.html
@@ -0,0 +1 @@
+<p>[[]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([</p>
diff --git a/test/specs/redos/reflink_redos.md b/test/specs/redos/reflink_redos.md
new file mode 100644
index 00000000..fe1f0cf0
--- /dev/null
+++ b/test/specs/redos/reflink_redos.md
@@ -0,0 +1,3 @@
+[x]: x
+
+[\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\]([

Vulnerable code:   def: /^ {0,3}\[(label)\]: *\n? *<?([^\s>]+)>?(?:(?: +\n? *| *\n *)(title))? *(?:\n+|$)/,
block._label = /(?!\s*\])(?:\\[\[\]]|[^\[\]])+/;
  reflink: /^!?\[(label)\]\[(?!\s*\])((?:\\[\[\]]?|[^\[\]\\])+)\]/,
  nolink: /^!?\[(?!\s*\])((?:\[[^\[\]]*\]|\\[\[\]]|[^\[\]])*)\](?:\[\])?/,
Fixed code:   def: /^ {0,3}\[(label)\]: *(?:\n *)?<?([^\s>]+)>?(?:(?: +(?:\n *)?| *\n *)(title))? *(?:\n+|$)/,
block._label = /(?!\s*\])(?:\\.|[^\[\]\\])+/;
  reflink: /^!?\[(label)\]\[(ref)\]/,
  nolink: /^!?\[(ref)\](?:\[\])?/,
  .replace('ref', block._label)
  .getRegex();

inline.nolink = edit(inline.nolink)
  .replace('ref', block._label)
module.exports = {
  markdown: `[x]:${' '.repeat(1500)}x ${' '.repeat(1500)} x`,
  html: `<p>[x]:${' '.repeat(1500)}x ${' '.repeat(1500)} x</p>`,
};
<p>[[]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([]([</p>
[x]: x

[\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\](\[\]([