GHSA-jfm3-95jq-q3rf: Algorithmic Complexity Denial of Service and Path-Delimiter Injection in league/commonmark Footnote Extension

league/commonmark is a widely adopted Markdown processing library for PHP. The FootnoteExtension, introduced in version 1.5.0, enables native parsing and rendering of footnotes and their associated backreferences. This extension is typically used in applications accepting rich-text content from users, such as content management systems, blogs, or collaborative portals.

Because the footnote parser processes document structure prior to final HTML generation, it exposes an unauthenticated attack surface to anyone capable of submitting Markdown content. If the extension is enabled, an attacker can exploit structural processing weaknesses to trigger severe denial of service conditions. The issues stem from algorithmic inefficiencies and insecure key-value configuration storage mechanisms inside the parser's event-driven pipeline.

The vulnerability is tracked under GitHub Security Advisory ID GHSA-jfm3-95jq-q3rf. It has a CVSS v3.1 base score of 7.5, reflecting a high-severity impact on system availability. Remediation requires an update to the underlying library or disabling the affected extension altogether.

The vulnerability consists of two primary logical failures in the Footnote extension parser. The first failure is an algorithmic complexity issue ($O(N^2)$ complexity) located in the interaction between footnote definitions and their backreferences. The second failure is an injection vulnerability resulting from path delimiter parsing inside the library's internal configuration management system.

In the first issue, the parser processes footnote definitions using an event listener called GatherFootnotesListener. Under normal conditions, a single footnote definition maps to one or more references. However, the parser fails to enforce uniqueness constraints on footnote labels. When multiple duplicate footnote definitions exist for the same label, the system processes every duplicate definition block separately and associates each block with all existing backreferences. This creates an $O(M \times N)$ operational multiplier, where $M$ is the number of footnote references and $N$ is the number of duplicate footnote definitions.

In the second issue, the NumberFootnotesListener stores footnote references inside a metadata configuration dictionary managed by $document->data. This data container processes keys containing period (.) or slash (/) characters as nested path delimiters. Because the footnote destination labels are derived directly from user input, an attacker can inject path-delimiter characters. This causes the data manager to interpret literal strings as multidimensional array indices, leading to structural collisions, data mutation, or fatal PHP type mismatches.

To understand the structural failure, we examine the logic of GatherFootnotesListener and NumberFootnotesListener prior to commit 66028124a17ba193da7b11cc3dfda92df21bfbf4.

In the vulnerable implementation of the footnote accumulator, the iterator iterates over all block nodes without checking if a given footnote label has already been declared. This allows redundant Footnote nodes to remain within the abstract syntax tree. For each node, it creates backreferences repeatedly based on keys stored in the document data:

// Vulnerable implementation of GatherFootnotesListener
foreach ($document->iterator(NodeIterator::FLAG_BLOCKS_ONLY) as $node) {
    if (! $node instanceof Footnote) {
        continue;
    }
    // User-controlled destination label is turned into a configuration lookup key
    $key = '#' . $this->config->get('footnote/footnote_id_prefix') . $node->getReference()->getDestination();
    if ($document->data->has($key)) {
        // Generates backref nodes for each duplicate footnote block
        $this->createBackrefs($node, $document->data->get($key));
    }
}

The corresponding patch addresses this by performing a tracking pass to deduplicate defined footnote labels. The duplicate nodes are cataloged and removed from the syntax tree prior to the generation of backreferences. This reduces the processing complexity from $O(N^2)$ down to a safe linear $O(N)$ execution path.

// Patched implementation of GatherFootnotesListener
$definitions = [];
$discarded   = [];
 
foreach ($document->iterator(NodeIterator::FLAG_BLOCKS_ONLY) as $node) {
    if (! $node instanceof Footnote) {
        continue;
    }
    $label = $node->getReference()->getLabel();
    if (isset($definitions[$label])) {
        // Identify redundant duplicate blocks for removal
        $discarded[] = $node;
        continue;
    }
    $definitions[$label] = $node;
}
 
// Process only unique footnote definitions
foreach ($definitions as $node) {
    $key = '#' . $this->config->get('footnote/footnote_id_prefix') . $node->getReference()->getDestination();
    if (isset($backrefs[$key])) {
        $this->createBackrefs($node, $backrefs[$key]);
    }
}
 
