simple_asn1 `decode_base127` O(N²) CPU DoS (Quadratic Complexity)

[tynus3]

Hi,

I found a quadratic-time parsing path in simple_asn1 that allows an attacker to cause CPU exhaustion with a small crafted input.

Summary

decode_base127 (src/lib.rs:612-628) accumulates base-128 bytes into a BigUint:

// src/lib.rs:623
res = (res << 7) + BigUint::from(nextbyte & 0x7f);

BigUint operations cost O(size_of_res) — they get slower as the accumulator grows. After reading N continuation bytes (each with bit 7 set), res holds an N×7-bit integer and each subsequent << 7 and + costs O(N). The total work across all N iterations is O(N²).

This function is called from two places:

1. Long-form tag parsing (decode_tag at src/lib.rs:604) — triggered by any tag byte ending in 0b1_1111 (e.g. 0x1F, 0x9F, 0xBF) followed by continuation bytes with the high bit set.
2. OID arc parsing — each OID sub-identifier is decoded with the same BigUint accumulation loop.

A payload with K continuation bytes of 0x81 followed by a final 0x01 causes O(K²) CPU work in from_der. With K = 262,144 bytes (~256 KB), the parser takes around 1 second — compared to 750 nanoseconds for a DER oracle parsing the same size, a >1,000,000× amplification.

OID vector (single huge sub-identifier)

Input size	Median (ms)	Doubling ratio	Classification
16 KB	2.5	—
32 KB	9.8	3.92×	quadratic
64 KB	39.1	3.99×	quadratic
128 KB	156.3	4.00×	quadratic
256 KB	624.9	4.00×	quadratic

Long-form tag vector

Input size	Median (ms)	Doubling ratio	Classification
16 KB	2.4	—
32 KB	9.6	4.00×	quadratic
64 KB	38.4	4.00×	quadratic
128 KB	153.5	4.00×	quadratic
256 KB	614.1	4.00×	quadratic

Both vectors show the same clean 4.0× doubling ratio — textbook O(N²) behavior.

Root cause

// src/lib.rs:612-628
fn decode_base127(i: &[u8], index: &mut usize) -> Result<BigUint, ASN1DecodeErr> {
    let mut res = BigUint::zero();
    loop {
        // ...
        res = (res << 7) + BigUint::from(nextbyte & 0x7f);
        //     ^^^^^^^^ each shift costs O(bit width of res)
        //              bit width grows by 7 per iteration
        //              total cost: 7 + 14 + 21 + ... + 7N = O(N²)
        if (nextbyte & 0x80) == 0 {
            return Ok(res);
        }
    }
}

---

Thanks for maintaining simple_asn1. Please let me know if I need to provide more information.