Pillow: Quadratic-time DoS in PDF save_all (PdfParser.next_object_id)

============================================================================
Quadratic-time DoS in PDF save_all (PdfParser.next_object_id)
Location: src/PIL/PdfParser.py:629  in next_object_id()
Commit:   a707c6b21c313880d0771e54965d142dd42358b6
============================================================================

Pillow's PDF writer takes time proportional to the square of the number of frames when it saves a multi-frame image as a multi-page PDF. Anyone who can get an application to convert their uploaded image this way can tie up a worker at full CPU for minutes with a small file. A 240 KB animated image takes about 70 seconds, a 720 KB one an estimated 10 minutes, and a 125-byte animated PNG that merely declares a large frame count triggers the same slowdown with no upper bound short of 2³¹ frames. Memory stays under 100 MB and the decompression-bomb limit never applies.

The cause is PdfParser.next_object_id() in src/PIL/PdfParser.py, which finds the next free id by computing max(self.xref_table.keys()). XrefTable.keys() rebuilds three sets over every id reserved so far on each call. PdfImagePlugin._save() calls it three times (four for palette images with transparency) per frame, for n_frames frames, before any page is written. That makes the id-reservation loop alone O(N²). Because n_frames is taken from the file before any frame is seeked, APNG's acTL count drives the loop even when the frames don't exist. In that case the save raises OSError only after the full delay.

The precondition is that the application calls im.save(..., "PDF", save_all=True) on the attacker's file; Image.open() and load() alone do not reach this code. The attached reproducer shows 4× the frames costing about 11× the CPU for a valid GIF and about 16× for a fixed 125-byte APNG. The behaviour was introduced in 6207b44ab1ff (2018-01-18) and first shipped in Pillow 5.1.0. A small patch that tracks the highest id in XrefTable makes the save linear.

Details

Saving a multi-frame image as a multi-page PDF (im.save(fp, "PDF", save_all=True)) costs CPU time proportional to the square of the frame count, independent of pixel content, because every object id the PDF writer reserves is found by rebuilding and scanning the set of all ids reserved so far.

A 1×1-pixel animated GIF made of N identical 15-byte frames (built by the reproducer) gives, on a 2-CPU container with the stock build at this commit (absolute timings vary by machine; the growth rate does not):

Each doubling of the input roughly quadruples the time. cProfile of the 8 000-frame save attributes 13.5 s of 17.6 s to 24 003 calls of PdfParser.next_object_id (8.9 s inside XrefTable.keys, 3.9 s inside max); encoding and writing the 8 000 pages is the remaining ~4 s and scales linearly.

The per-page id reservation loop runs before any page is written:

# src/PIL/PdfImagePlugin.py:247-259  (_save)
    for im in ims:
        im_number_of_pages = 1
        if save_all:
            im_number_of_pages = getattr(im, "n_frames", 1)
        …
        for i in range(im_number_of_pages):
            image_refs.append(existing_pdf.next_object_id(0))
            if im.mode == "P" and "transparency" in im.info:
                image_refs.append(existing_pdf.next_object_id(0))

            page_refs.append(existing_pdf.next_object_id(0))
            contents_refs.append(existing_pdf.next_object_id(0))

n_frames comes straight from the file (for GIF it is the number of image blocks; the GIF plugin counts them by walking block headers, which is cheap). The frames do not even have to exist: the loop runs on n_frames before any frame is seeked, and for APNG n_frames is the num_frames value declared in the acTL chunk, rejected only if it is 0 or above 0x80000000 (src/PIL/PngImagePlugin.py:716-720). A 125-byte APNG declaring 8 000 frames therefore costs the same ~10–13 s as the 120 KB GIF, and more without bound as the declared count grows. Each of the 3 (or 4, for P images with transparency) calls per frame lands here:

# src/PIL/PdfParser.py:626-634
    def next_object_id(self, offset: int | None = None) -> IndirectReference:
        try:
            # TODO: support reuse of deleted objects
            reference = IndirectReference(max(self.xref_table.keys()) + 1, 0)
        except ValueError:
            reference = IndirectReference(1, 0)
        if offset is not None:
            self.xref_table[reference.object_id] = (offset, 0)
        return reference

# src/PIL/PdfParser.py:175-178  (XrefTable)
    def keys(self) -> set[int]:
        return (
            set(self.existing_entries.keys()) - set(self.deleted_entries.keys())
        ) | set(self.new_entries.keys())

_save passes offset=0, so every reserved id is inserted into xref_table.new_entries. The k-th call therefore materialises three sets covering all k−1 previous ids, computes a difference and a union, and then max() scans the result — O(k) work to produce the integer k. Summed over 3N calls this is O(N²): for 48 000 frames, 144 002 calls over sets growing to 144 002 elements, on the order of 10¹⁰ set-element operations, all spent before _write_image is reached for the first frame. Nothing on this path consults MAX_IMAGE_PIXELS (the frames are 1×1) and nothing raises; for the GIF the save eventually completes and produces a valid PDF, and for the declared-only APNG it raises OSError only once the id loop has finished and the first missing frame is seeked.

This reservation scheme was introduced in 6207b44ab1ff ("issue #2959: support appending to existing PDFs", 2018-01-18) and first shipped in Pillow 5.1.0; before it, the writer numbered objects arithmetically.

For contrast, write_obj(ref, …) with an already-reserved ref (src/PIL/PdfParser.py:548-555) only does a dict store, which is why the page-writing phase that follows is linear; the super-linear cost is entirely in how the next free id is computed.

Impact

The precondition is that the application saves the attacker's image as PDF with save_all=True; Image.open() and load() alone do not reach this code. An application that converts uploaded images to PDF this way — the documented way to get one page per frame from animated GIF/APNG/WebP or multi-page TIFF input — can have a worker held at 100 % CPU for about 10 minutes by a 720 KB GIF, about 4½ minutes by a 480 KB one, with the cost continuing to grow quadratically with upload size. With APNG the file size does not matter at all: a 125-byte file declaring N frames in acTL drives the same quadratic loop, up to the 2³¹ cap. The attacker controls only the file bytes; no unusual dimensions, modes or options are needed, memory use stays under 100 MB so memory limits do not intervene, and the decompression-bomb guard is not applicable. The consequence is denial of service of the process performing the conversion. Single-image PDF saves, and save_all saves of images with tens or hundreds of frames, are unaffected in practice.

This is the same family as earlier accidentally-quadratic parsing issues fixed in Pillow (e.g. CVE-2021-28677, EPS readline), but on the PDF writer side, reached only through a save rather than on open, and driven by frame count rather than by line structure.

Reproducing

repro is a single Python script. Run it with the Python that has Pillow installed (./repro). It uses under 100 MB of RAM and writes no files.

Input. Two kinds of file are built in memory, each with 2 000 and 8 000 frames:

• gif(n): a valid animated GIF — a GIF89a header with a 1×1 logical screen and a 2-colour global palette, then `