Primary-Secondary-Resolvers Membership Proof Systems and their Applications to DNSSEC
Moni Naor
Abstract:
We consider Primary-Secondary-Resolver Membership Proof Systems (PSR for short) that enable a secondary to convince a resolver whether or not a given a element is in a set defined by the primary without revealing more information about the set. The main motivation is studying 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 current DNSSEC (NSEC3) suffers from the problem of zone enumeration: we use cryptographic lower bounds to prove that in a PSR system the secondary must perform non trivial online computation. This implies that the three design goals of DNSSEC --- high performance, security against network attackers, and privacy against zone enumeration --- cannot be satisfied simultaneously.
We provide PSR constructions matching our lower bound and in particular suggest NSEC5, a protocol that solves the problem of DNSSEC zone enumeration while remaining faithful to the operational realities of DNSSEC. The scheme can be seen as a variant of NSEC3, where the hash function is replaced with an RSA based hashing scheme. Other constructions we have are based on the Boneh–Lynn–Shacham signature scheme, Verifiable Random and Unpredictable Functions and Hierarchical Identity Based Encryption.
The talk is based on the papers "NSEC5: Provably Preventing DNSSEC Zone Enumeration" by Sharon Goldberg, Moni Naor, Dimitrios Papadopoulos, Leonid Reyzin, Sachin Vasant and Asaf Ziv and "PSR Membership Proof Systems" by Moni Naor and Asaf Ziv