International Association
for Cryptologic Research

This paper uses cryptographic techniques to study the problem of zone enumeration in DNSSEC. 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, where an adversary launches a small number of online DNSSEC queries and then uses offline dictionary attacks to learn which domain names are present or absent in a DNS zone. We explain why the current DNSSEC standard (with NSEC and NSEC3) suffers from zone enumeration: we use cryptographic lower bounds to prove that DNSSEC\'s three design goals -high performance, security against network attackers, and privacy against zone enumeration- cannot be satisfied simultaneously. We then introduce NSEC5, a new cryptographic construction that solves the problem of DNSSEC zone enumeration while matching our lower bounds and remaining faithful to the operational realities of DNSSEC. NSEC5 can be thought of as a variant of NSEC3, where the hash function is replaced with an RSA-based keyed-hashing scheme.