NSEC5: Provably Preventing DNSSEC Zone Enumeration

Abstract:     DNSSEC is designed to prevent network attackers from tampering with domain name system (DNS) messages. The cryptographic machinery used in DNSSEC, however, also creates a new vulnerability, zone enumeration, enabling an adversary to use a small number of online DNSSEC queries combined with offline dictionary attacks to learn which domain names are present or absent in a DNS zone. In [1], we prove that the design underlying current DNSSEC standard, with NSEC and NSEC3 records, inherently suffers from zone enumeration: specifically, we show that security against network attackers and privacy against zone enumeration cannot be satisfied simultaneously unless the DNSSEC server performs online public-key cryptographic operations.

We then propose NSEC5, a new cryptographic construction that solves the problem of DNSSEC zone enumeration while remaining faithful to the operational realities of DNSSEC. NSEC5 can be thought of as a variant of NSEC3 in which the unkeyed hash function is replaced with an keyed hashing scheme. In [1] we present the original RSA-based version of NSEC5, and in [2] we present more performant version of NSEC5 based on elliptic curve cryptography (ECC). We show in [2] that our ECC-based NSEC5 can be viable even for high-throughput scenarios. Throughput at our authoritative nameserver implementation easily scales to a few tens of thousands of queries per second (64K query/second) on a moderately-sized multi-core server (i.e., 24 threads on 40 virtual cores). In fact, our ECC-based NSEC5 nameserver implementation achieves a throughput that is about 2x higher than the only widely-deployed nameserver implementation that prevents zone enumeration and is compliant with the DNSSEC standards (i.e., PowerDNS's implementation of online signing via NSEC3 White Lies). Our ECC-based NSEC5 responses easily fit into a single IP packet, and have lengths that are comparable to ECC versions of the current DNSSEC protocol (i.e., NSEC3 with ECDSA signatures).

NSEC5 that has been specified in the Internet draft [3], implemented, and its performance has been evaluated [3]. The crypto behind NSEC5 is prototyped here. Shortly, we plan to release our full implementation of an authoritative nameserver and recursive resolver that support both RSA- and ECC-based NSEC5. (For the nameserver implementation, we extend the Knot DNS 1.6. For the recursive resolver, we extend Unbound 1.5.9.)

Video:    An updated view of the NSEC5 project, January 2017 (YouTube)             The original video introducing NSEC5 (YouTube)
FAQ:   Frequently Asked Questions


  1. NSEC5: Provably Preventing DNSSEC Zone Enumeration
    Sharon Goldberg, Moni Naor, Dimitrios Papadopoulos, Leonid Reyzin, Sachin Vasant, Asaf Ziv
    NDSS'15, San Diego, CA. February 2015. (The original NSEC5 paper, presenting RSA-based NSEC5.)
    ePrint (Cryptology) Report (2014/582).     (Alternatively, see this short overview.)

  2. Can NSEC5 be Practical for DNSSEC Deployments?
    Dimitrios Papadopoulos, Duane Wessels, Shumon Huque, Jan Včelák, Moni Naor, Leonid Reyzin, Sharon Goldberg,
    (NSEC5 based on both RSA and ECC, optimized, implemented, and evaluated.)
    ePrint (Cryptology) Report (2017/099).     (February, 2017.)

  3. draft-vcelak-nsec5-03: NSEC5, DNSSEC Authenticated Denial of Existence
    Jan Včelák, Sharon Goldberg, Dimitrios Papadopoulos.
    IETF Internet Draft. First version March 2015, last updated September 2016.
    IETF draft.     work-in-progress version.    

  4. Primary-Secondary-Resolver Membership Proof Systems
    Moni Naor, Asaf Ziv.
    TCC'15. Warsaw, Poland. March 2015.
    ePrint Cryptology Report (2014/905). (A companion to the NSEC5 paper with alternative constructions.)

  5. NSEC5 from Elliptic Curves: Provably Preventing DNSSEC Zone Enumeration with Shorter Responses
    Sharon Goldberg, Moni Naor, Dimitrios Papadopoulos, Leonid Reyzin
    (Technical report detailing the cryptographic construction behind ECC-based NSEC5.)
    ePrint (Cryptology) report 2016/083, January 2016.

  6. Stretching NSEC3 to the Limit: Efficient Zone Enumeration Attacks on NSEC3 Variants
    Sharon Goldberg, Moni Naor, Dimitrios Papadopoulos, Leonid Reyzin, Sachin Vasant, Asaf Ziv
    Technical report. (Discusses zone enumeration attacks on variants of NSEC3 that do not use online signing.)

  NSEC5 at NDSS'17 DNS Privacy Workshop (.pdf) (Sharon Goldberg, 2/2017)
  NSEC5 at DNS-OARC Fall'14 Workshop (.ppsx) (Sharon Goldberg, 10/2014)
  NSEC5 at NDSS'15 (.pdf) (Asaf Ziv, 02/2015)
  NSEC5 at IETF'92 (.pdf) (Jan Včelák, 03/2015)
  Primary-Secondary-Resolver Systems at CANS'14 (.pptx) (Moni Naor, 10/2014)
  Primary-Secondary-Resolver Systems at TCC'15 (.pptx) (Asaf Ziv, 3/2015)

Team: (in alphabetical order)

This material is based upon work supported by the US National Science Foundation under Grants 017907, 1347525, 1012798, and 1012910, a gift from Verisign Labs, the Israel Science Foundation , BSF and IMOS, and from the I-CORE Program of the Planning and Budgeting Committee and the Israel Science Foundation. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the sponsors.

Last updated February 24, 2017.