CVE-2026-119197: Quadratic Algorithmic Complexity Denial of Service in pyasn1 REAL Mantissa Decoder

CVE-2026-119197 (tracked also as GHSA-mm57-4v3p-rchx) is an inefficient algorithmic complexity vulnerability (CWE-407) affecting pyasn1, the foundational Abstract Syntax Notation One (ASN.1) library for Python. The library provides core serialization and deserialization routines for Basic Encoding Rules (BER), Canonical Encoding Rules (CER), and Distinguished Encoding Rules (DER). Because pyasn1 serves as an upstream dependency for numerous Python networking, cryptographic, authentication, and directory service implementations (including LDAP, SNMP, and X.509 certificate parsers), any parsing bottleneck within its core decoders exposes a wide range of network-facing services.

The vulnerability is located in the RealPayloadDecoder.valueDecoder method within pyasn1/codec/ber/decoder.py. When deserializing a binary-encoded ASN.1 REAL data type, the parser extracts the unsigned integer mantissa from the incoming byte stream using an iterative while loop. On each iteration, the loop shifts an arbitrary-precision integer by 8 bits, performs a bitwise OR with the leading byte, and slices the remaining byte buffer using chunk = chunk[1:].

In Python, bytes objects are immutable, meaning every slice operation allocates a new memory buffer and copies the remaining $N - i$ bytes. Combined with the linear cost of shifting a progressively growing arbitrary-precision integer, this loop operates in quadratic $O(N^2)$ time relative to the byte length of the mantissa. An unauthenticated remote attacker who submits a crafted ASN.1 payload containing a multi-kilobyte binary REAL mantissa can force the Python interpreter into prolonged CPU saturation, blocking event loops or worker processes and resulting in an application-level Denial of Service (DoS).

According to the ITU-T X.690 standard for ASN.1 encoding rules, a REAL value (universal tag 0x09) can be encoded in binary, decimal, or special value formats. Binary encoding is selected when bit 8 (the most significant bit, 0x80) of the first content octet is set to 1. In this mode, the first content octet defines the sign bit ($S$ at bit 7), the logarithm base ($B$ at bits 6–5, representing base 2, 8, or 16), the scaling factor ($F$ at bits 4–3), and the exponent length format (bits 2–1). The octets immediately following the header specify the signed integer exponent ($e$), while the remainder of the payload (chunk) represents the unsigned binary integer mantissa ($p$). The decoded numerical value is evaluated as $(-1)^S \times p \times 2^F \times B^e$.

In pyasn1 versions prior to 0.6.5, after stripping the format octet and decoding the exponent octets, RealPayloadDecoder.valueDecoder converted the remaining chunk buffer into the integer mantissa p. Instead of utilizing bulk memory conversion primitives, the implementation relied on a manual byte-by-byte accumulator loop in pure Python. This design pattern violates expected linear $O(N)$ stream parsing guarantees when confronted with large input buffers.

Two distinct mechanics inside the Python runtime compound to create the quadratic complexity penalty for a mantissa of length $N$ bytes:

1. Immutable Byte-String Slicing Overhead: Executing chunk = chunk[1:] on an immutable bytes object requires CPython to allocate a new PyBytesObject of size $N - 1$ and execute a memcpy of the trailing bytes. Across $N$ iterations, the total number of bytes copied is $\sum_{i=1}^{N} (N - i) = \frac{N(N - 1)}{2}$, which scales quadratically as $O(N^2)$.
2. Arbitrary-Precision Integer Reallocation: Python's int type (PyLongObject) uses an array of 30-bit digits to represent arbitrary-precision integers. Executing p <<= 8 on an integer that grows by one byte every iteration requires allocating a new PyLongObject and shifting the entire array of existing digits across memory. As p scales from 1 byte to $N$ bytes, each bit-shift operation takes $O(i)$ time, yielding a second independent $O(N^2)$ CPU bottleneck.

> [!IMPORTANT] > This vulnerability affects both schema-driven and schemaless decoding paths. Even if an application's expected ASN.1 schema does not explicitly use univ.Real(), calling decoder.decode(data) without a rigid schema (asn1Spec=None) or parsing structures containing untagged open types (ANY) allows the decoder to dynamically dispatch tag 0x09 payloads directly to RealPayloadDecoder.

