It is always the DNS

[edit: miscellaneous fixes suggested by attentive readers. Thanks!]

I recently took part in an overhaul of both the authoritative and recursing DNS platform at the company I work for.

Then some hard to diagnose problems appeared…

The Internet standards, compiled as the well known IETF RFCs, are constantly evolving: new ones come, and old ones either get formally deprecated or simply aren’t used anymore over time. DNS has a part in all of this as it knits the IP address space to the names we all know when visiting websites or emailing someone. Earlier this year at the company I work for both our authoritative and recursive DNS platforms where updated to make sure we can offer the latest in privacy and security.

One of our customers started to experience intermittent outages shortly after the modernisation of the ProcoliX DNS platform. They could at times not receive email nor were they able to send it. In both cases, the recursive DNS claimed that “the domain didn’t exist”. Which is strange because when we checked it out looked just fine, though the logs of the email server confirmed the customer’s observation. This became unworkable for the customer and they asked us to have this sorted out.

The first thing that needed to happen was a) figure out how this happens and then b) reproduce it reliably. Without any clue nor lead the only way was painstakingly through observation, and when caught in the act determine the state of the involved systems.

We did check the DNSSEC enabled domain involved for inconsistencies right from the start using e.g. DNSViz or NLNetLabs drill from their ldns suite. These tools didn’t indicate a DNSSEC error as such, and neither did the DNS recursor logs complain about invalid DNSSEC signatures. So far so good…

There might be something wrong with the “on wire” format of some responses, and started to inspect DNS traffic between our recursors and the authoritative DNS of the domain involved. Also there is nothing out of the extraordinary:

• The clients asks DNSDist, our first line of defence against DNS abuse
• DNSDist then relays the question to PowerDNS recursor
• When not already cached from a previous query the recursor then proceeds to find out the authoritative DNS servers for that domain and query those.
  • There is some initial communication over UDP
  • The recursor gets signalled the answer is too large for UDP
  • The recursor retries with TCP that can handle answers of arbitrary length but doing so is more costly in time and performance to perform.

That is until the problem occurs, where it was observed the client is doing the query but the recursing DNS does not go out on the Internet to fetch the answer from the applicable authoritative DNS. Instead, the recursing DNS immediately returns… “the answer you are looking for does not exist”.

As if the query was already done previously, deemed nonexistent, and cached as a negative answer.

The response indicated it was a genuine negative answer: Empty answer section, and a “start of authority” (aka SOA) record in the response’s authority section with a timer (time to live, TTL) to indicate how long this negative answer should be cached.

An example with nonexistent.example.com, illustrates how a negative answer looks using NLNetLabs’ drill.

$ drill nonexistent.example.com 
;; ->>HEADER<<- opcode: QUERY, rcode: NXDOMAIN, id: 40415
;; flags: qr rd ra ; QUERY: 1, ANSWER: 0, AUTHORITY: 1, ADDITIONAL: 0 
;; QUESTION SECTION:
;; nonexistent.example.com.     IN      A

;; ANSWER SECTION:

;; AUTHORITY SECTION:
example.com.    3556    IN      SOA     ns.icann.org. noc.dns.icann.org. 2021090201 7200 3600 1209600 3600

;; ADDITIONAL SECTION:

;; Query time: 2 msec
;; SERVER: 2001:db8::53
;; WHEN: Wed Sep 15 17:29:46 2021
;; MSG SIZE  rcvd: 97

The TTL, current at 3556, in the authority section’s SOA record indicates how long this recursor (at 2001:db8::53) can continue to say it does not exist before looking for it on the Internet again.

Meanwhile, the customer’s issue was mitigated with a recursing DNS server dedicated to them which made the problem harder to observe.

Still, there was an issue to be explained and through a monitoring check we still saw the issue triggered at times. However, full packet capture and full systems logging didn’t reveal anything new we didn’t already knew.

To prevent extensive logging from exhausting both system performance and system resources, a separate testing environment was set up. We should have done that from the early beginning, but in hindsight would not have revealed the cause… directly.

The testing environment was used to assess different means of logging, using trace capabilities of the software involved without the risk of overwhelming production.

It showed the same pattern as the earlier mentioned packet traces, but now from the software’s perspective (and that each and every answer was DNSSEC validated). PowerDNS recursor’s rec_control(1) trace-regex command proved to be of much value here as it allowed for very verbose tracing of queries on just matching domains, and not everything else that passed by.

Isolated and with a synthesised workload the issue was not provoked which indicated there must be some other, but as of yet, hidden dependency to trigger it.

Something that occurs at the moment the negative cache entry is created. It is possible to find out what was going on at that moment because you have a timer so one can count back in time to where it happened.

This, and the assumption trace logging of these queries for this domain would not overwhelm production, made us realise that the troubleshooting could and should continue on production, where the monitoring for this issue occasionally still fired despite the customer being no longer impacted by the mitigation.

