CVE-2026-112894: 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.