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

Cryptography in DNSCurve

The DNSCurve project adds link-level public-key protection to DNS packets. This page discusses the cryptographic tools used in DNSCurve.

Elliptic-curve cryptography

DNSCurve uses elliptic-curve cryptography, not RSA.

RSA is somewhat older than elliptic-curve cryptography: RSA was introduced in 1977, while elliptic-curve cryptography was introduced in 1985. However, RSA has shown many more weaknesses than elliptic-curve cryptography. RSA's effective security level was dramatically reduced by the linear sieve in the late 1970s, by the quadratic sieve and ECM in the 1980s, and by the number-field sieve in the 1990s. For comparison, a few attacks have been developed against some rare elliptic curves having special algebraic structures, and the amount of computer power available to attackers has predictably increased, but typical elliptic curves require just as much computer power to break today as they required twenty years ago.

IEEE P1363 standardized elliptic-curve cryptography in the late 1990s, including a stringent list of security criteria for elliptic curves. NIST used the IEEE P1363 criteria to select fifteen specific elliptic curves at five different security levels. In 2005, NSA issued a new "Suite B" standard, recommending the NIST elliptic curves (at two specific security levels) for all public-key cryptography and withdrawing previous recommendations of RSA.

Some specific types of elliptic-curve cryptography are patented, but DNSCurve does not use any of those types of elliptic-curve cryptography.

Curve25519

DNSCurve uses a particular elliptic curve, Curve25519, introduced in the following paper: Daniel J. Bernstein, "Curve25519: new Diffie–Hellman speed records," pages 207–228 in Proceedings of PKC 2006, edited by Moti Yung, Yevgeniy Dodis, Aggelos Kiayias, and Tal Malkin, Lecture Notes in Computer Science 3958, Springer, 2006, ISBN 3-540-33851-9.

This elliptic curve follows all of the standard IEEE P1363 security criteria. It also follows new recommendations that achieve "side-channel immunity" and "twist security" while improving speed. What this means is that secure implementations of Curve25519 are considerably simpler and faster than secure implementations of (e.g.) NIST P-256; there are fewer opportunities for implementors to make mistakes that compromise security, and mistakes are more easily caught by reviewers.

An attacker who spends a billion dollars on special-purpose chips to attack Curve25519, using the best attacks available today, has about 1 chance in 1000000000000000000000000000 of breaking Curve25519 after a year of computation. One could achieve similar levels of security with 3000-bit RSA, but encryption and authentication with 3000-bit RSA are not nearly fast enough to handle modern DNS loads and would require much more space in DNS packets.

Two-key communication

All DNSCurve communications are between two public keys. When a DNSCurve cache sends a packet to a DNSCurve server, it encrypts and authenticates the packet from its own public key to the server's public key. Similarly, when the server sends a packet back to the cache, it encrypts and authenticates the packet from the server's public key to the cache's public key.

Specifically, let's say the cache's long-term secret key is c and the server's long-term secret key is s. The cache's long-term public key is then Curve25519(c), and the server's long-term public key is Curve25519(s). The cache and the server both compute a shared secret Curve25519(cs), and then use fast secret-key cryptographic mechanisms to encrypt and authenticate data.

DNSCurve does not use signatures broadcast from one public key. Signatures might seem to be an adequate substitute for two-key protection when confidentiality is not required, and they would allow an important speedup: the server, after computing a signature once, can reuse the signature for any number of clients. However, DNSCurve allows two speedups that turn out to be even more important:

  • The server, after computing the secret shared with a particular cache, can reuse the secret for any number of packets exchanged with that cache.
  • The cache, after computing the secret shared with a particular server, can reuse the secret for any number of packets exchanged with that server.
Computing Curve25519 shared secrets for ten million servers takes under ten minutes of computation on a Core 2 Quad, leaving the rest of the day free for communication with those servers.

Version

This is version 2009.06.26 of the crypto.html web page.