DNSCurve: Usable security for DNS


Introduction
DNS users:
Why DNSCurve?
Installing DNSCurve
DNS data managers:
Why DNSCurve?
Installing DNSCurve
DNS implementors:
Caches
Forwarders
Protocol designers:
Cryptography
DNS integration
Attackers:
Forgery
Negative forgery
Replays
Query espionage
Database espionage
+ nsec3walker
CPU flooding
Amplification
+ dnssecamp

DNS database espionage

DNS variantPrivacy-violating speed
Current DNS229 noisy guesses per day, assuming continuous 4Mbps flood of queries to the legitimate servers
DNS+DNSCurve229 noisy guesses per day, assuming continuous 4Mbps flood of queries to the legitimate servers
Current DNSSEC (NSEC3)typically between 240 and 250 secret guesses per day, depending on attacker's computer power
Old DNSSEC (NSEC)instantaneous: server leaks database via NSEC
Ancient DNSSEC (NXT)instantaneous: server leaks database via NXT
Original DNS (DNS+AXFR)instantaneous: server discloses database upon request

The myth of public DNS databases

The original DNS protocol contained a "zone transfer" mechanism ("AXFR") that allowed anyone on the Internet to download the entire DNS database, or selected portions of it. Asking the private.yahoo.com servers for a zone transfer would expose a complete list of subdomains: jennyqsmith.private.yahoo.com, freeranger.private.yahoo.com, etc.

DNS administrators, unhappy with the exposure of information that they want to keep private, began disabling public AXFR. Surveys by the Measurement Factory showed that half of the second-level DNS zones in .com had disabled public AXFR by 2005 and that 70% had disabled it by 2008.

Of course, attackers can guess domain names by trial and error, but this is much slower than seeing a complete list. Flooding a 4-megabit-per-second connection with guesses for an entire day allows only about 229 guesses.

The NXT-walking attack against ancient DNSSEC

The first complete DNSSEC specification, RFC 2065, included a mandatory "NXT" record as part of DNSSEC's protection against negative forgery. For example, upon receiving a request for crackedribs.webmd.com, the webmd.com DNS server (if it had ever installed DNSSEC) would return a signed NXT record saying (essentially) "there are no names between cancer.webmd.com and data.webmd.com".

"NXT walking" is an easy attack against the version of DNSSEC specified in RFC 2065. The attacker asks webmd.com about the 26 names a.webmd.com, b.webmd.com, etc. The server returns various NXT records: for example, in response to d.webmd.com, it returns "there are no names between cancer.webmd.com and data.webmd.com", leaking the existing names cancer.webmd.com and data.webmd.com. The attacker then sends another round of queries, probing any remaining gaps between the leaked names. After a few rounds of queries, consuming not much more traffic than an AXFR request, the attacker knows all of the names within webmd.com.

In other words, by installing DNSSEC, an administrator would be exposing his complete DNS database, even if the administrator had turned off AXFR.

RFC 2065 stated "It is part of the design philosophy of the DNS that the data in it is public and that the DNS gives the same answers to all inquirers" and did not comment on this attack.

The NSEC-walking attack against old DNSSEC

DNSSEC was incompatibly updated in 2005. The revised specification, RFC 4033, stated that "DNS was originally designed with the assumptions that the DNS will return the same answer to any given query regardless of who may have issued the query, and that all data in the DNS is thus visible. Accordingly, DNSSEC is not designed to provide confidentiality, access control lists, or other means of differentiating between inquirers."

RFC 4033 included, and mandated, an "NSEC" record that exposed just as much information as NXT. As before, by installing DNSSEC, an administrator would be exposing his complete DNS database, even if the administrator had turned off AXFR.

RFC 4033 admits that DNSSEC "introduces the ability for a hostile party to enumerate all the names in a zone by following the NSEC chain. NSEC RRs assert which names do not exist in a zone by linking from existing name to existing name along a canonical ordering of all the names within a zone. Thus, an attacker can query these NSEC RRs in sequence to obtain all the names in a zone." Even though this information disclosure is clearly the fault of the DNS server, RFC 4033 claims that "this is not an attack on the DNS itself."

The NSEC3-walking attack against current DNSSEC

DNSSEC was once again incompatibly updated in 2008, replacing NSEC with "NSEC3."

NSEC3 exposes hashes of DNS names in the same way that NSEC exposes the original DNS names. A hash is 150 iterations of SHA-1. Imaginary example: Upon receiving a request for crackedribs.webmd.com, the webmd.com DNS server would return a signed NSEC3 record saying "there are no names whose hashes are between 71f64b7c9418fac530999c3a267f457a and 72461131da8439570e3a2230f7523533."

"NSEC3 walking" is an easy privacy-violating attack against the current version of DNSSEC. After a few rounds of requests to a DNSSEC server, the attacker has collected a list of hashes of existing names. The attacker then guesses a name, hashes the guess, checks whether the hash is in the list, and repeats. This is much, much, much faster than sending a guess through the network: in a single day a low-cost 2.4GHz Core 2 Quad CPU can compute more than 2^41 SHA-1 iterations (using OpenSSL; a tuned implementation would be even faster), enough to check 2^34 guesses. A 100-computer lab can check 2^40 guesses per day. A large company or botnet can check 2^50 guesses per day.

In other words, compared to normal DNS, current DNSSEC (with NSEC3) makes privacy violations thousands of times faster for casual attackers, or millions of times faster for serious attackers. It also makes the privacy violations practically silent: the attackers are guessing names in secret, rather than flooding the legitimate servers with guesses.

NSEC3 is advertised as being much better than NSEC. It's true that NSEC is even worse than NSEC3: "instantaneous" is faster than "2^40 or 2^50 guesses per day". However, NSEC3 is much worse than DNS without DNSSEC.

How does DNSCurve help?

None of these issues arise for DNSCurve. With DNSCurve, negative-answer packets are cryptographically protected in exactly the same way that positive-answer packets are; there are no complications analogous to NXT/NSEC/NSEC3.

Version

This is version 2009.06.24 of the espionage2.html web page.