September 16, 2011

The Unreliability of the Domain Name Service

Consider the case of DNS (the Domain Name Service). This innocuous-seeming protocol, which merely translates hostnames (like into IP addresses (like is such an important foundation of the Internet that, without it, humans would have had a serious challenge building and engaging meaningfully with such a vast distributed system. The web as we know it would not exist without DNS. The beauty of DNS is in its simplicity: you ask a question, and you get a response.

But if you can't get a response, then nothing else works -- your web browser can't load up news for you, your email client can't fetch email, and your music player can't download the latest songs. It's important to ensure the DNS system is highly available; counterintuitively, we built it assuming that its components are likely to fail. And from that we can learn how to build other survivable infrastructures.

First, DNS primarily uses UDP, rather than TCP, for transport. UDP (often nicknamed the Unreliable Data Protocol) is more like sending smoke signals than having a conversation; the sender has no idea if their message reached the recipient. A client sends a UDP query to a name server; the name server sends back a UDP answer (had this been implemented in TCP, the conversation would instead have taken several round trips).

Because DNS has no reliability assertion from UDP (and, frankly, the reliability assertion that TCP would have provided isn't worth much, but at least provides failure notification), the implementations had to assume -- correctly -- that failure would happen, and happen regularly. So failure was planned for. If the client does not get a response within a set time window, it will try again - but then the client may query a different server IP address. Because the DNS query/response is accomplished within a single packet, there is no need for server stickiness.

An array of DNS servers can be placed behind a single IP address, with simple stateless load-balancing required - no complex stateful load balancers required (higher end DNS systems can even use IP-anycasting, to have one IP address respond from multiple geographic regions, with no shared state between the sites). Clients can and do learn which servers are highly response, and preferentially use those.

DNS also has built into itself other means of reliability, like the TTL (time to live). This is a setting associated with every DNS response which indicates how long the response is valid. A client therefore does not need to make queries for some time; if a name server fails, a client may not notice for hours.

On top of this failure-prone infrastructure -- an unreliable transport mechanism, servers that might fail at any time, and an Internet that has an unfortunate tendency to lose packets -- a highly survivable system begins to emerge, with total DNS outages a rare occurrence.

May 28, 2010

NSEC3: Is the glass half full or half empty?

NSEC3, or the "Hashed Authenticated Denial of Existence", is a DNSSEC specification to authenticate the NXDOMAIN response in DNS. To understand how we came to create it, and the secrecy issues around it, we have to understand why it was designed. As the industry moves to a rollout of DNSSEC, understanding the security goals of our various Designed Users helps us understand how we might improve on the security in the protocol through our own implementations.

About the Domain Name Service (DNS)

DNS is the protocol which converts mostly readable hostnames, like, into IP addresses (like At its heart, a client (your desktop) is asking a server to provide that conversion. There are a lot of possible positive answers, which hopefully result in your computer finding its destination. But there are also some negative answers. The interesting answer here is the NXDOMAIN response, which tells your client that the hostnames does not exist.

Secrecy in DNS

DNS requests and replies, by design, have no confidentiality: anyone can see any request and response. Further, there is no client authentication: if an answer is available to one client, it is available to all clients. The contents of a zone file (the list of host names in a domain) are rarely publicized, but a DNS server acts as a public oracle for the zone file; anyone can make continuous requests for hostnames until they reverse engineer the contents of the zone file. With one caveat: the attacker will never know that they are done, as there might exist hostname that they have not yet tried.

But that hasn't kept people from putting information that has some form of borderline secrecy into a zone file. Naming conventions in zone files might permit someone to easily map an intranet just looking at the hostnames. Host names might contain names of individuals. So there is a desire to at least keep the zone files from being trivially readable.

DNSSEC and authenticated denials

DNSSEC adds in one bit of security: the response from the server to the client is signed. Since a zone file is (usually) finite, this signing can take place offline: you sign the contents of the zone file whenever you modify them, and then hand out static results. Negative answers are harder: you can't presign them all, and signing is expensive enough that letting an adversary make you do arbitrary signings can lead to DoS attacks. And you have to authenticate denials, or an adversary could poison lookups with long-lived denials.

Along came NSEC. NSEC permitted a denial response to cover an entire range (e.g., there are no hosts between and Unfortunately, this made it trivial to gather the contents of a zone: after you get one range, simply ask for the next alphabetical host ( and learn what the next actual host is ( From a pre-computation standpoint, NSEC was great - there are the same number of NSEC signed responses in a zone as all other signatures - but from a secrecy standpoint, NSEC destroyed what little obscurity existed in DNS.


NSEC3 is the update to NSEC. Instead of providing a range in which there are no hostnames, a DNS server publishes a hashing function, and a signed range in which there are no valid hashes.. This prevents an adversary from easily collecting the contents of the zone (as with NSEC), but does allow them to gather the size of the zone file (by making queries to find all of the unused hash ranges), and then conduct offline guessing at the contents of the zone files (as Dan Bernstein has been doing for a while). Enabling offline guessing makes a significant difference: with traditional DNS, an adversary must send an arbitrarily large number of queries (guesses) to a name server (making them possibly detectable); with NSEC, they must send as many queries as there are records; and with NSEC3, they must also send the same number of requests as there are records (with some computation to make the right guesses), and then can conduct all of their guessing offline.

While NSEC3 is an improvement from NSEC, it still represents a small step down in zone file secrecy. This step is necessary from a defensive perspective, but it makes one wonder if this is the best solution: why do we still have the concept of semi-secret public DNS names? If we have a zone file we want to keep secret, we should authenticate requests before answering. But until then, at least we can make it harder for an adversary to determine the contents of a public zone.

"Best" practices in zone secrecy

If you have a zone whose contents you want to keep obscure anyway, you should consider:
  • Limiting access to the zone, likely by IP address.
  • Use randomly generated record names, to make offline attacks such as Dan Bernstein's more difficult.
  • Fill your zone with spurious answers, to send adversaries on wild goose chases.
  • Instrument your IDS system to detect people trying to walk your zone file, and give them a different answer set than you give to legitimate users.

Jason Bau and John Mitchell, both of Stanford, have an even deeper dive into DNSSEC and NSEC3.

January 4, 2010

Interview at ThreatChaos

Over the holidays, I spent some time on the phone with Richard Stiennon, talking a bit about Akamai and DDoS. The interview is up over at ThreatChaos.

December 21, 2009

Would DNSSEC have helped Twitter?

Twitter had its name servers "stolen". Would DNSSEC have helped protect them? To be brief, no. But looking at why not will help understand the limitations of DNSSEC. It helps to start with the basics of DNS, and DNSSEC.

DNS is broken down into zones. A zone is a hierarchical collections of names, roughly grouped by the periods in the hostname -- e.g., exists under three zones: . (the root zone), .com, and Each zone has a set of servers that are authoritative when answering queries in that zone, and can delegate responsibility for a subsidiary zone to a different set of servers.

With DNSSEC, each zone has a set of keys used to sign answers in the zone; the zone signing key, which signs the records, and the key signing key, which signs the zone signing key. You learn the key signing key for a zone when receiving a delegation; the delegating server adds a special record informing you of the key for the zone they're passing you to.


Looking at the incident, it appears that a compromised Twitter employee email account was used to reset an administrative account login with their registrar, and then that account was used to change the delegation for Had Twitter been using DNSSEC, Twitter would have needed to provide the public half of their key signing key to their registrar. Odds are, that would be in the same interface that was used to redirect An adversary would have been able to alter the DNSSEC delegation just as easily as they altered the zone delegation.

DNSSEC has a lot of strengths, but it isn't a magic bullet for all of the weaknesses in the DNS infrastructure.