Is zone enumeration really possible with NSEC3?
Some of the cryptographic machinery used in DNSSEC 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.
To answer this question, we need to distinguish between two separate cases: schemes where all signed response components are pre-computed and the DNSSEC zone-signing key need NOT be stored on the nameserver (e.g., standard NSEC3), and schemes that require online signing and the zone-signing key stored at the nameserver (as specified in RFC's 4470 and 4471, and "NSEC3 White Lies", where NSEC3 responses are constructed and signed online).
With respect to the former (schemes where the responses are precomputed), others have shown efficient zone enumeration attacks. Bernstein showed how to collect all the NSEC3 records in a zone by sending a sufficient number of randomly-generated queries; for a zone of R names, only R queries are necessary. Next, observe that most domain names have a particular structure; thus, given a dictionary which is used for breaking the hashes that form the NSEC3 records, the hash values in the retrieved NSEC3 records can be compared against the hashes of the names in the dictionary to learn which names are present in the zone. In 2014, Wander, Schwittmann, Boelmann and Weiss demonstrated the efficiency of this attack against the .com TLD. Using a $400 AMD GPU for hash breaking, they managed to successfully recover more than 64% of the names in the .com zone, in under 5 days.
With respect to the latter (schemes where responses are computed online), these schemes are NOT vulnerable to zone enumeration attacks. On the other hand, these schemes do require that all nameservers that are authoritative for the zone must store the zone-signing key. This makes the DNSSEC security model weaker: any such nameserver becomes a potential point of failure. That is, compromising any such nameserver completely breaks the security of the zone, and allows an attacker to launch DNS poisoning attacks, create bogus DNSSEC records, etc. This is especially problematic when the secondary nameservers for a zone are operated by an entirely different organization than the one that is authoritative for the zone.
Why do we need NSEC5 to avoid zone enumeration?
NSEC3 with White Lies (RFC 7129) already achieves this.
Yes, it's true that NSEC3 White Lies is NOT vulnerable to zone enumeration attacks.
(NSEC3 White Lies implements authenticated denial of existence by signing, online, the minimal possible pair of hash values that cover a queried name, independently of names existing in the zone. For example, given a query q and its hash value h(q), the nameserver generates and signs the following NSEC3 record online:
However, NSEC3 White Lies falls in the category of schemes that require online signing, since the NSEC3 record depends on the query q and cannot be pre-computed offline. We already discussed the weaknesses of this model above---namely, the fact that nameservers need to be trusted with the secret zone-signing key. A compromise of the nameserver leads to a total compromise of the integrity of the zone. In other word, an attacker that compromises the nameserver can sign bogus DNSSEC responses.
In contrast, NSEC5 provides the same privacy guarantee (it is NOT vulnerable to zone enumeration attacks), but in a stronger security model (the integrity of the zone is not lost even if the nameserver is compromised).
NSEC5 also requires online crypto using the secret NSEC5KEY. Isn't this a security threat?
Online crypto operations with NSEC5 are done with a different type of key ---not the zone-signing key, but rather a different key we call the "NSEC5KEY".
Even an attacker that knows the secret NSEC5KEY cannot forge NSEC5 or any other type of DNSSEC records. Our paper shows that a compromise of this secret NSEC5KEY does not jeopardize the integrity of DNSSEC at all; that is, anyone with access to the secret NSEC5KEY cannot forge NSEC5 or any other type of DNSSEC responses. Our video also explains why this is the case.
However, access to the secret NSEC5KEY does allow for zone enumeration. Thus, if the NSEC5KEY is leaked or compromised, all that happens is that the security of NSEC5 downgrades to that of NSEC3.
Is NSEC5 the only way to eliminate zone enumeration?
In our paper we prove that a DNSSEC scheme that achieves both integrity (i.e., DNSSEC records cannot be forged by a network attacker) and privacy (against zone enumeration, so that the only way to determine whether or not a name is in the zone is to query for that name) requires an online cryptographic signature computation as part of the query response.
NSEC3 with White Lies is an online signing solution that provides integrity against a network attacker and privacy against zone enumeration. However, as we described above, it requires entrusting the nameserver with the secret zone-signing key; thus, any compromise of the nameserver leads to a complete compromise of the zone.
NSEC5 also provides integrity against network attackers and privacy against zone enumeration, but it also provides protection against a compromised nameserver. Even an adversary that learns the secret NSEC5KEY cannot forge NSEC5 or other DNSSEC records.
NSEC5 was the most lightweight crypto construction we could think of that achieves all three of these security goals, while (1) using only a single online signature and (2) using only cryptographic algorithms that are commonly used with DNSSEC. Our companion paper has other crypto constructions that also achieve these three security goals, but NSEC5 is more lightweight than all of the constructions in the companion paper.
Wait, what if we add more salt to the NSEC3 hashes (that is, a different salt for each NSEC3 record)? Won't that prevent zone enumeration?
Salting is used to protect, e.g., password files against dictionary attacks. The idea is that instead of storing the password p, we store salt, h(p,salt) where the salt is a unique random number. A different salt is used for each password.
However , it is not possible to use different salts for different NSEC3 records, unless there exists a full chain of NSEC3 records for each salt. If a different salt is used for each NSEC3 record, a query for a non-existent name might not map to any NSEC3 record. RFC 5155 confirms this: "There MUST be at least one complete set of NSEC3 RRs for the zone using the same salt value."
In order to truly make zone enumeration harder, there must be one complete NSEC3 chain per different salt. Thus, the nameserver can randomly choose the NSEC3 record to include in a response, out of all the covering ones (each from a different NSEC3 chain with a difference salt). For the attacker, this means that if there exist K separate NSEC3 chains in the zone, recovering a complete NSEC3 chain will take on average K*R DNS queries.
This does make zone enumeration harder but it only provides a linear benefit/cost trade-off --- the nameserver must setup and store K times more records to make the attack K times harder for the attacker, which is not a favorable trade-off. Compare, for example, usual cryptographic schemes where increasing the key-length by one bit makes the attack twice as costly.
What if we stick to NSEC3 and somehow add randomized records? Wouldn't this make zone enumeration hard?
There are various ways to achieve something like this.
We could introduce a number of random values from the hash function range and then use these random values together with the hashes of the names in the zone to compute the NSEC3 chain. This effectively makes the chain larger and the returned NSEC3 record for a given query may contain one or two entirely random values as its boundaries (instead of the hashes of names from the zone).
Alternatively, we may add some amount of (parametrized) noise around existing NSEC3 hash values (conceptually similar to a pre-computed version of NSEC3 White Lies, but with noise around the existing hash values instead of the queried name). The basic idea here is that, assuming the noise is relatively small, it will be hard for the adversary to "hit" the NSEC3 records that have actual hashed names as boundaries.
However, in this technical report we present efficient attacks against both of these schemes, and demonstrates that they also only provide a linear benefit/cost trade-off for the nameservers.
This is not surprising, since in our paper we show that a DNSSEC scheme that achieves both integrity (i.e., DNSSEC records cannot be forged by a network attacker) and privacy (against zone enumeration, so that the only way to determine whether or not a name is in the zone is to query that nameserver for that name) requires an online cryptographic signature computation as part of the query response. Thus, any offline variant of NSEC3 that uses only hashing (including the two schemes mentioned above) will still be vulnerable to zone enumeration attacks.
What is the response size of NSEC5 as compared with NSEC3?
Well, we now have two version of NSEC5: one based on elliptic curves (the NIST P-256 curve, or Curve25519), and the other based on RSA. Put simply, NSEC5 from elliptic curves provides the shorter responses of all our NSEC5 constructions. Using a 256-bit elliptic curve (which provides a security level approximately like 3072-bit RSA), NSEC5 from elliptic curves (ECC) produces responses that are even shorter than today's dominant deployment configuration of NSEC3 signed with 1024-bit RSA. ECC-based NSEC5 responses are also only 11% longer than NSEC3 signed with ECDSA!
For precise measurements of NSEC5 response lengths, see the performance evaluation from our latest NSEC5 paper.
What about computation time? How does NSEC5 compare to NSEC3?
NSEC and NSEC3 are the most efficient authenticated denial mechanisms, in terms of computation for authoritative server and resolver. NSEC also has the shortest response lengths. However, these mechanisms do not prevent zone enumeration.
Regarding mechanisms that do prevent zone enumeration, NSEC5 should be examined in contrast with NSEC3 White Lies [RFC7129]. 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 supports NSEC3 White Lies (ie PowerDNS). 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).
What exactly is this RSA-style hash function that NSEC5 uses?
Assuming a 2048 bit RSA modulo N, to compute the hash of a name x the nameserver first uses full-domain-hash MGF with 2047 bits (as specified in RFC 2437) to compute:
What about the elliptic curve hash function that ECC-based NSEC5 uses?
We adapt the Chaum-Pederson (CP) protocol from CRYPTO'92, for
proving that two cyclic group elements have the same discrete logarithm. For a full description of the scheme, see
Section 4.1 of ourECC-based NSEC5 paper. A specification for
implementors is available in the NSEC5 internet draft.
Do you have any working code?
Yes! An RSA-based NSEC5-ready nameserver based on the KNOT DNS software is available on
(github). Prototypes of all
the crypto used in NSEC5 and specified in the NSEC5 internet draft
is available here.
Whatever happened to NSEC4?
NSEC4 was suggested by Gieben and Mekking in this Internet draft that was not standardized. It proposed the introduction of a Wildcard flag and an Opt-out mechanism for NSEC. These are pretty nice optimizations; if we use their Wildcard flag optimization with NSEC5, we can save significantly on space and computation. These optimizations are adopted as part of NSEC5.
See also this.
I'm interested in implementing NSEC5 in my resolver/nameserver.
Fabulous. Please get in touch with one of our team, we would love to work with you.
OK. Sounds good. Anything else?
Yes. Check out these awesome NSEC5 memes!