CVE-2026-59937: CPU Exhaustion via Quadratic-Time Cross-Reference Recovery Loop in pypdf

The pypdf library is a pure-Python library designed for splitting, merging, cropping, and transforming PDF files. It is heavily used in automated backend document processing pipelines, web applications supporting user-uploaded files, and data extraction engines.\n\nThis vulnerability exposes a denial-of-service vector through the parsing of cross-reference (xref) tables. When standard parsing fails due to invalid formatting or corrupted entries, the library triggers an automated recovery routine.\n\nThe recovery routine employs an inefficient algorithm that scales quadratically with respect to the number of invalid entries and the file buffer size. By executing multiple regex searches across the entire remaining stream buffer, a remote unauthenticated attacker can exhaust CPU resources on the hosting application.

The core flaw lies within the _read_standard_xref_table method inside pypdf/_reader.py. Standard PDF specifications state that the cross-reference table matches object numbers to their physical byte offsets, permitting rapid lookup.\n\nIn corrupted files, the entry fields may contain unexpected or corrupt formatting characters. To prevent immediate processing failures, the parser executes a recovery loop that sequentially scans the file stream to extract the actual byte coordinates of the target object.\n\nDuring each loop iteration, the parser calls re.search over the entire remaining file buffer buf of size $M$. If the table specifies $N$ corrupt entries, the system performs $N$ regex scans over the buffer of size $M$. This results in a time complexity of $O(N \times M)$, causing extreme thread blockages and high CPU utilization.

The vulnerable logic in pypdf/_reader.py processes entries inside a persistent parsing loop. When a corrupt entry is identified, it repeatedly reads the remaining stream and runs a regex match to find the actual PDF object location.\n\npython\n# Vulnerable recovery fallback in pypdf/_reader.py\nbuf = stream.read(-1)\nstream.seek(p)\n\nf = re.search(rf\"{num}\\s+(\\d+)\\s+obj\".encode(), buf)\nif f is None:\n # Log missing object\nelse:\n generation = int(f.group(1))\n offset = f.start()\n\n\nThe patched implementation solves this structural problem by loading an in-memory dictionary-based cache exactly once when the first recovery is required. Lookups thereafter operate in constant $O(1)$ complexity.\n\npython\n# Patched logic utilizing a single-pass recovery cache\nif recovery_cache is None:\n recovery_cache = self._load_recovery_cache(buf)\n\nif num not in recovery_cache:\n # Log missing object\nelse:\n generation, offset = recovery_cache[num]\n\n\nThis change reduces the programmatic complexity of the recovery sequence from quadratic $O(N \times M)$ down to linear $O(N + M)$ execution complexity.

An attacker can exploit this behavior by sending a minimized PDF with a custom xref table. The table declares a high number of entries (e.g., 20,000) followed by sequential lines of corrupted ASCII characters like xxxxxxxxxxxxxxxx 0\\r\\n.\n\nBecause the parser tries to gracefully recover each declared entry, it executes the regex engine repeatedly. This causes the CPU core handling the parse job to spike to 100% capacity for an extended duration.\n\nBelow is a conceptual data flow diagram of the vulnerability execution:\n\nmermaid\ngraph LR\n A[\"Malformed PDF Payload\"] --> B[\"pypdf Reader Parse\"]\n B --> C[\"Read Standard XRef Table\"]\n C --> D{\"Entry Corrupt?\"}\n D -- \"Yes (N entries)\" --> E[\"Sequential Regex Scan on Buffer (M bytes)\"]\n E --> F[\"Repeat N times: O(N * M) Complexity\"]\n F --> G[\"CPU Exhaustion / Thread Freeze\"]\n D -- \"No\" --> H[\"Normal Processing\"]\n

The primary security consequence of CVE-2026-59937 is local or remote denial of service. For architectures deploying pypdf on synchronous web application workers, processing a single payload can completely lock a worker process, preventing it from handling legitimate web traffic.\n\nIf multiple malicious payloads are processed concurrently, the entire system can quickly exhaust its available CPU capacity, resulting in system-wide degradation or outages.\n\nWhile this vulnerability does not allow remote code execution or data extraction, its low attack complexity and high impact on system availability yield a CVSS score of 7.5. Applications that permit anonymous file uploads are especially vulnerable to this denial of service attack.

The definitive fix is upgrading to pypdf version 6.14.0 or above. This version implements the single-pass cache system which neutralizes the algorithmic bottleneck.\n\nIf upgrading is not immediately possible, security teams should implement defensive file-processing controls. Restricting the maximum size of uploaded PDF files (e.g., keeping $M$ small) limits the impact of the sequential scans.\n\nAdditionally, wrapping PDF parsing calls in isolated subprocesses with explicit execution timeouts will terminate runaway parsing threads before they cause broad infrastructure issues.