league/commonmark: Quadratic-time denial of service in the GitHub Flavored Markdown Table extension block-start scan

Summary

league/commonmark's GitHub Flavored Markdown Table extension registers TableStartParser as a block-start parser. While a paragraph is the active block, the core block parser calls TableStartParser::tryStart() on every non-blank line. Its first action fetches the entire growing paragraph buffer via getParagraphContent() and runs strpos($paragraph, '|') across all of it. For a paragraph of M pipe-free lines, line k rescans about k lines of buffer, so total work is 1+2+...+M, which is O(M^2). An unauthenticated user who submits a single large paragraph of pipe-free lines that do not begin with a letter (see Attack Chain) to any service that converts untrusted Markdown with GithubFlavoredMarkdownConverter (or any environment that enables TableExtension) drives seconds to tens of seconds of single-core CPU that grows quadratically with body size, enough to exhaust worker processes and deny service.

Root Cause

The GFM table detector performs a per-line "quick check" against the whole accumulated paragraph rather than only the portion that could form a table header. A paragraph never closes while non-blank lines keep arriving, so its buffer grows without bound, and the quick check rescans the entire buffer on each line. Only the paragraph's last line can ever be a table header (it is extracted separately via strrpos/substr), so scanning the full multi-line buffer for a pipe on every line is unnecessary work and creates quadratic time complexity. There is no input-size cap and the default nesting limit is not reached, so nothing bounds the scan.

Affected function: League\CommonMark\Extension\Table\TableStartParser::tryStart
Location: src/Extension/Table/TableStartParser.php:35-38
  $paragraph = $parserState->getParagraphContent();       // returns the FULL growing buffer
  if ($paragraph === null || \strpos($paragraph, '|') === false) {
      return BlockStart::none();                           // strpos scans whole buffer each line
  }
Buffer growth: src/Reference/ReferenceParser.php:89-95 ($this->paragraph .= "\n"; $this->paragraph .= $line;)
Per-line dispatch: src/Parser/MarkdownParser.php:135-147 and :224-236

Impact

An unauthenticated, remote attacker with no user interaction can cause denial of service against any application that renders untrusted Markdown with the GitHub Flavored Markdown converter or any configuration that enables the Table extension (the default GFM bundle enables it). A single request carrying a large paragraph of pipe-free, blank-line-free lines that do not begin with a letter consumes CPU proportional to the square of the input size: measured runs show roughly 4x CPU growth per input doubling. A body of a few megabytes ties up a worker for seconds to tens of seconds; repeated or concurrent requests exhaust all available PHP worker processes, denying service to legitimate users. Impact is limited to availability; there is no confidentiality or integrity impact.

Proof of Concept

Requires PHP with league/commonmark 2.x installed. The harness parses pipe-free paragraphs of increasing size with the real MarkdownParser and the real block-start parsers, comparing a GFM-plus-Table configuration against a core-only configuration to isolate the Table parser's contribution.

1. Install league/commonmark (2.10.1 or any 2.x release).
2. Convert a single large paragraph of pipe-free, blank-line-free lines that do not begin with a letter, with GithubFlavoredMarkdownConverter.
3. Measure wall-clock time as the paragraph size doubles.

<?php
require 'vendor/autoload.php';
use League\CommonMark\GithubFlavoredMarkdownConverter;

$converter = new GithubFlavoredMarkdownConverter();
foreach ([25000, 50000, 100000, 200000] as $lines) {
    $md = str_repeat("12345678\n", $lines); // one paragraph, no blank lines, no '|', lines not starting with a letter
    $t = microtime(true);
    $converter->convert($md);
    printf("%7d lines  %6.3fs\n", $lines, microtime(true) - $t);
}

   lines    input    letter-leading    non-letter-leading
                     ("aaaaaaaa")          ("12345678")
   25000   0.23MB        0.27s               0.75s
   50000   0.45MB        0.50s               2.36s
  100000   0.90MB        1.07s               7.70s
  200000   1.80MB        2.26s              27.81s

Letter-leading input scales linearly (doubles per input doubling) because SkipLinesStartingWithLettersParser aborts before the Table parser is reached. Non-letter-leading input quadruples per doubling (0.75, 2.36, 7.70, 27.81), confirming O(M^2) behavior attributable to the Table start parser.

Attack Chain

