QNAME Minimization and Spamhaus

Update: Spamhaus has issued a blog responding to this issue.

A recent thread on the bind-users mailing list discussed an issue with QNAME minimization and Spamhaus's DNS servers. We have created a GitLab issue about it, but the issue appears to be non RFC-compliant responses from Spamhaus's DNS servers. This is our analysis of the situation.

The Problem

On the bind-users mailing list, a user reported receiving the following lame-servers responses to virtually every query to Spamhaus's DNS servers:

07-Sep-2023 14:30:13.608 lame-servers: FORMERR resolving '
mykey.hbl.dq.spamhaus.net/NS/IN': 66.42.94.100#53
07-Sep-2023 14:30:13.625 resolver: DNS format error from 143.215.143.8#53
resolving mykey.hbl.dq.spamhaus.net/NS for <unknown>: reply has no answer
07-Sep-2023 14:30:13.625 lame-servers: FORMERR resolving '
mykey.hbl.dq.spamhaus.net/NS/IN': 143.215.143.8#53
07-Sep-2023 14:30:13.628 lame-servers: success resolving
'psnobcays3v2r52vapfv5fgvr6pgd6znvuzyhe5ktid3ty3oai4q._
file.mykey.hbl.dq.spamhaus.net/A' after disabling qname minimization due to
'failure'

07-Sep-2023 14:39:30.214 lame-servers: success resolving '
22.10.223.192.bl.spamcop.net/A' after disabling qname minimization due to
'ncache nxdomain'

The user wondered why these errors were being reported.

Our Analysis

ISC engineer Mark Andrews investigated and discovered that Spamhaus’s servers are incorrectly answering the NS query. Spamhaus is sending back the NS records for the top of the zone rather than the correct NODATA responses for empty non-terminal names. The reason this RFC non-compliance matters is that named uses the response from NS queries for QNAME minimization.

Spamhaus's initial recommendation was to disable QNAME minimization altogether, but ISC disagrees: the correct solution is for Spamhaus to fix its broken servers. QNAME minimization is an important privacy protection that is enabled by default in BIND and in most standards-based DNS implementations today.

Spamhaus's servers give correct answers for DS, A, TXT, AAAA, and other types of records. However, they give incorrect answers for NS (instead, they give a referral back to the same servers), for SOA (the zone's SOA record is returned in the ANSWER section instead of the AUTHORITY section for NODATA), and for TYPE1000 (they return NOTIMP instead of NOERROR NODATA, which they do for DS, A, TXT, AAAA, and others). The correct behavior is specified in RFC 1034. QNAME minimization (RFC 7816) is a security fix designed to prevent the leaking of query names and types to servers closer to the root that don’t need this information; it works with all servers that are DNS protocol-compliant. Turning off a privacy feature is not a viable solution.

The Details

From RFC 1034, 4.3.2. Algorithm:

...
2. Search the available zones for the zone which is the nearest
ancestor to QNAME. If such a zone is found, go to step 3,
otherwise step 4.

3. Start matching down, label by label, in the zone. The
   matching process can terminate several ways:

   a. If the whole of QNAME is matched, we have found the
   node.

   If the data at the node is a CNAME, and QTYPE doesn’t
   match CNAME, copy the CNAME RR into the answer section
   of the response, change QNAME to the canonical name in
   the CNAME RR, and go back to step 1.

   Otherwise, copy all RRs which match QTYPE into the
   answer section and go to step 6.
   ...

4. Using local data only, attempt to add other RRs which may be
   useful to the additional section of the query. Exit.

Step 2 gives zrd.dq.spamhaus.net. Step 3a matches pc5eqyfskhlh55qut433gdq2gq.zrd.dq.spamhaus.net; as there are no NS records at that name, the answer section should be empty. Adding referral records would be done in step 3b, which is skipped:

    b. If a match would take us out of the authoritative data,
    we have a referral. This happens when we encounter a
    node with NS RRs marking cuts along the bottom of a
    zone.

    Copy the NS RRs for the subzone into the authority
    section of the reply. Put whatever addresses are
    available into the additional section, using glue RRs
    if the addresses are not available from authoritative
    data or the cache. Go to step 4.

% dig 'pc5eqyfskhlh55qut433gdq2gq.zrd.dq.spamhaus.net' ds @a.gns.spamhaus.net

; <<>> DiG 9.19.17-dev <<>> pc5eqyfskhlh55qut433gdq2gq.zrd.dq.spamhaus.net ds @a.gns.spamhaus.net
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 26823
;; flags: qr aa rd; QUERY: 1, ANSWER: 0, AUTHORITY: 1, ADDITIONAL: 1
;; WARNING: recursion requested but not available

;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 2048
;; QUESTION SECTION:
;pc5eqyfskhlh55qut433gdq2gq.zrd.dq.spamhaus.net. IN DS

