GHSA-MW73-8637-G65G
pymdownx.keys: exponential ReDoS in RE_EARLY_KBD quoted-key branches
Texto original en inglés · Ver en español
CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H
Fuente: GitHub
Ciclo de vida de la vulnerabilidad
| Fecha | Fase | Evento | Detalle |
|---|---|---|---|
| Remediación | Parche 11.0.2 | pymdown-extensions · -77 d desde divulgación | |
| Divulgación | Publicada | GHSA-MW73-8637-G65G divulgada · CVSS 7.5 (GitHub) | |
| Monitoreo | Detectada | Ingresó al índice | |
| Monitoreo | Verificada | Última verificación contra las fuentes |
Summary
`pymdownx/keys.py` builds `RE_EARLY_KBD` with an ambiguous alternation in both of its quoted-key
branches. A run of backslashes inside a quoted key has Fibonacci-many valid decompositions, so when
the surrounding match cannot complete, the regex engine explores all of them. A 42-byte document
takes ~36 seconds of single-core CPU to render; 44 bytes takes ~91 seconds. Growth is ~2.7× per
two added bytes.
This is the same class of bug as the four patterns fixed in 11.0.1 by
`c68498598d7b13011bb4571350b6e3612a4ce44b` ("Fix regex pattern inefficiencies: BetterEm, Tilde, Caret,
and MagicLink"). That commit did not touch `keys.py`, which carries the same idiom in a different form,
so 11.0.1 is still affected.
Affected component
`pymdownx/keys.py`, lines 101–102, inside `RE_EARLY_KBD` (the construct appears twice — once in the lazy
repetition, once in the trailing mandatory alternative):
(?:(?:[\w\-]+|"(?:\\.|[^"])+"|\'(?:\\.|[^\'])+\')\+)*?Both quoted alternatives are affected — `"(?:\\.|[^"])+"` and `'(?:\\.|[^'])+'`.
This line is unchanged since `6bc3eb92a` (2017-04-16, "Add Keys extension"), so every release shipping
the Keys extension is affected, including the current 11.0.1.
Reachability: `RE_EARLY_KBD` is registered unconditionally in `KeysExtension.extendMarkdown()`
(`keys.py:233`) whenever `pymdownx.keys` is enabled. No configuration option gates it. Any deployment
that renders untrusted Markdown with the Keys extension enabled is reachable. You will have a much
better sense than I do of how common that is in practice.
Details
The inner alternation is ambiguous because the two branches can consume the same input in different
ways:
- `\\.` matches a backslash followed by any character — two characters
- `[^"]` matches any character other than a double quote — including a backslash — one character
So a run of N backslashes can be tiled as `\\.` pairs, as single `[^"]` steps, or any mixture. The
number of tilings of a length-N run using pieces of size 1 and 2 is Fibonacci(N+1), i.e. ~1.62^N. As
long as the match ultimately fails, the engine must try all of them before giving up.
The payload forces exactly that: `++"` enters the quoted branch, the backslash run creates the
ambiguity, and a trailing character that is not a quote guarantees the closing `"` is never found.
For contrast, `pymdownx/blocks/html.py:19` already writes this construct correctly, by excluding the
backslash from the negated class so the branches are disjoint:
(?:"(?:\\(?:.)|[^\\"\r\n\f]+)*?"|...)
# ^^^^ backslash excluded — only \\(?:.) can consume one`keys.py` is the outlier rather than the rule in this codebase.
For completeness, `betterem.py:37` — `((?:[^\*]|(?<!\*{2})\*)+?)` — is not affected and needs no
change: its second branch matches exactly one star, so a star run has only one decomposition. I checked
this empirically rather than just by eye (mean growth ratio 0.85, flat). Disjoint or fixed-length branches
are safe regardless of how deep the nesting looks.
I also re-checked the 11.0.1 fix itself while I was in here, in case it's useful to you: `betterem`,
`caret` and `tilde` each render a 4,000-character adversarial run (`*a` + `*`×4000 + `b` and equivalents)
in about 50 ms. The fix is holding — `keys.py` was simply never in its scope.
Proof of concept
import markdown, time
payload = '++"' + '\\' * 38 + 'x' # 42 bytes
t = time.monotonic()
markdown.markdown(payload, extensions=['pymdownx.keys'])
print(f"{len(payload)} bytes -> {time.monotonic() - t:.1f}s")Measured on pymdown-extensions 11.0.1 (PyPI) with Markdown 3.10.3, CPython 3.14, single core:
| payload | double-quoted | single-quoted |
| --- | --- | --- |
| 34 B | 0.69 s | — |
| 38 B | 4.91 s | — |
| 42 B | 35.8 s | 39.1 s |
| 44 B | ~91 s | — |
Controls, to show the timings are attributable to this pattern and not to input length or environment:
| control | result |
| --- | --- |
| same 42-byte payload, `pymdownx.keys` disabled | 0.0005 s |
| benign 42-byte input (`++"` + `a`×38 + `x`), keys enabled | 0.0004 s |
| `++"Custom Key"++` renders `<kbd>` before timing | yes — extension verified functional |
| harness calibration: pre-fix `betterem` pattern | grows 2.62× per step (expected) |
| harness calibration: post-fix `betterem` pattern | flat, 0.82× (expected) |
A self-contained script with the calibration controls built in is attached
(`poc_pymdown_keys_redos.py`); it runs the regex-only case with no dependencies and the end-to-end case
if `markdown` and `pymdown-extensions` are installed, and it aborts rather than reporting timings if the
extension is not actually rendering.
Impact
An unauthenticated attacker who can submit Markdown to a service that renders it with `pymdownx.keys`
enabled can consume unbounded CPU with a trivially small input. Because the growth is exponential, the
attacker chooses the cost: 42 bytes is ~36 seconds measured, and extrapolating the observed 2.7×-per-two-
bytes growth puts ~54 bytes in the hours range (extrapolated, not measured — I stopped at 44 B / ~91 s).
A small number of concurrent requests can therefore saturate every worker, so the practical result is
denial of service.
There is no data exposure and no integrity impact — this is purely resource exhaustion.
The precondition is that the Keys extension is enabled and the Markdown source is untrusted. Sites that
only render trusted, authored content are not meaningfully exposed.
Severity
I've proposed CVSS 3.1 7.5 High — `AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H` — on the basis that the
payload is trivial, needs no authentication or interaction, and the attacker controls the cost.
Two honest qualifications, since you're better placed to weigh them:
- CVSS has no clean way to express "requires an optional extension to be enabled". That precondition is
- I've aligned the proposal with how the sibling issue in 11.0.1 was treated. If you scored that one
Suggested fix
Make the branches disjoint by excluding the escape character from the negated class — exactly what
`blocks/html.py` already does:
-(?:(?:[\w\-]+|"(?:\\.|[^"])+"|\'(?:\\.|[^\'])+\')\+)*?
+(?:(?:[\w\-]+|"(?:\\.|[^\\"])+"|\'(?:\\.|[^\\\'])+\')\+)*?Both occurrences of each quoted branch need the change — line 101 (the lazy repetition) and line 102
(the trailing mandatory alternative), for both the double- and single-quoted alternatives, so four edits
in total.
I applied this to the full `RE_EARLY_KBD` and verified it against the installed 11.0.1:
- Removes the blowup. Mean growth ratio drops from 2.66× to 1.01× (flat). The 42-byte payload goes
- Output is byte-identical to stock on every case I tried: `++ctrl+alt+delete++`,
One behaviour change, which I'd rather flag than gloss over: the input `"trailing\"` — a lone backslash
immediately before the closing quote — currently matches and would not after the change. Under escape
semantics that string is unterminated, since the quote is escaped, so failing to match is arguably the
more correct reading and is consistent with `blocks/html.py`. But it is a change in behaviour and it's
your call, not mine. If you'd prefer to preserve the current behaviour exactly, adding `(?!\\)` to the
negated-class branch achieves that instead.
I have not opened a PR, to avoid creating a public artefact before you've had a chance to look. Happy to
send one privately against a fork or a security branch if that's easier for you.
Mitigation
If you feel you are at risk of this issue and cannot tolerate the risk, the Keys extension is optional and can be disabled.
References
- Sibling fix: `c68498598d7b13011bb4571350b6e3612a4ce44b` — BetterEm, Tilde, Caret, MagicLink (11.0.1)
- Correct handling of the same construct already in-tree: `pymdownx/blocks/html.py:19`
- Vulnerable line origin: `6bc3eb92a`, 2017-04-16
- CWE-1333: Inefficient Regular Expression Complexity
Incluye detalles técnicos publicados por el investigador. Úselos solo para validar y corregir sus propios sistemas.
Desglose de métricas
Rangos afectados
Estado del parche por paquete
| Paquete / producto | Estado | Corregida en | Desde divulgación | Última versión |
|---|---|---|---|---|
pypipymdown-extensions |
Corregida | 11.0.2 | -77 d | 13.1.0 no afectada |
11.0.2Arsenal público
Sin exploits, módulos ni PoC públicos conocidos a la fecha de verificación.
https://github.com/facelessuser/pymdown-extensions/security/advisories/GHSA-mw73-8637-g65gLas referencias externas se muestran para copiar: cve.llama.ec no lo redirige a otros sitios.