// Detach the duplicate blocks to prevent downstream structural issues
foreach ($discarded as $duplicate) {
    $duplicate->detach();
}

Additionally, the dot-notation path traversal issue in NumberFootnotesListener is resolved. Instead of writing references dynamically using $document->data->append($destination, $reference), the library now aggregates backreferences in a native PHP associative array ($backrefs), which treats delimiters like dot and slash as standard characters. The aggregate array is subsequently stored under a single, secure nested dictionary path.

// Patched reference storage mechanism in NumberFootnotesListener
$backrefs = [];
foreach ($document->iterator() as $node) {
    // ... processes nodes ...
    // Safe insertion into a native PHP associative array instead of dot-notation storage
    $backrefs[$existingReference->getDestination()][] = $newReference;
}
// Write safe structured container to configuration
$document->data->set('footnote/backrefs', $backrefs);

Exploitation of the algorithmic complexity vulnerability requires only an unauthenticated HTTP request containing a crafted Markdown body. The attacker does not need special privileges or a specific session state. The target endpoint must parse user-supplied input using the league/commonmark parser with the FootnoteExtension enabled.

To construct an algorithmic complexity exploit payload, an attacker defines a highly repetitive list of footnote references matched with a corresponding block of duplicate footnote definitions. Because the parser attempts to map each reference to every duplicate definition, the payload size scales linearly while execution complexity scales quadratically.

This is a reference[^a] and another[^a] and another[^a] (repeated M times)
 
[^a]: Definition 1
[^a]: Definition 2
[^a]: Definition 3 (repeated N times)

For example, setting $M = 1000$ and $N = 1000$ results in a payload size of approximately 10 kilobytes. Processing this payload forces the parser to allocate more than 440 megabytes of memory and consume over 3 seconds of CPU execution. This exceeds typical default web server limitations, such as the PHP memory_limit of 128MB, triggering an immediate out-of-memory crash of the worker process.

Alternatively, path delimiter injection is triggered by utilizing footnote labels with nested periods. When parsing the document, the internal data manager interprets the dot notation as an array traversal instruction. If the target structure has a different format than expected (such as a string instead of an array), PHP throws a fatal runtime error and halts execution.

[^a] and [^a.b]
 
[^a]: base note
[^a.b]: nested path note

The impact of this vulnerability is a high-severity Denial of Service (DoS) affecting the availability of the application server. When a web server processes the malicious Markdown payload, the target PHP process consumes 100% CPU capacity and runs out of allocatable memory. This leads to the termination of the active PHP-FPM worker or Apache child process.

If multiple requests are submitted concurrently, an attacker can easily exhaust the entire pool of available web worker processes. This leaves the server unable to respond to legitimate HTTP traffic, resulting in a persistent offline state for the web application. Because the exploit payload is exceptionally small (approximately 10 KB), standard network-level mitigations such as maximum request size limits are ineffective.

Additionally, the path-delimiter injection flaw allows attackers to reliably crash any PHP script that parses footnote references. Because this error results in a fatal runtime exception, it bypasses standard application-level try-catch handling blocks, preventing graceful degradation or error reporting.

There is no known risk of remote code execution or data exposure associated with this vulnerability. The weakness is categorized strictly under CWE-407 (Inefficient Algorithmic Complexity) and CWE-400 (Uncontrolled Resource Consumption).

The absolute remediation for this vulnerability is to upgrade the league/commonmark library to version 2.9.0 or higher. This release contains the formal patch that deduplicates footnote definitions and replaces the insecure dot-notation storage mechanism.

For environments where an immediate package upgrade is not feasible, the following workarounds can be implemented:

First, disable the FootnoteExtension from the Markdown configuration environment. If the extension is not registered, the parser treats footnote syntax as standard plaintext, completely neutralizing the attack vector.

// Insecure Configuration
$environment->addExtension(new FootnoteExtension());
 
// Mitigated Configuration (Remove the above line entirely)

Second, implement application-level pre-parsing filters. You can use regular expressions to detect duplicate footnote labels or labels containing period or slash characters prior to invoking the league/commonmark compiler. If any invalid or duplicate footnote pattern is detected, the application should reject the input before execution reaches the vulnerable parsing engine.