Non-responsive delegation: CPU exhaustion in Unbound and BIND 9 resolvers

Paul Mockapetris wrote this into RFC 1034 in 1987, in a list of recommended priorities for anyone implementing a resolver:

Bound the amount of work (packets sent, parallel processes started) so that a request can't get into an infinite loop or start off a chain reaction of requests or queries with other implementations EVEN IF SOMEONE HAS INCORRECTLY CONFIGURED SOME DATA.

The capitals are his. Yehuda Afek of Tel-Aviv University, with Anat Bremler-Barr and Shani Stajnrod of Reichman University, quote it at the top of a paper. The paper describes a single DNS query that costs a BIND 9 resolver about 5,600 times as many CPU instructions as an ordinary one. They call it the Non-Responsive Delegation Attack. It got three CVEs across three resolver implementations in September

1. Unbound's is CVE-2022-3204, and that advisory is the easiest of the three to read.

Referral responses#

When your resolver looks up www.example.com it doesn't ask one server. It asks a root server. The root says "not me, ask the servers for .com". It asks one of those and gets "not me, ask the servers for example.com". Each of those answers is a referral response: a list of nameserver names for the zone below.

Two things about that list matter here.

It can be long. Referral responses carry several nameservers for fault tolerance. Nothing caps the count at anything small.

And it is a list of names, not addresses. Sometimes the referral includes the addresses as extra records, which are called glue. Often it can't. An authoritative server isn't allowed to hand out addresses for domains outside its own zone, because that's a cache-poisoning primitive. Those are out-of-bailiwick nameservers. For each one the resolver has to run a whole separate resolution just to find out where to send the next query.

So a referral response is a to-do list of arbitrary length. Every item on it is itself a lookup.

The NXNSAttack mitigation#

In 2020 the NXNSAttack used exactly this. A malicious authoritative server answers with a referral naming hundreds of nonexistent nameservers. The resolver dutifully starts resolving all of them at once, in parallel. That floods the resolver itself and everyone else's servers with it.

The mitigation everybody shipped was a cap: on receiving a referral, resolve only the first k names for this client query. BIND 9 and Knot use k = 5, Unbound uses 6. If those all come back NXDOMAIN, give up, return an error, done. BIND 9 enforces the cap with a flag on the lookup, DNS_ADBFIND_NOFETCH, or No_Fetch. It means "the referral limit has been reached for this one, don't go fetching more".

Now the other mechanism. When a resolver gets delegated somewhere new it does a restart: it resets its state and continues resolving at the new server. Restarts have been in the protocol since RFC 1034, and they're how delegation works at all. Part of resetting the state is clearing a handful of flags. No_Fetch is one of them.

The paper's insight is what happens when you combine the two. The trick is to change one word in the NXNSAttack. Instead of nonexistent nameservers, use nameservers that exist and simply never answer.

The chain, from the paper:

1. The malicious authoritative sends a referral listing n names, up to about 1,500, with no glue.
2. Before starting on any of them, the resolver checks all n against its cache and its address database to see whether any already has a usable answer. For large n this is not cheap. The paper calls this cost CC(n) and it's the engine of the whole attack.
3. Because of the NXNSAttack fix, the resolver then starts resolving only k of them.
4. Each of those k leads to a delegation, which triggers a restart.
5. Each restart clears No_Fetch, so the referral limit is forgotten. The resolver goes back to step 2 (a full cache scan over all n names) and picks up k more names from the list.

That's k restarts in the first round, producing k more resolutions each, so k² in the next. The paper puts the accumulated cost at (k + k²) · CC(n), and rising. Only n and the safety counters bound it. In BIND 9 the total restart limit is 100.

The nameservers don't respond rather than returning NXDOMAIN, so there's no early exit. The NXNSAttack burned itself out as soon as an NXDOMAIN came back. Here the resolver sits and waits, hopefully, and keeps chewing through the list while it waits.

The measured result on a BIND 9 resolver is 1.1 billion instructions per attacker query against 195,000 for a benign one. The paper also compares the same attack against pre- and post-NXNSAttack builds of BIND 9. The old code spent 292 million instructions, the patched code 3,415 million. The mitigation made it worse by more than a factor of ten.

None of this requires much. The threat model is a client you control, an authoritative nameserver you control, and a list of domain names whose servers don't answer. The authors note they bought several domains for under a dollar each in under five minutes.

What the vendors did#

Send 15,000 malicious packets per second with a referral list of 1,500 names. Throughput for legitimate users then dropped by a factor of 609 on BIND 9, 388 on Knot, and 58 on Unbound.

That last number explains the Unbound advisory. It is rated MEDIUM, and it says:

Unbound does not suffer from high CPU usage, but resources are still needed for resolving the malicious delegation. Unbound 1.16.3 includes fixes for better performance when under load.

That is a fair description of the fix, because it isn't a correctness patch. There's nothing here that violates a spec. Every message in the attack is well-formed and every step the resolver takes is a step it is supposed to take. The bug is that a small input buys a large amount of work. So 1.16.3 ships performance work:

cutting opportunistic queries for nameserver discovery and DNSKEY prefetching and limiting the number of times a delegation point can issue a cache lookup for missing records.

That last clause is the one that matters. It puts a ceiling on how many times step 2 can run.

Versions up to and including 1.16.2 are affected; 1.16.3 has the fix. ISC's advisory for the BIND 9 half is CVE-2022-2795, titled "Processing large delegations may severely degrade resolver performance". It is rated Medium at CVSS 5.3, and it affects 9.0.0 through 9.16.32, 9.18.0 through 9.18.6 and 9.19.0 through 9.19.4. The fixes are in 9.16.33, 9.18.7 and 9.19.5. ISC lists no workarounds.

Both advisories credit Afek, Bremler-Barr and Stajnrod by name. The full paper landed at USENIX Security in August 2023. The authors also report testing the attack against the top 16 open resolvers, and finding all of them affected to some degree.

Sources

1. 1Unbound advisory for CVE-2022-3204, the NRDelegation Attacknlnetlabs.nl
2. 2NLnet Labs index of all Unbound security advisoriesnlnetlabs.nl
3. 3Red Hat bug 2128947: CVE-2022-3204 unbound NRDelegation resource consumptionbugzilla.redhat.com