(Migrated from Issue#4610) max-recursion-queries substantially exceeded by crafted query patterns

Summary

We would like to report a potential DoS vulnerability. BIND limits the number of resolver queries to serve a client request by setting max-recursion-queries. This helps to cap the amplification effects on a BIND recursive resolver under application-layer amplification attacks (e.g., the recent NXNSAttack). However, we find that this feature is not correctly implemented, and it is possible to exceed the default limit of 100 with certain query patterns. We have managed to achieve a message amplification factor (MAF) over 1400, i.e., a single client request triggers >1400 queries to be sent by a BIND recursive resolver (and >800 of those queries can be directed towards a single name server). This vulnerability can be exploited to launch powerful DoS attacks that abuse or target BIND recursive resolvers.

Below is a quick summary of three query patterns that lead to large MAF. There are potenetially many more such patterns.

1. Rewrite chain composed with referral chain: MAF=178 if using only IPv4 (named -v), MAF=337 otherwise

   The idea is to construct a chain of CNAME (or DNAME) RRs such that the resolution of each name on the rewrite chain in turn follows a chain of NS records. By properly arranging these RRs, we only need two authoritative nameservers to host all zones required for the setup. A vulnerable recursive resolver will chase the rewrite chain and all referral chains.

2. Rewrite chain composed with concurrent referral: MAF=260 if using only IPv4, MAF=486 otherwise

   This setup is similar to the one above, except that the resolution of each name on the rewrite chain leads to the resolution of a large NS RRSet. A vulnerable resolver will try to resolve multiple NS names in each NS RRset.

3. Rewrite chain composed with concurrent referral further composed with referral chain: MAF=1420 if using only IPv4, MAF=1555 otherwise

   This setup extends the second two-dimensional composition with a third dimension. In particular, each NS name in an NS RRset further initiates a referral chain, forcing a vulnerable recursive resolver to send multiplicatively many queries.

BIND versions affected

Version up to and including 9.18.21.

BIND 9.18.21 (Extended Support Version) id:cb6cff6

Preconditions and assumptions

• Two authoritative nameservers set up with the required zones.
• For the current report, DNSSEC is disabled in our setup. We find that DNSSEC can further intensify the amplification and DoS effects. We will send our findings on DNSSEC in a separate report.

Attacker's abilities

Attacker needs to set up two authoritative nameservers with specially crafted zone files, and send a single request to the vulnerable BIND recursive resolver.

Impact

With a single client request we managed to trigger >1400 queries to be sent by a BIND recursive resolver and more than 800 of those can be directed to a single authoritative nameserver. This vulnerability can be exploited to launch powerful DoS attacks targeting a vulnerable BIND server running in recursive or authoritative mode.

Steps to reproduce

We have provided a dockerised testbed attached. In the README, you can find detailed commands to reproduce our results. You can also find the pre-run results and logs for each query pattern. If any issues arise, we would be happy to provide further assistance.

What is the current bug behavior?

• Resolver CPU load increases to 100% at low attacker client QPS (e.g., <10 for a 2.7GHz core)
• Legitimate QPS drops by 20% at low attacker client QPS
• Latency of legitimate queries increases over 10x

What is the expected correct behavior?

BIND stops serving a client request after having generated max-recursion-queries iterative queries.

Relevant logs

Logs and traces from tcpdump can be found in the corresponding query pattern folders.

Coordination

Other tested implementations

• Unbound with versions up to 1.19.0
• PowerDNS with versions up to 4.9.X

We have also shared the information with Swiss National Cybersecurity Center (NSCS). After our investigations with the major DNS software vendors are concluded, they will help conduct coordinated disclosure to global DNS operators through their international partners (e.g., GovCERTs and IWWN).

We plan to go public during conference USENIX Security'24 on 2024-08-14

Acknowledgements