GHSA-J8PM-GJ4C-RQ4X: Algorithmic Complexity Denial of Service in league/commonmark

The league/commonmark library is the standard Markdown parsing package for the PHP ecosystem. Under default configurations, it exposes three independent algorithmic complexity weaknesses. These flaws reside in different parts of the parser and do not require custom extensions to trigger. An unauthenticated remote attacker can exploit these weaknesses to cause application-wide Denial of Service.

Algorithmic complexity attacks exploit vulnerabilities where the execution time of an algorithm grows non-linearly with input size. In these cases, very small payloads can lead to severe CPU utilization. This is distinct from network-level flooding attacks because it achieves resource exhaustion using minimal attacker bandwidth.

The vulnerabilities affect three separate execution paths within the library. These are the fenced code block parser, the reference link label normalizer, and the delimiter stack processing engine. When processing maliciously formatted input, the PHP engine wastes significant CPU cycles performing redundant operations, stalling the thread and preventing the system from answering legitimate web requests.

The first path is a Regular Expression Denial of Service (ReDoS) vulnerability in FencedCodeStartParser.php. The parser used a greedy, non-possessive quantifier inside a regular expression to match the opening of code blocks. The regular expression pattern featured a negative lookahead assertion. When the engine failed to find a matching sequence, the non-possessive quantifier forced exhaustive backtracking over each character of the input line.

The second path is a quadratic string normalization flaw in CloseBracketParser.php. When processing reference link brackets, the parser extracts the label and queries the ReferenceMap. Before searching, the library normalizes the label by running multiple passes of high-overhead functions including trim, preg_replace, and multi-byte string functions. In documents containing nested brackets, this normalization is evaluated repeatedly on overlapping substrings, resulting in quadratic time complexity.

The third path lies in the delimiter processing engine where the parser tracks openers and closers for style delimiters. To avoid quadratic back-scanning, the engine relies on a memoization cache using search boundaries. However, because the cache keys included the unclamped raw length of the closing delimiters, an attacker could supply closers of varying lengths to generate distinct keys. This bypassed the cache entirely, falling back to sequential back-scans of the entire stack.

The combination of these three issues represents a severe exposure for applications accepting user-submitted Markdown. An attacker can target any or all of these paths depending on the exact parsing features allowed by the application.

The first fix makes the greedy quantifier possessive in the code block parser. Making the quantifier possessive prevents the engine from backtracking into the matched group of backticks upon subsequent match failures. The execution time is successfully reduced from quadratic to linear.

// Before the fix
$fence  = $cursor->match('/^[ \\t]*(?:`{3,}(?!.*`)|~{3,})/');
 
// After the fix
$fence  = $cursor->match('/^[ \\t]*(?:`{3,}+(?!.*`)|~{3,})/');

The second fix introduces an early length-based escape check in the bracket processor. According to the CommonMark specification, link labels are capped at 999 characters. By measuring the length of the raw bracket sequence before executing any copy or normalization logic, the parser drops oversized spans early.

$start  = $opener->getPosition();
$length = $startPos - $start;
 
// Reject spans longer than the maximum link label length
if ($length > 999) {
    $cursor->restoreState($savePos);
    return null;
}

The third fix limits the cache-key variations generated by delimiters. By capping the delimiter length used for the key generation, the cache key space becomes finite and small. This ensures that even if an attacker passes extremely long sequences of varying delimiters, they will hit existing cache buckets and preserve the linear-time lookup guarantee.

// Clamping the closer length to 2 for emphasis
\\min($closer->getLength(), 2);
 
// Clamping the closer length to 3 for strikethrough/highlight
\\min($closer->getLength(), 3);

Exploitation requires no special privileges and can be performed remotely over HTTP. The target endpoint must accept raw Markdown input from users and render it using a vulnerable version of league/commonmark. Common targets include comment sections, blog platforms, profile bios, and messaging features.

To exploit the ReDoS vulnerability in the fenced code block parser, the attacker sends a payload with a massive run of opening backticks followed by regular text and a single trailing backtick. When the regex engine evaluates the trailing backtick, it is forced to backtrack across the massive run, keeping the execution thread at 100% CPU.

``````````````````````````````````[200,000 backticks]`````````````````````````````````a`

To exploit the reference link lookup vulnerability, the attacker registers a single legitimate reference link definition and then provides deeply nested bracket structures. The parser will evaluate every nested bracket level, invoking the heavy string normalization functions repeatedly.

[x]: y
 
[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[a]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]

The impact of successful exploitation is complete Denial of Service. Because PHP-FPM and similar execution models rely on a fixed number of worker threads, blocking several threads with CPU-heavy loops quickly exhausts the pool. When the worker pool is exhausted, the server can no longer process incoming requests, resulting in gateway timeouts (HTTP 504) for all visitors.

The vulnerability is classified as High severity with a CVSS score of 7.5. The vector breakdown is CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H. This indicates that the vulnerability can be exploited over the network without user interaction or authentication, causing a complete loss of availability.

While there is no threat to confidentiality or integrity, the operational impact of a persistent Denial of Service is significant. Attackers can continually submit malicious payloads to keep worker processes locked indefinitely, effectively taking down the target platform with minimal outbound bandwidth requirements.

The most effective resolution is upgrading league/commonmark to version 2.9.1 or later. This release addresses all three vulnerabilities while maintaining backward compatibility with existing integration patterns.

composer update league/commonmark

If upgrading is not immediately possible, applications should deploy input validation filters. Implementing a pre-parsing check to reject raw Markdown submissions containing lines longer than 2,000 characters is a highly effective mitigation. This restricts the scale of backtracking and normalization loops before the library processes the input.

function preValidateMarkdown(string $content): bool {
    $lines = explode("\\n", $content);
    foreach ($lines as $line) {
        if (strlen($line) > 2000) {
            return false;
        }
    }
    return true;
}

Additionally, operations teams should configure strict execution timeouts in their PHP environment. Lowering max_execution_time in php.ini or configuring request_terminate_timeout in PHP-FPM configuration ensures that threads locked by malicious inputs are terminated automatically, freeing up workers to handle legitimate traffic.