;; AUTHORITY SECTION:
zrd.dq.spamhaus.net. 1 IN SOA need.to.know.only. hostmaster.spamhaus.org. 2309182309 3600 600 432000 1

;; Query time: 194 msec
;; SERVER: 149.28.9.86#53(a.gns.spamhaus.net) (UDP)
;; WHEN: Tue Sep 19 09:11:44 AEST 2023
;; MSG SIZE  rcvd: 151

% dig 'pc5eqyfskhlh55qut433gdq2gq.zrd.dq.spamhaus.net' txt @a.gns.spamhaus.net

; <<>> DiG 9.19.17-dev <<>> pc5eqyfskhlh55qut433gdq2gq.zrd.dq.spamhaus.net txt @a.gns.spamhaus.net
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 65222
;; flags: qr aa rd; QUERY: 1, ANSWER: 0, AUTHORITY: 1, ADDITIONAL: 1
;; WARNING: recursion requested but not available

;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 2048
;; QUESTION SECTION:
;pc5eqyfskhlh55qut433gdq2gq.zrd.dq.spamhaus.net. IN TXT

;; AUTHORITY SECTION:
zrd.dq.spamhaus.net. 1 IN SOA need.to.know.only. hostmaster.spamhaus.org. 2309182309 3600 600 432000 1

;; Query time: 188 msec
;; SERVER: 149.28.9.86#53(a.gns.spamhaus.net) (UDP)
;; WHEN: Tue Sep 19 09:12:05 AEST 2023
;; MSG SIZE  rcvd: 151

% dig 'pc5eqyfskhlh55qut433gdq2gq.zrd.dq.spamhaus.net' soa @a.gns.spamhaus.net

; <<>> DiG 9.19.17-dev <<>> pc5eqyfskhlh55qut433gdq2gq.zrd.dq.spamhaus.net soa @a.gns.spamhaus.net
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 29540
;; flags: qr aa rd; QUERY: 1, ANSWER: 1, AUTHORITY: 0, ADDITIONAL: 1
;; WARNING: recursion requested but not available

;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 2048
;; QUESTION SECTION:
;pc5eqyfskhlh55qut433gdq2gq.zrd.dq.spamhaus.net. IN SOA

;; ANSWER SECTION:
zrd.dq.spamhaus.net. 900 IN SOA need.to.know.only. hostmaster.spamhaus.org. 2309182311 3600 600 432000 1

;; Query time: 188 msec
;; SERVER: 149.28.9.86#53(a.gns.spamhaus.net) (UDP)
;; WHEN: Tue Sep 19 09:12:18 AEST 2023
;; MSG SIZE  rcvd: 151

% dig 'pc5eqyfskhlh55qut433gdq2gq.zrd.dq.spamhaus.net' ns @a.gns.spamhaus.net

; <<>> DiG 9.19.17-dev <<>> pc5eqyfskhlh55qut433gdq2gq.zrd.dq.spamhaus.net ns @a.gns.spamhaus.net
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 30418
;; flags: qr aa rd; QUERY: 1, ANSWER: 5, AUTHORITY: 0, ADDITIONAL: 1
;; WARNING: recursion requested but not available

;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 2048
;; QUESTION SECTION:
;pc5eqyfskhlh55qut433gdq2gq.zrd.dq.spamhaus.net. IN NS

;; ANSWER SECTION:
zrd.dq.spamhaus.net. 3600 IN NS a.gns.spamhaus.net.
zrd.dq.spamhaus.net. 3600 IN NS b.gns.spamhaus.net.
zrd.dq.spamhaus.net. 3600 IN NS c.gns.spamhaus.net.
zrd.dq.spamhaus.net. 3600 IN NS d.gns.spamhaus.net.
zrd.dq.spamhaus.net. 3600 IN NS e.gns.spamhaus.net.

;; Query time: 187 msec
;; SERVER: 149.28.9.86#53(a.gns.spamhaus.net) (UDP)
;; WHEN: Tue Sep 19 09:12:23 AEST 2023
;; MSG SIZE  rcvd: 159

% dig 'pc5eqyfskhlh55qut433gdq2gq.zrd.dq.spamhaus.net' type1000 @a.gns.spamhaus.net

; <<>> DiG 9.19.17-dev <<>> pc5eqyfskhlh55qut433gdq2gq.zrd.dq.spamhaus.net type1000 @a.gns.spamhaus.net
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOTIMP, id: 3121
;; flags: qr rd; QUERY: 1, ANSWER: 0, AUTHORITY: 0, ADDITIONAL: 1
;; WARNING: recursion requested but not available

;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; udp: 2048
;; QUESTION SECTION:
;pc5eqyfskhlh55qut433gdq2gq.zrd.dq.spamhaus.net. IN TYPE1000

;; Query time: 201 msec
;; SERVER: 149.28.9.86#53(a.gns.spamhaus.net) (UDP)
;; WHEN: Tue Sep 19 09:12:42 AEST 2023
;; MSG SIZE  rcvd: 75