league/commonmark: Quadratic-time denial of service when parsing crafted Markdown

QFinch assessment

Affected versions of `league/commonmark` can have quadratic time complexity when parsing specially crafted Markdown lines. In practical terms, doubling the length of an affected line can make the parser perform roughly four times as much work. The parser identifies locations using character positions, but regular-expression matches report byte positions. These positions differ when a UTF-8 character uses more than one byte. Several parsing paths repeatedly rescan growing portions of the line to translate between the two positions. The Autolink extension can also copy and validate the remaining line at every URL-like prefix.

Potential impact

Affected versions of league/commonmark can have quadratic time complexity when parsing specially crafted Markdown lines. In practical terms, doubling the length of an affected line can make the parser perform roughly four times as much work. The parser identifies locations using character positions, but regular-expression matches report byte positions. These positions differ when a UTF-8 character uses more than one byte. Several parsing paths repeatedly rescan growing portions of the line to translate between the two positions. The Autolink extension can also copy and validate the remaining line at every URL-like prefix. In current 2.x releases, a single non-ASCII character anywhere on a line can place that whole line on the slower multibyte path. An attacker can combine it with a long run of leading whitespace or repeated Markdown punctuation, causing increasingly large rescans. When the Autolink extension is enabled, repeated URL-like prefixes provide another trigger, even on ASCII-only lines. Each trigger fits within one long line, so complex Markdown structure is unnecessary. An attacker who can submit Markdown for conversion can use a comparatively small request to consume disproportionate CPU time and allocation activity. Repeated or concurrent requests can occupy all available PHP workers and prevent legitimate requests from completing. The core paths affect CommonMarkConverter, GithubFlavoredMarkdownConverter, and custom environments. The autolink-specific path affects applications using AutolinkExtension or GithubFlavoredMarkdownExtension. Applications that process only trusted Markdown are not remotely exploitable. The impact is limited to availability: it does not disclose data, change rendered output, or bypass rendering restrictions. Settings such as htmlinput and allowunsafelinks do not mitigate the issue because the expensive work occurs before rendering.