When the monitoring fired, it finally became possible to see what happened at the inception time of the negative caching: a request was made for a non-existing name, and created a negative cache entry for it.

The existing MX record expired from the cache and needs to be queried again. But this time it is already present as a (negative) cache entry as shown in the trace set with rec_control trace-regex ‘minjenv\.nl\.$’ earlier on.

Sep 01 15:32:36 pdns_recursor[57696]: QM minjenv.nl.|MX child=(empty): doResolve
Sep 01 15:32:36 pdns_recursor[57696]: minjenv.nl: Wants DNSSEC processing, auth data in query for MX
Sep 01 15:32:36 pdns_recursor[57696]: minjenv.nl: Recursion not requested for 'minjenv.nl|MX', peeking at auth/forward zones
Sep 01 15:32:36 pdns_recursor[57696]: QM minjenv.nl.|MX child=(empty): Step0 Found in cache
Sep 01 15:32:36 pdns_recursor[57696]: Answer to minjenv.nl|MX for [::1]:38853 validates correctly

While this negative cache entry persists, we can look back at its original inception time using the SOA record obtained from the response’s authority section:

$ date -d @$(expr $(date +%s) - $(expr 3600 - $(/usr/bin/dig -t mx minjenv.nl @95.215.185.6 | grep SOA | awk '{print $2}'))) +%FT%T
2021-09-01T15:23:32

Looking back at that time we see that a request was made for a nonexisting A record:

Sep 01 15:23:32 pdns_recursor[57696]: 3 [253565/1] question for 'minjenv.nl|A' from [::1]:38853
Sep 01 15:23:32 pdns_recursor[57696]: : no TA found for 'minjenv.nl' among 1
Sep 01 15:23:32 pdns_recursor[57696]: : no TA found for 'nl' among 1
Sep 01 15:23:32 pdns_recursor[57696]: : got TA for '.'
Sep 01 15:23:32 pdns_recursor[57696]: QM minjenv.nl.|A child=(empty): doResolve
....
A lot of debug output concerning find the proper authoritative nameservers and DNSSEC validation left out for readability 
...
Sep 01 15:23:32 pdns_recursor[57696]: minjenv.nl: determining status after receiving this packet
Sep 01 15:23:32 pdns_recursor[57696]: minjenv.nl: got negative caching indication for 'minjenv.nl|A'
Sep 01 15:23:32 pdns_recursor[57696]: validation state was Secure, state update is Secure, validation state is now Secure
Sep 01 15:23:32 pdns_recursor[57696]: minjenv.nl: status=noerror, other types may exist, but we are done (have negative SOA) (have aa bit)
Sep 01 15:23:32 pdns_recursor[57696]: QM minjenv.nl.|A child=minjenv.nl: Step3 Final resolve: No Error/4
Sep 01 15:23:32 pdns_recursor[57696]: Answer to minjenv.nl|A for [::1]:38853 validates correctly

But why would this also be applicable to existing names? With an empty cache, first asking for the existing record and then the non-existent one didn’t provoke the issue.

The other way around it did. It also finally became possible to reproduce this on the test bed. Time to poll the community whether this was a bug or not. (Spoiler alert, yes it was, but not as I anticipated)

The PowerDNS engineers I spoke on the Dutch Network Operator Group (NLNOG) at first did confirm this might be a bug, but then saw the real culprit: The other side was responding with invalid “NSEC” responses, the signalling mechanism DNSSEC uses to prove an answer does not exist. A recent addition to the standards that encompass DNS is that this information can be used to preemptively declare an answer does not exist, without doing a query at all.

This explained a couple of observations:

• It confirms not seeing the outgoing query as the negative answer was synthesised with aggressive use of DNSSEC validated cache, something that was observed earlier on already
• The new production resolvers employ this strategy by default
• The dedicated resolver used for the customer does not enable this functionality by default

But how?

For a nonexisting answer, a NextSECure (NSEC) or its more privacy-friendly hashed NSEC (NSEC3) record is sent back in the authority section of the DNS answer so it can be cryptographically validated.

Amongst other data in that record, it also lists the record type for names that do exist at the queried location.

If a record does exist for that name, but somehow is omitted from a NSEC/NSEC3 response earlier on, it will be preempted being non-existent by resolvers employing aggressive use of DNSSEC validated cache.

The following was observed in the test bed

$ drill -D @2001:db8::53 A minjenv.nl
;; ->>HEADER<<- opcode: QUERY, rcode: NOERROR, id: 46387
;; flags: qr rd ra ad ; QUERY: 1, ANSWER: 0, AUTHORITY: 4, ADDITIONAL: 0 
;; QUESTION SECTION:
;; minjenv.nl.  IN      A

;; ANSWER SECTION:

