`SetOfVec::decode_value` uses O(N²) insertion sort — quadratic DoS on crafted SET OF input

[tynus3]

Summary

der_sort() in der/src/asn1/set_of.rs is a hand-rolled insertion sort with no element count cap. It is called on every SetOfVec decode in DER mode. On a reverse-sorted input of N elements, insertion sort performs N(N−1)/2 comparisons and swaps — O(N²) total work.

A 246 KB crafted SET OF with 18,000 elements in reverse-sorted DER order causes a single SetOfVec::decode_value call to block for ~11 seconds on a modern machine. At N=9,000 (123 KB payload) it takes ~2.9 seconds, N=18,000 takes ~11s.

Root cause

// der/src/asn1/set_of.rs
fn der_sort<T: DerOrd>(slice: &mut [T]) -> Result<(), Error> {
    for i in 0..slice.len() {
        let mut j = i;
        while j > 0 {
            if slice[j - 1].der_cmp(&slice[j])? == Ordering::Greater {
                slice.swap(j - 1, j);
                j -= 1;
            } else {
                break;
            }
        }
    }
    Ok(())
}

This is insertion sort. For N elements in reverse order: element at index k requires k swaps, total = N(N−1)/2 = O(N²).

Verified timing (der 0.7.10, x509-cert 0.2.5, --release)

Payload: crafted RelativeDistinguishedName (SET OF AttributeTypeAndValue) with N ATVs in reverse-sorted DER order.

N	Payload	Worst-case (ms)	Best-case (ms)	Ratio
300	4.2 KB	3.2	0.08	40×
1,000	14 KB	35	0.24	146×
3,000	42 KB	316	0.73	433×
9,000	123 KB	2,818	2.2	1,281×
18,000	246 KB	11,414	4.3	2,654×

Consecutive worst-case ratios per 3×-N step are consistently ~9×, confirming O(N²). Best-case (already sorted) is O(N) as expected for insertion sort.

Note: each comparison is allocation-free — DerOrd uses the blanket impl in ord.rs which compares Header structs then delegates to the field-by-field ValueOrd derive. The O(N²) cost is pure computation (function calls + byte comparisons + struct swaps).

Attack surface

Any SetOfVec decoded from untrusted DER is affected. The two widest-deployed paths:

• x509-cert — RelativeDistinguishedName = SetOfVec: triggered by any call to Certificate::from_der() on an attacker-supplied certificate (TLS, S/MIME, code signing, …).
• cms — DigestAlgorithmIdentifiers, CertificateSet, SignerInfos are all independent SetOfVec fields in SignedData; a single crafted CMS blob stacks the sort cost across all three.

This should fix

Replace the insertion sort with slice::sort_unstable_by (introsort, O(N log N)):

fn der_sort<T: DerOrd>(slice: &mut [T]) -> Result<(), Error> {
    let mut first_err: Option<Error> = None;
    slice.sort_unstable_by(|a, b| {
        a.der_cmp(b).unwrap_or_else(|e| {
            first_err.get_or_insert(e);
            core::cmp::Ordering::Equal
        })
    });
    first_err.map_or(Ok(()), Err)
}

This reduces worst-case sort time from O(N²) to O(N log N) — at N=18,000 that is >100× faster. No change to accepted/rejected inputs or sort semantics. A secondary element count limit (e.g., reject SET OF with > 1024 elements at decode time) could be added as an optional hardening measure but is not required to fix the algorithmic issue.

Affected versions

Tested in 0.7.x / 0.8.x, might affect all versions.

---

One another finding (maybe feature?

In the same file, the two SET OF types have opposite behaviour on out-of-order DER input:

• SetOfVec::decode_value — silently sorts → accepts non-canonical input
• SetOfRef::from_bytes — rejects with ErrorKind::SetOrdering

Are they work as expected?

---

If I made any mistake, plz let me know. Many thanks.

[tarcieri]

This is a good observation, and suggested resolution.

SetOfRef::from_bytes rejecting non-canonical inputs sounds like a holdover from when that was the previous behavior for the decoder too. We should accept them even though they're invalid DER, simply because that's what other decoders do and such out-of-order DER has become pervasive.