The vulnerable logic was located in pyasn1/codec/ber/decoder.py inside the RealPayloadDecoder.valueDecoder method. Because the Canonical Encoding Rules (pyasn1.codec.cer.decoder) and Distinguished Encoding Rules (pyasn1.codec.der.decoder) inherit RealPayloadDecoder directly from the BER decoder module, this single code path governed binary REAL deserialization across all three codec formats.

Vulnerable Implementation (Prior to v0.6.5)

# File: pyasn1/codec/ber/decoder.py
            elif b == 2:  # encbase = 16
                e *= 4
            p = 0
 
            # VULNERABLE: Iterates N times for an N-byte mantissa.
            # Each iteration reallocates 'p' (bignum shift) and copies
            # all remaining bytes in 'chunk' via slice allocation.
            while chunk:  # value
                p <<= 8
                p |= chunk[0]
                chunk = chunk[1:]
 
            if fo & 0x40:  # sign bit
                p = -p

Patched Implementation (v0.6.5)

In commit ce3ec3390784780a530047e0e77be5ff457636a4, the maintainers replaced the five-line iterative accumulator with a single call to Python's built-in int.from_bytes() method:

# File: pyasn1/codec/ber/decoder.py
            elif b == 2:  # encbase = 16
                e *= 4
            
            # FIXED: Delegates conversion to CPython's native C implementation
            # (_PyLong_FromByteArray), executing in a single pass without slicing.
            p = int.from_bytes(bytes(chunk), 'big')
 
            if fo & 0x40:  # sign bit
                p = -p

Assessment of Fix Completeness

The remediation is complete with respect to mantissa deserialization. By invoking int.from_bytes(bytes(chunk), 'big'), CPython delegates the byte-to-integer conversion to the internal C function _PyLong_FromByteArray. This function calculates the exact number of 30-bit limb digits required for the target PyLongObject, performs a single memory allocation, and populates the integer digits in one linear $O(N)$ pass over the input buffer.

While int.from_bytes completely eliminates the quadratic slicing and shifting bottleneck in RealPayloadDecoder, downstream applications should be aware that downstream arithmetic on the resulting univ.Real object (such as converting a massive mantissa and exponent into a native floating-point value or string representation) could still incur high computational costs if overall ASN.1 message sizes are not bounded at the transport layer. Furthermore, this commit was released alongside fixes for three other quadratic complexity flaws in pyasn1 0.6.5 (GHSA-2qm8-x737-gmw5, GHSA-9m75-vc3g-4x39, and GHSA-fm9c-5rcf-2q5p), addressing similar concatenation and reassembly loops in BIT STRING, OCTET STRING, and long tag ID parsers.

Exploiting CVE-2026-119197 requires no authentication or specialized environmental conditions beyond the ability to deliver an ASN.1-encoded byte stream to a target parser. The attacker constructs a syntactically valid BER, CER, or DER frame using universal tag 0x09 (REAL), sets the binary encoding flag in the first content octet (0x80), specifies a minimal 1-byte exponent (0x00), and fills the remainder of the payload with an arbitrary sequence of mantissa bytes.

Frame Construction Breakdown

A minimal proof-of-concept structure mirrors the regression tests added in commit ce3ec3390784780a530047e0e77be5ff457636a4 across tests/codec/ber/test_decoder.py, tests/codec/cer/test_decoder.py, and tests/codec/der/test_decoder.py:

1. Identifier Octet (0x09): Specifies Universal class, primitive encoding, tag number 9 (REAL).
2. Length Octets: Encodes the total length of the content using long-form length encoding (e.g., 0x83 0x04 0x00 0x02 to indicate a 262,146-byte payload).
3. First Content Octet (0x80): Bit 8 is 1 (binary encoding), Bit 7 is 0 (positive sign), Bits 6–5 are 00 (base 2), Bits 4–3 are 00 (scale factor 0), and Bits 2–1 are 00 (1-octet exponent).
4. Exponent Octet (0x00): Sets the exponent $e = 0$.
5. Mantissa Octets (chunk): $N$ bytes of arbitrary non-zero payload (e.g., b'\x80' + b'\x01' * (N - 1)).

from pyasn1.codec.ber import decoder
from pyasn1.type import univ
 
