We launched DNSSEC late last year and are already signing 56.9 billion DNS record sets per day. At this scale, we care a great deal about compute cost. One of the ways we save CPU cycles is our unique implementation of negative answers in DNSSEC.
CC BY-SA 2.0 image by Chris Short
I will briefly explain a few concepts you need to know about DNSSEC and negative answers, and then we will dive into how CloudFlare saves on compute when asked for names that don’t exist.
What You Need To Know: DNSSEC Edition
Here’s a quick summary of DNSSEC:
This is an unsigned DNS answer (unsigned == no DNSSEC):
cloudflare.com. 299 IN A 198.41.214.162
cloudflare.com. 299 IN A 198.41.215.162
This is an answer with DNSSEC:
cloudflare.com. 299 IN A 198.41.214.162
cloudflare.com. 299 IN A 198.41.215.162
cloudflare.com. 299 IN RRSIG A 13 2 300 20160311145051 20160309125051 35273 cloudflare.com. RqRna0qkih8cuki++YbFOkJi0DGeNpCMYDzlBuG88LWqx+Aaq8x3kQZX TzMTpFRs6K0na9NCUg412bOD4LH3EQ==
Answers with DNSSEC contain a signature for every record type that is returned. (In this example, only A records are returned so there is only one signature.) The signatures allow DNS resolvers to validate the records returned and prevent on-path attackers from intercepting and changing the answers.
What You Need To Know: Negative Answer Edition
There are two types of negative answers. The first is NXDOMAIN
, which means that the name asked for does not exist. An example of this is a query asking for missing.cloudflare.com
. missing.cloudflare.com
doesn’t exist at all.
The second type is NODATA
, which means that the name does exist, just not in the requested type. An example of this would be asking for the MX
record of blog.cloudflare.com
. There are A
records for blog.cloudflare.com
but no MX
records so the appropriate response is NODATA
.
What Goes Into An NXDOMAIN With DNSSEC
To see what gets returned in a negative NXDOMAIN
answer, let’s look at the response for a query for bogus.ietf.org
.
The first record that has to be returned in a negative answer with DNSSEC is an SOA, just like in an unsigned negative answer. The SOA contains some metadata about the zone and lets the recursor know how long to cache the negative answer for.
ietf.org. 1179 IN SOA ns0.amsl.com. glen.amsl.com. 1200000325 1800 1800 604800 1800
Because the domain is signed with DNSSEC, the signature for the SOA
is also returned:
ietf.org. 1179 IN RRSIG SOA 5 2 1800 20170308083354 20160308073501 40452 ietf.org. S0gIjTnQGA6TyIBjCeBXL4ip8aEQEgg2y+kCQ3sLtFa3oNy9vj9kj4aP 8EVu4oIexr8X/i9L8Oj5ec4HOrQoYsMGObRUG0FGT0MEbxepi+wWrfed vD/3mq8KZg/pj6TQAKebeSQGkmb8y9eP0PdWdUi6EatH9ZY/tsoiKyqg U4vtq9sWZ/4mH3xfhK9RBI4M7XIXsPX+biZoik6aOt4zSWR5WDq27pXI 0l+BLzZb72C7McT4PlBiF+U86OngBlGxVBnILyW2aUisi2LY6KeO5AmK WNT0xHWe5+JtPD5PgmSm46YZ8jMP5mH4hSYr76jqwvlCtXvq8XgYQU/P QyuCpQ==
The next part of the negative answer in DNSSEC is a record type called NSEC
. The NSEC
record returns the previous and next name in the zone, which proves to the recursor that the queried name cannot possibly exist, because nothing exists between the two names listed in the NSEC record.
www.apps.ietf.org. 1062 IN NSEC cloudflare-verify.ietf.org. A RRSIG NSEC
This NSEC
record above tells you that bogus.ietf.org
does not exist because no names exist canonically between www.apps.ietf.org
and cloudflare-verify.ietf.org
. Of course, this record also has a signature contained in the answer:
www.apps.ietf.org. 1062 IN RRSIG NSEC 5 4 1800 20170308083322 20160308073501 40452 ietf.org. NxmjhCkTtoiolJUow/OreeBRxTtf2AnIPM/r2p7oS/hNeOdFI9tpgGQY g0lTOYjcNNoIoDB/r56Kd+5wtuaKT+xsYiZ4K413I+cmrNQ+6oLT+Mz6 Kfzvo/TcrJD99PVAYIN1MwzO42od/vi/juGkuKJVcCzrBKNHCZqu7clu mU3DEqbQQT2O8dYIUjLlfom1iYtZZrfuhB6FCYFTRd3h8OLfMhXtt8f5 8Q/XvjakiLqov1blZAK229I2qgUYEhd77n2pXV6SJuOKcSjZiQsGJeaM wIotSKa8EttJELkpNAUkN9uXfhU+WjouS1qzgyWwbf2hdgsBntKP9his 9MfJNA==
A second NSEC record is also returned to prove that there is no wildcard that would have covered bogus.ietf.org
:
ietf.org. 1062 IN NSEC ietf1._domainkey.ietf.org. A NS SOA MX TXT AAAA RRSIG NSEC DNSKEY SPF
This record above tells you that a wildcard (*. ietf.org
) would have existed between those two names. Because there is no wildcard record at *.ietf.org
, as proven by this NSEC record, the DNS resolver knows that really nothing should have been returned for bogus.ietf.org
. This NSEC
record also has a signature:
ietf.org. 1062 IN RRSIG NSEC 5 2 1800 20170308083303 20160308073501 40452 ietf.org. homg5NrZIKo0tR+aEp0MVYYjT7J/KGTKP46bJ8eeetbq4KqNvLKJ5Yig ve4RSWFYrSARAmbi3GIFW00P/dFCzDNVlMWYRbcFUt5NfYRJxg25jy95 yHNmInwDUnttmzKuBezdVVvRLJY3qSM7S3VfI/b7n6++ODUFcsL88uNB V6bRO6FOksgE1/jUrtz6/lEKmodWWI2goFPGgmgihqLR8ldv0Dv7k9vy Ao1uunP6kDQEj+omkICFHaT/DBSSYq59DVeMAAcfDq2ssbr4p8hUoXiB tNlJWEubMnHi7YmLSgby+m8b97+8b6qPe8W478gAiggsNjc2gQSKOOXH EejOSA==
All in all, the negative answer for bogus.ietf.org
contains an SOA + SOA RRSIG + (2) NSEC + (2) NSEC RRSIG
. It is 6 records in total, returning an answer that is 1095 bytes (this is a large DNS answer).
Zone Walking
What you may have noticed is that because the negative answer returns the previous and next name, you can keep asking for next names and essentially “walk” the zone until you learn every single name contained in it.
For example, if you ask for the NSEC
on ietf.org
, you will get back the first name in the zone, ietf1._domainkey.ietf.org
:
ietf.org. 1799 IN NSEC ietf1._domainkey.ietf.org. A NS SOA MX TXT AAAA RRSIG NSEC DNSKEY SPF
Then if you ask for the NSEC
on ietf1._domainkey.ietf.org
you will get the next name in the zone:
ietf1._domainkey.ietf.org. 1799 IN NSEC apps.ietf.org. TXT RRSIG NSEC
And you can keep going until you get every name in the zone:
apps.ietf.org. 1799 IN NSEC mail.apps.ietf.org. MX RRSIG NSEC
The root zone uses NSEC
as well, so you can walk the root to see every TLD:
The root NSEC:
. 21599 IN NSEC aaa. NS SOA RRSIG NSEC DNSKEY
.aaa NSEC
:
aaa. 21599 IN NSEC aarp. NS DS RRSIG NSEC
.aarp NSEC
:
aarp. 21599 IN NSEC abb. NS DS RRSIG NSEC
Zone walking was actually considered a feature of the original design:
The complete
NXT
chains specified in this document enable a resolver to obtain, by successive queries chaining throughNXT
s, all of the names in a zone. - RFC2535
(NXT
is the original DNS record type that NSEC
was based off of)
However, as you can imagine, this is a terrible idea for some zones. If you could walk the .gov
zone, you could learn every US government agency and government agency portal. If you owned a real estate company where every realtor got their own subdomain, a competitor could walk through your zone and find out who all of your realtors are.
So the DNS community rallied together and found a solution. They would continue to return previous and next names, but they would hash the outputs. This was defined in an upgrade to NSEC
called NSEC3
.
6rmo7l6664ki2heho7jtih1lea9k6los.icann.org. 3599 IN NSEC3 1 0 5 2C21FAE313005174 6S2J9F2OI56GPVEIH3KBKJGGCL21SKKL A RRSIG
NSEC3
was a “close but no cigar” solution to the problem. While it’s true that it made zone walking harder, it did not make it impossible. Zone walking with NSEC3
is still possible with a dictionary attack. An attacker can use a list of the most common hostnames, hash them with the hashing algorithm used in the NSEC3
record (which is listed in the record itself) and see if there are any matches. Even if the domain owner uses a salt on the hash, the length of the salt is included in the NSEC3
record, so there are a finite number of salts to guess.
The Salt Length field defines the length of the salt in octets, ranging in value from 0 to 255.”
NODATA Responses
If you recall from above, NODATA
is the response from a server when it is asked for a name that exists, but not in the requested type (like an MX
record for blog.cloudflare.com
). NODATA
is similar in output to NXDOMAIN
. It still requires SOA
, but it only takes one NSEC
record to prove the next name, and to specify which types do exist on the queried name.
For example, if you look for a TXT
record on apps.ietf.org
, the NSEC
record will tell you that while there is no TXT
record on apps.ietf.org
, there are MX
, RRSIG
and NSEC
records.
apps.ietf.org. 1799 IN NSEC mail.apps.ietf.org. MX RRSIG NSEC
Problems With Negative Answers
There are two problems with negative answers:
The first is that the authoritative server needs to return the previous and next name. As you’ll see, this is computationally expensive for CloudFlare, and as you’ve already seen, it can leak information about a zone.
The second is that negative answers require two NSEC
records and their two subsequent signatures (or three NSEC3
records and three NSEC3
signatures) to authenticate the nonexistence of one name. This means that answers are bigger than they need to be.
The Trouble with Previous and Next Names
CloudFlare has a custom in house DNS server built in Go called RRDNS. What's unique about RRDNS is that unlike standard DNS servers, it does not have the concept of a zone file. Instead, it has a key value store that holds all of the DNS records of all of the domains. When it gets a query for a record, it can just pick out the record that it needs.
Another unique aspect of CloudFlare's DNS is that a lot of our business logic is handled in the DNS. We often dynamically generate DNS answers on the fly, so we don't always know what we will respond with before we are asked.
Traditional negative answers require the authoritative server to return the previous and next name of a missing name. Because CloudFlare does not have the full view of the zone file, we'd have to ask the database to do a sorted search just to figure out the previous and next names. Beyond that, because we generate answers on the fly, we don’t have a reliable way to know what might be the previous and next name, unless we were to precompute every possible option ahead of time.
One proposed solution to the previous and next name, and secrecy problems is RFC4470, dubbed 'White Lies'. This RFC proposes that DNS operators make up a previous and next name by randomly generating names that are canonically slightly before and after the requested name.
White lies is a great solution to block zone walking (and it helps us prevent unnecessary database lookups), but it still requires 2 NSEC
records (one for previous and next name and another for the wildcard) to say one thing, so the answer is still bigger than it needs to be.
When CloudFlare Lies
We decided to take lying in negative answers to its fullest extent. Instead of white lies, we do black lies.
For an NXDOMAIN
, we always return \000
.(the missing name) as the next name, and because we return an NSEC
directly on the missing name, we do not have to return an additional NSEC
for the wildcard. This way we only have to return SOA
, SOA RRSIG
, NSEC
and NSEC RRSIG
, and we do not need to search the database or precompute dynamic answers.
Our negative answers are usually around 300 bytes. For comparison, negative answers for ietf.org
which uses NSEC
and icann.org
, which uses NSEC3
are both slightly over 1000 bytes, three times the size. The reason this matters so much is that the maximum size of an unsigned UDP packet is typically 512 octets. DNSSEC requires support for at least 1220 octets long messages over UDP, but above that limit, the client may need to upgrade to DNS over TCP. A good practice is to keep enough headroom in order to keep response sizes below fragmentation threshold during zone signing key rollover periods.
NSEC
: 1096 bytes
ietf.org. 1799 IN SOA ns0.amsl.com. glen.amsl.com. 1200000317 1800 1800 604800 1800
ietf.org. 1799 IN RRSIG SOA 5 2 1800 20170213210533 20160214200831 40452 ietf.org. P8XoJx+SK5nUZAV/IqiJrsoKtP1c+GXmp3FvEOUZPFn1VwW33242LVrJ GMI5HHjMEX07EzOXZyLnQeEvlf2QLxRIQm1wAnE6W4SUp7TgKUZ7NJHP dgLr2gqKYim4CI7ikYj3vK7NgcaSE5jqIZUm7oFxxYO9/YPz4Mx7COw6 XBOMYS2v8VY3DICeJdZsHJnVKlgl8L7/yqrL8qhkSW1yDo3YtB9cZEjB OVk8uRDxK7aHkEnMRz0LODOJ10AngJpg9LrkZ1CO444RhZGgTbwzN9Vq rDyH47Cn3h8ofEOJtYCJvuX5CCzaZDInBsjq9wNAiNBgIQatPkNriR77 hCEHhQ==
ietf.org. 1799 IN NSEC ietf1._domainkey.ietf.org. A NS SOA MX TXT AAAA RRSIG NSEC DNSKEY SPF
ietf.org. 1799 IN RRSIG NSEC 5 2 1800 20170213210816 20160214200831 40452 ietf.org. B9z/JJs30tkn0DyxVz0zaRlm4HkeNY1TqYmr9rx8rH7kC32PWZ1Fooy6 16qmB33/cvD2wtOCKMnNQPdTG2qUs/RuVxqRPZaQojIVZsy/GYONmlap BptzgOJLP7/HOxgYFgMt5q/91JHfp6Mn0sd218/H86Aa98RCXwUOzZnW bdttjsmbAqONuPQURaGz8ZgGztFmQt5dNeNRaq5Uqdzw738vQjYwppfU 9GSLkT7RCh3kgbNcSaXeuWfFnxG1R2SdlRoDICos+RqdDM+23BHGYkYc /NEBLtjYGxPqYCMe/7lOtWQjtQOkqylAr1r7pSI2NOA9mexa7yTuXH+x o/rzRA==
www.apps.ietf.org. 1799 IN NSEC cloudflare-verify.ietf.org. A RRSIG NSEC
www.apps.ietf.org. 1799 IN RRSIG NSEC 5 4 1800 20170213210614 20160214200831 40452 ietf.org. U+hEHcTps2IC8VKS61rU3MDZq+U0KG4/oJjIHVYbrWufQ7NdMdnY6hCL OmQtsvuZVRQjWHmowRhMj83JMUagxoZuWTg6GuLPin3c7PkRimfBx7jI wjqORwcuvpBh92A/s/2HXBma3PtDZl2UDLy4z7wdO62rbxGU/LX1jTqY FoJJLJfJ/C+ngVMIE/QVneXSJkAjHV96FSEnreF81V62x9azv3AHo4tl qnoYvRDtK+cR072A5smtWMKDfcIr2fI11TAGIyhR55yAiollPDEz5koj BfMstC/JXVURJMM+1vCPjxvwYzTZN8iICf1AupyyR8BNWxgic5yh1ljH 1AuAVQ==
Black Lies: 357 bytes
cloudflare.com. 1799 IN SOA ns3.cloudflare.com. dns.cloudflare.com. 2020742566 10000 2400 604800 3600
blog.cloudflare.com. 3599 IN NSEC \000.blog.cloudflare.com. RRSIG NSEC
cloudflare.com. 1799 IN RRSIG SOA 13 2 86400 20160220230013 20160218210013 35273 cloudflare.com. kgjtJDuuNC/yX8yWQpol4ZUUr8s8yAXZi26KWBI6S3HDtry2t6LnP1ou QK10Ut7DXO/XhyZddRBVj3pIpWYdBQ==
blog.cloudflare.com. 3599 IN RRSIG NSEC 13 3 3600 20160220230013 20160218210013 35273 cloudflare.com. 8BKAAS8EXNJbm8DxEI1OOBba8KaiimIuB47mPlteiZf3sVLGN1edsrXE +q+pHaSHEfYG5mHfCBJrbi6b3EoXOw==
DNS Shotgun
Our take on NODATA
responses is also unique. Traditionally, NODATA
responses contain one NSEC
record to tell the resolver which types exist on the requested name. This is highly inefficient. To do this, we’d have to search the database for all the types that do exist, just to answer that the requested type does not exist. Remember that’s not even always possible because we have dynamic answers that are generated on the fly.
What we realized was that NSEC
is a denial of existence. What matters in NSEC
are the missing types, not the present ones. So what we do is we set all the types. We say, this name does exist, just not on the one type you asked for.
For example, if you asked for an TXT
record of blog.cloudflare.com
we would say, all the types exist, just not TXT
.
blog.cloudflare.com. 3599 IN NSEC \000.blog.cloudflare.com. A WKS HINFO MX AAAA LOC SRV CERT SSHFP IPSECKEY RRSIG NSEC TLSA HIP OPENPGPKEY SPF
And then if you queried for a MX
on blog.cloudflare.com
, we would return saying we have every record type, even TXT
, but just not MX
.
blog.cloudflare.com. 3599 IN NSEC \000.blog.cloudflare.com. A WKS HINFO TXT AAAA LOC SRV CERT SSHFP IPSECKEY RRSIG NSEC TLSA HIP OPENPGPKEY SPF
This saves us a database lookup and from leaking any zone information in negative answers. We call this the DNS Shotgun.
How Are Black Lies and DNS Shotgun Standards Compliant
We put a lot of care to ensure CloudFlare’s negative answers are standards compliant. We’re even pushing for them to become an Internet Standard by publishing an Internet Draft earlier this year.
RFC4470, White Lies, allows us to randomly generate next names in NSEC
. Not setting the second NSEC
for the wildcard subdomain is also allowed, so long as there exists an NSEC
record on the actual queried name. And lastly, our lie of setting every record type in NSEC
records for NODATA
, is okay too –– after all, domains are constantly changing, it’s feasible that the zone file changed in between the time the NSEC
record indicated to you there was no MX
record on blog.cloudflare.com
and when you queried successfully for MX
on blog.cloudflare.com
.
Conclusion
We’re proud of our negative answers. They help us keep packet size small, and CPU consumption low enough for us to provide DNSSEC for free for any domain. Let us know what you think, we’re looking forward to hearing from you.