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 22.214.171.124 cloudflare.com. 299 IN A 126.96.36.199
This is an answer with DNSSEC:
cloudflare.com. 299 IN A 188.8.131.52 cloudflare.com. 299 IN A 184.108.40.206 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 man-in-the-middle 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 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
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
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 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
NSEC record above tells you that
bogus.ietf.org does not exist because no names exist canonically between
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
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
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).
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
ietf.org, you will get back the first name in the zone,
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
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. 21599 IN NSEC aarp. NS DS RRSIG NSEC
aarp. 21599 IN NSEC abb. NS DS RRSIG NSEC
Zone walking was actually considered a feature of the original design:
NXTchains specified in this document enable a resolver to obtain, by successive queries chaining through
NXTs, 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.
CC BY 2.0 image by KIUI
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
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.”
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
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
NSEC record will tell you that while there is no
TXT record on
apps.ietf.org, there are
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.
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
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
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==
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
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
blog.cloudflare.com, we would return saying we have every record type, even
TXT, but just not
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
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.