;; AUTHORITY SECTION:
minjenv.nl.     3592    IN      SOA     ns1.minvenj.nl. hostmaster.solvinity.com. 2021072701 10800 3600 604800 86400
vo8f2qgvp616nepg0vr59b2dpuh1guem.minjenv.nl.    86392   IN      NSEC3   1 0 1 09f7893649b04b4c  vo8f2qgvp616nepg0vr59b2dpuh1guen NS SOA RRSIG DNSKEY NSEC3PARAM 
minjenv.nl.     3592    IN      RRSIG   SOA 8 2 3600 20210924000051 20210917000051 65451 minjenv.nl. jNenXdcqW9NSGcjPC0833a8Vd6GZxwonCB3tRzJRDGGmCzDhEIyfZMxBUCRn2c046iqeMhbS3qDGsHIKw7qRgp7TNcSYobe9astaIw6R9hwdljDMq0pjdoZH2/E/LBXVbyE/+4lQzjrfPvI6mMf02W2VhD67IqDm+rtR11CUlxM=
vo8f2qgvp616nepg0vr59b2dpuh1guem.minjenv.nl.    86392   IN      RRSIG   NSEC3 8 3 86400 20210924094112 20210917094112 65451 minjenv.nl. S09UOv1T9zAvCd5WJe6tgF8rJzvRrEZjPw1Xoq+6vvF0caz4Nsc7dkv62T6sev4s+00t+3sdbsJ3FwHBDwxW7DTTh5oncTqP5un9unjIri8m7XLobM01TtnPy+HV+QOkUX06Rzp24A8nDvAT/wMB6qrybnNaJ+qkPHFwMFNvNkI=

;; ADDITIONAL SECTION:

;; Query time: 0 msec
;; EDNS: version 0; flags: do ; udp: 512
;; SERVER: 2001:db8::53
;; WHEN: Fri Sep 17 17:18:51 2021
;; MSG SIZE  rcvd: 539

Looking at the NSEC3 response we see the following

vo8f2qgvp616nepg0vr59b2dpuh1guem.minjenv.nl.    86392   IN      NSEC3   1 0 1 09f7893649b04b4c  vo8f2qgvp616nepg0vr59b2dpuh1guen NS SOA RRSIG DNSKEY NSEC3PARAM 

Whereas A does not exist, it does indicate NS, SOA, RRSIG, DNSKEY, and NSEC3PARAM are available for vo8f2qgvp616nepg0vr59b2dpuh1guem.minjenv.nl.

To see that vo8f2qgvp616nepg0vr59b2dpuh1guem.minjenv.nl. indeed corresponds with minjenv.nl itself, the ldns-nsec3-hash tool (also from NLNetLabs’s ldns suite) can be used. This tool needs to know the algorithm used for -a, iterations for -t, and salt for -s which can be obtained by decoding the NSEC3 record as follows:

... NSEC3 algorithm flags iterations salt ...

This tells us that the NSEC3 record is indeed for the name minvenj.nl.

$ ldns-nsec3-hash -a 1 -t 1 -s 09f7893649b04b4c minjenv.nl
vo8f2qgvp616nepg0vr59b2dpuh1guem.

Furthermore, the record is validly DNSSEC signed (see the ad bit (authentication delivered) in the header) and therefore a resolver complying with RFC8198 can use it to return requests for record types which are not in this list.

According to the DNSSEC proof above, there is not only no A resource record type, but also no MX (mail exchange) nor AAAA (IPv6 address) resource record type available for minvenj.nl. At least one of these is needed for an e-mail server to deliver e-mail addressed to minvenj.nl.

An inconvenience at best (just keep retrying), a denial of service at worst: Knowing a DNSSEC protected domain might generate incomplete NSEC records an attacker could create a denial of service attack by (letting) querying nonexisting names which will then mask the types not present in the NSEC record, potentially rendering either websites or email “broken”.

This was also discussed in brief with the DNS-OARC community, where they independently confirmed the same thing as the PowerDNS developers did: the other side was responding with invalid “NSEC” responses and considered a security risk due to the possibility of abuse.

The follow-up on this is that for now a grace period is implemented in which aggressive use of DNSSEC validated cache is disabled, and contact involved parties and ask them to address this issue during this grace period.

DNS, since its inception in 1987, has seen a lot of additions throughout the years. It transformed from a relatively maintenance-free service towards something that needs active care.

DNSSEC, devised in 2005 and put in operation in 2010, was a major game changer. Also, DNS got an increased “public utility” role these days prompting for ever-present availability. Gaining complexity also means misinterpretation of standards can lead to inoperability issues that should be fixed and not mitigated.

Easy access to the OpenSource community that has your back is a big help. Maintaining internet infrastructure, which has been derived from OpenSource at large, is a multi-stakeholder initiative.

I would also like to thank the people from PowerDNS, Knot resolver, and NLNetLabs for the discussions and suggestions whom I spoke to in the NLNOG and DNS-OARC communities.