Algorithmic Complexity Denial of Service in league/commonmark

The league/commonmark library, specifically versions 2.0.0 through 2.8.x, contains an algorithmic complexity vulnerability (CVE-2025-27144) within its UniqueSlugNormalizer component. This component is designed to ensure document-unique heading anchors by appending numeric suffixes to duplicate slugs. However, the implementation resets the search for an unused suffix to index '1' upon every collision. Consequently, processing K colliding slugs results in O(K²) time complexity.

An attacker can exploit this by submitting a Markdown document containing a large number of headings that normalize to the same slug (e.g., identical text, empty headings, or punctuation-only strings). When parsed by applications utilizing extensions such as HeadingPermalinkExtension, FootnoteExtension, or TableOfContentsExtension with the default PER_DOCUMENT uniqueness setting, the processor consumes excessive CPU cycles, leading to a denial-of-service condition. Because this behavior occurs during the standard parsing process and requires no authentication, it poses a significant availability risk for web applications that render user-provided Markdown.

Impact

Successful exploitation results in CPU exhaustion, rendering the affected application unresponsive or significantly degraded. The vulnerability affects any service processing untrusted Markdown input using vulnerable versions of league/commonmark. The scale of the impact depends on the configured document size limits; however, even moderately sized inputs can trigger multi-second stalls on a single thread.

Recommendation

Prioritize upgrading league/commonmark to version 2.9.0 or later, which resolves the quadratic behavior. If an immediate upgrade is not feasible, apply one of the following mitigations:

• Set the slug_normalizer/unique configuration to false (or UniqueSlugNormalizerInterface::DISABLED) to stop the de-duplication scan.
• Disable the HeadingPermalinkExtension, TableOfContentsExtension, and FootnoteExtension when processing untrusted input.
• Implement strict upstream constraints on document size or the number of headings allowed in a single input to prevent reaching the threshold where O(K²) complexity becomes destructive.