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

Why it is Amber

• CVSS 7.5 high
• Public exploit or proof of concept referenced
• Remotely exploitable without logging in
• On your watchlist: Composer

Affected packages

References

• https://github.com/advisories/GHSA-3q6v-r5mr-hxv8
• https://github.com/thephpleague/commonmark/security/advisories/GHSA-3q6v-r5mr-hxv8
• https://github.com/thephpleague/commonmark/commit/5f63680a5e29dd57f9c6be9743b0e90493d3c2d0
• https://github.com/thephpleague/commonmark/releases/tag/2.10.2
• https://github.com/advisories/GHSA-3q6v-r5mr-hxv8

Original description

## 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. ```text 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 <?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); } ``` ```text 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 no