1. Exposure: The attacker submits a Markdown body to any endpoint that converts untrusted Markdown with GithubFlavoredMarkdownConverter, or any environment that adds TableExtension. The default GFM bundle registers the Table extension: GithubFlavoredMarkdownExtension adds TableExtension (src/Extension/GithubFlavoredMarkdownExtension.php:30), which registers TableStartParser (src/Extension/Table/TableExtension.php:56).
2. Control: The attacker fully controls the Markdown body. The exploit input is one paragraph with no blank lines, no | character, and lines that do not begin with a letter (for example str_repeat("12345678\n", 200000)).
3. Path: MarkdownParser::parseLine() loops over block-start parsers for every non-blank line while a paragraph is active (src/Parser/MarkdownParser.php:135-147). ParagraphParser::tryContinue() keeps the paragraph open for every non-blank line, so the buffer keeps growing (src/Parser/Block/ParagraphParser.php:46-53), appended line by line in ReferenceParser::parse() (src/Reference/ReferenceParser.php:89-95). Since 2.0.2, the highest-priority SkipLinesStartingWithLettersParser returns BlockStart::abort() for any line whose first non-space character is a letter, short-circuiting findBlockStart() before TableStartParser. When lines begin with a non-letter (e.g. a digit), that parser returns none and every remaining core parser returns null, so control reaches TableStartParser on every line (src/Parser/MarkdownParser.php:224-236).
4. Guard: There is no input-size cap in MarkdownInput, and max_nesting_level defaults to PHP_INT_MAX, which the depth-1 paragraph never approaches. No guard bounds the whole-buffer scan.
5. Primitive: TableStartParser::tryStart() runs strpos($paragraph, '|') over the entire buffer returned by getParagraphContent() (src/Extension/Table/TableStartParser.php:35-38). With no pipe present, strpos scans to the end of the buffer on every line.
6. Result: Cumulative scanning work is O(M^2). A single small request drives disproportionate, quadratically growing CPU, exhausting worker processes and denying service.

Bypass Evidence

No prior fix exists for this code path, so this is not an incomplete-fix or regression case; it is a distinct, previously undisclosed quadratic path. The strongest disproof attempts were made and all failed:

• Attempt: the observed quadratic is core-parser or PHP string overhead, not the Table parser. Refuted: the only difference between the two measured configurations is TableStartParser; the core-only baseline is linear while the isolated Table contribution quadruples per input doubling.
• Attempt: strpos short-circuits or the buffer does not actually grow. Refuted by source trace: ReferenceParser::parse() appends every line unconditionally before its state switch, and for pipe-free text strpos finds no | and scans the full buffer each line.
• Attempt: another parser short-circuits before TableStartParser. Partially correct: since 2.0.2 SkipLinesStartingWithLettersParser aborts block-start scanning for lines beginning with a letter, so letter-leading input (including the original aaaaaaaa PoC) never reaches the Table parser and runs in linear time. Input whose lines begin with a non-letter (e.g. a digit) passes every core parser and reaches TableStartParser on every line, exhibiting the quadratic behavior.
• Attempt: an input-size or nesting guard neutralizes it. Refuted: there is no size cap and the default nesting limit is never reached.
• Attempt: this duplicates an existing quadratic-DoS advisory or was already fixed. Refuted: published quadratic advisories address per-line position translation and other distinct mechanisms in other files; git log on src/Extension/Table/TableStartParser.php shows no security fix ever touched this rescan, and the code is present unchanged in the latest release.

Affected Versions

• Ecosystem: composer
• Package: league/commonmark
• Confirmed affected range: >= 2.0.0, <= 2.10.1
• Latest release checked: 2.10.1 (Packagist, repo.packagist.org/p2/league/commonmark.json)
• Fix status: not fixed

Note: SkipLinesStartingWithLettersParser was introduced in 2.0.2. On 2.0.0 and 2.0.1 the issue can also be triggered with letter-leading lines. Regardless, the underlying quadratic scan itself is present across the whole >= 2.0.0, <= 2.10.1 range.

The vulnerable rescan is artifact-verified present in tags 2.8.0 and 2.10.1 (the latest published release). The lower bound 2.0.0 is inferred from the 2.x block-parser rewrite that introduced the getParagraphContent()-based architecture this quick check depends on; the checkout contains only tags 2.8.0 through 2.10.1, so the path is not artifact-verified below 2.8.0. No published release removes or bounds the whole-buffer scan.

Suggested Fix

Enforce that the per-line quick check inspects only the paragraph's last line, which is the only line that can form a table header. Compute the last line break with strrpos($paragraph, "\n"), derive the last line, and test strpos($lastLine, '|') instead of scanning the whole buffer. This bounds the per-line check to the length of the last line and removes the quadratic behavior without changing table detection semantics. As an interim mitigation without a code change, operators can cap the size of untrusted Markdown accepted for conversion, or disable the Table extension for untrusted input, which reduces exposure but does not remove the underlying quadratic path.

Reported by zx (GitHub: @manus-pi).