# Construct a 256 KB binary REAL mantissa
mantissa_len = 262144
mantissa = b'\x80' + (b'\x01' * (mantissa_len - 1))
content = b'\x80\x00' + mantissa
 
# Encode ASN.1 tag (0x09) and long-form length (0x83 + 3-byte big-endian length)
length_bytes = len(content).to_bytes(3, 'big')
substrate = b'\x09\x83' + length_bytes + content
 
# Trigger decoding (works with asn1Spec=None or asn1Spec=univ.Real())
value, rest = decoder.decode(substrate)

When mantissa_len is small (such as 512 bytes in the unit test suite), decoding completes rapidly. However, as mantissa_len scales to 256 KB ($262,144$ bytes), the vulnerable while chunk: loop performs approximately $\frac{(262,144)^2}{2} \approx 34.3 \times 10^9$ bytes of memory copying alongside 262,144 arbitrary-precision integer allocations. On a standard server CPU core, a single 256 KB network packet blocks the Python interpreter thread for several seconds, while a 1 MB payload can stall execution for minutes.

CVE-2026-119197 is rated with a CVSS v3.1 base score of 7.5 (High) via the vector CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H. The vulnerability exclusively impacts system availability; it does not permit unauthorized memory read access (Confidentiality: None) or arbitrary state modification (Integrity: None).

Because Python's Global Interpreter Lock (GIL) serializes bytecode execution across threads within a single process, an algorithmic complexity attack executing inside a Python while loop holds the GIL during each bytecode instruction and C-level slice allocation. In multi-threaded Python services or asynchronous event loops (such as asyncio or Twisted), a single malicious ASN.1 payload prevents all other concurrent tasks within the same worker process from making progress.

Services most at risk include:

• Authentication and Directory Gateways: Python-based LDAP proxies, RADIUS/EAP handlers, and Kerberos utilities that parse ASN.1 BER/DER packets prior to authenticating the client.
• Network Monitoring and Management Daemons: SNMP managers and agents receiving unauthenticated traps or polling requests.
• Public Key Infrastructure (PKI) and Cryptographic Services: Online Certificate Status Protocol (OCSP) responders, Certificate Authority (CA) enrollment endpoints, and S/MIME or CMS signature verification pipelines that decode untrusted X.509 certificates or PKCS structures without strict pre-decoding size limits.

As of current threat intelligence measurements, the Exploit Prediction Scoring System (EPSS) assigns CVE-2026-119197 a probability score of 0.00425 (36.83rd percentile), and the vulnerability is not listed in the CISA Known Exploited Vulnerabilities (KEV) catalog.

The primary remediation is to upgrade pyasn1 to version 0.6.5 or later, which replaces the quadratic mantissa decoding loop with linear-time native byte conversion and resolves three additional quadratic complexity flaws across the BER, CER, and DER codecs.

Upgrading pyasn1

Update the package in all affected Python environments and container images using pip:

pip install --upgrade "pyasn1>=0.6.5"

Verify the installed version and ensure that transitive dependency locks (such as poetry.lock, Pipfile.lock, or requirements.txt files used by packages like pyasn1-modules, pysnmp, or ldap3) are regenerated to pull at least 0.6.5.

Defense-in-Depth Mitigations

In environments where immediate patching is not feasible, or as an architectural safeguard against resource exhaustion in ASN.1 parsers, implement the following controls:

1. Enforce Strict Payload Size Limits: Validate and cap the maximum byte length of incoming ASN.1 frames at the network socket or HTTP proxy layer before invoking pyasn1.codec.ber.decoder.decode(). For most authentication and certificate protocols, legitimate payloads rarely exceed 16 KB to 64 KB.
2. Provide Explicit ASN.1 Schemas: Always pass a strict asn1Spec structure to decoder.decode(substrate, asn1Spec=ExpectedSchema()) rather than relying on schemaless decoding (asn1Spec=None). If the explicit schema does not include univ.Real fields or open ANY types, the decoder will reject unexpected 0x09 tags immediately before entering RealPayloadDecoder.valueDecoder.
3. Process Isolation and Timeouts: Execute untrusted ASN.1 parsing inside dedicated worker processes governed by strict CPU time limits (RLIMIT_CPU) and request timeouts so that a stalled worker can be terminated and recycled without starving the primary application server.