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

============================================================================
ReDoS in XbmImagePlugin: 512-byte file stalls Image.open() for minutes
Location: src/PIL/XbmImagePlugin.py:58  in XbmImageFile._open()
Commit:   a707c6b21c313880d0771e54965d142dd42358b6
============================================================================

A crafted 512-byte file makes Pillow's Image.open() spend about six minutes of processor time on one core before it gives up with UnidentifiedImageError. Anyone who can hand bytes to an application that opens images with Pillow's default settings can trigger this, for example through an upload form, a thumbnailer, or a service that checks whether a blob is an image. A few such files sent at once can tie up a typical pool of worker processes.

The cause is the xbm_head regular expression in src/PIL/XbmImagePlugin.py:32-40, which XbmImageFile._open() (line 58) runs over the first 512 bytes of any stream whose prefix starts with #define. Several adjacent parts of the pattern can match the same characters. [ \t]+ overlaps with .* in the width and height lines and with [^_]* in the optional hotspot lines, and [\r\n]+ closing the hotspot group overlaps with the following [\000-\377]*. The header sets a run of k spaces after each #define and a run of k line terminators after _y_hot, then omits the [] after _bits. That forces Python's backtracking matcher to try every way of splitting those runs and rescan the remaining bytes each time. The cost grows roughly as k to the fifth power: k = 60 measured 375 s, while a well-formed XBM of the same size opens in about 40 ms. Because this happens before any format is identified, none of Pillow's size, pixel-count or decompression-bomb limits apply, and upload size limits do not help because the file is tiny. ImageFile.Parser.feed() repeats the cost on every chunk until the stream is identified. The only existing mitigation is passing a formats= allowlist that excludes "XBM".

The attached reproducer opens the same header with and without the trailing []. The valid version opens as XBM in 52 ms. The broken version takes 0.1 s, 0.75 s, 3.0 s and 8.6 s at k = 10, 15, 20 and 25, and the slow k = 60 case is not run. This is the same class of bug as CVE-2021-25292 in PdfParser, but in a different plugin and reachable from plain Image.open().

Details

XbmImageFile._open() identifies an XBM file by running the module-level regex xbm_head over the first 512 bytes of the stream. The pattern has several adjacent quantifier pairs that can consume the same characters, followed by a [\000-\377]*_bits\[] tail that rescans the rest of the buffer for every way of splitting them. A 512-byte input built to exercise all of them and then fail the final literal keeps Image.open() in xbm_head.match() for minutes before it raises UnidentifiedImageError.

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 in k ways. Factor k.

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