What a lovely hat

Paper 2016/083

NSEC5 from Elliptic Curves: Provably Preventing DNSSEC Zone Enumeration with Shorter Responses

Sharon Goldberg, Moni Naor, Dimitrios Papadopoulos, and Leonid Reyzin

Abstract

While DNSSEC securely provides authenticity and integrity to the domain name system (DNS), it also creates a new security vulnerability called zone enumeration that allows an adversary that asks a small number of targeted DNS queries to learn the IP addresses of all domain names in a zone. An enumerated zone can be used as ''a source of probable e-mail addresses for spam, or as a key for multiple WHOIS queries to reveal registrant data that many registries may have legal obligations to protect'' [RFC 5155] (e.g., per EU data protection laws), or to create a toehold for more complex attacks. As the Internet of things becomes increasingly ubiquitous, it also becomes increasingly important to keep the names and addresses of these ''things'' (e.g., thermostats, fridges, baby monitors) away from remote attackers. In previous work we solved DNSSEC's zone enumeration problem by introducing NSEC5, a cryptographic construction based on RSA digital signatures. NSEC5 provides authenticated denial of existence, i.e., it is used to answer DNS queries that have negative responses (e.g., NXDOMAIN). RSA-based NSEC5 was recently submitted for specification in an Internet draft [draft-vcelak-nsec5-01], and a working implementation of a nameserver that supports RSA-based NSEC5 is also available [https://github.com/dipapado/nsec5-implementation]. However, recent years have seen the DNSSEC community aiming to replace RSA with elliptic curve cryptography (EC), in order to shorten the length of DNSSEC responses. Therefore, in this paper we present a new variant of NSEC5 that uses elliptic curve cryptography (ECC) to produce shorter NSEC5 responses. If a zone is signed with ECDSA at the 128-bit security level and also uses our new ECC-based NSEC5 scheme, its denial-of-existence responses (response code NXDOMAIN) will be about 2 times shorter than that a zone signed with 2048-bit RSA and RSA-based NSEC5. Moreover, our ECC-based NSEC5 has responses lengths that are comparable to NSEC3, DNSSEC's current authenticated-denial-of-existence mechanism that is vulnerable to zone enumeration via offline dictionary attacks. In fact, if a zone signed with ECDSA at the 128-bit security level also uses our new ECC-based NSEC5 scheme, it will have responses that are shorter than a zone using NSEC3 with 1024-bit RSA and SHA1 (for an 80-bit security level), which is today's dominant deployment configuration.

Note: Slightly changed scheme to shorten the length of NSEC5 proofs. [Now the value c in the NSEC5 proof need only be 128 bits long, rather than 256 bits long.]