Economical With The Truth: Making DNSSEC Answers Cheap

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.

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.

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.

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).

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 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 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.”

• RFC5155

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

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.

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.

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==

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.

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.

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.