DNSCurve: Usable security for DNS

Cryptography in DNSCurve

Elliptic-curve cryptography

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

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

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.

Version