GHSA-22p9-wv53-3rq4

Описание

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:

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:

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:

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

Proof of concept

Measured 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 remediation

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

1. Add the g flag to email_fuzzy, link_fuzzy, link_no_ip_fuzzy, host_fuzzy_test in lib/re.mjs
2. 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
3. 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.

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.