GHSA-22p9-wv53-3rq4: LinkifyIt#match scan loop has quadratic algorithmic complexity
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 componentHEAD 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.0Vulnerability detailsThe O(N²) outer loop`index.mjs:528-554`:The loop iterates O(N) times (once per match). Each iteration:`tail.slice()` re-allocates a string of length `|text| - shift` — O(N) per iteration`this.test(tail)` runs three unanchored regex searches over the full new `tail`:Total cost: `Σ(N - i*c) for i=0..N = O(N²)`.Contrast with the linear schema branchThe schema-prefixed scan in the same `test()` function does it correctly at `index.mjs:428-440`:That branch uses a `g`-flag RegExp and advances `lastIndex` — linear. The fuzzy branches don't follow this pattern.Proof of conceptMeasured output (Node v25.5.0, Apple Silicon)Doubling N → ~4× wall-clock, consistent with O(N²).markdown-it transitive (independently confirmed)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 remediationThe 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 tailIn `match()`, drop `tail = tail.slice(...)` entirely — advance a `pos` offset insteadThe schema branch at `index.mjs:428-440` is already structured this way — it's the in-repo precedent for the fix.Total cost becomes O(N): each character scanned at most once per regex across the whole loop.Duplicate-risk analysisZero 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 pipelineThis finding appears novel.Note to maintainersSince `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.
CVSS v4.0: 8.7