Authenticated Denial of Existence with NSEC and NSEC3

Signing a positive answer is straightforward: the RRset is present, so a signature over it proves the answer was not altered. Signing an absence is harder, because there is nothing to sign. The protocol’s solution is to sign a statement about what surrounds the missing name, namely that the next name after this point in the zone’s ordering is a particular one, and to make the ordering itself deterministic so that the statement can be checked by a third party.

The canonical ordering is the proof

Every signed zone is sorted by owner name in canonical DNS name order: compare labels from the rightmost inward, and within a label compare octets as lowercase, with shorter labels sorting before longer ones when one is a prefix of the other. This produces a total order over the zone’s names, and each name therefore has a predecessor and a successor.

An NSEC record carries the name that follows it in canonical order and the set of types present at its owner. If a queried name sorts between the owner and the next name, the name is absent, unless that next name is a descendant of the query, in which case the queried name exists only as an empty non-terminal. If the queried name equals the owner and the type bitmap lacks the queried type, the name exists but that type does not. The ordinary interval result is an NXDOMAIN proof. The bitmap result is a NODATA proof for an existing name, and the descendant relation is a NODATA proof for an empty non-terminal. A complete NXDOMAIN answer also has to rule out a wildcard that could have synthesised an answer, which takes an NSEC covering the wildcard’s owner name; the same record often serves both purposes.

alpha.example.org.   3600 IN NSEC  delta.example.org. A RRSIG NSEC
delta.example.org.   3600 IN NSEC  mike.example.org.  A MX RRSIG NSEC
mike.example.org.    3600 IN NSEC  zulu.example.org.  A RRSIG NSEC
zulu.example.org.    3600 IN NSEC  example.org.      A RRSIG NSEC

A query for bravo.example.org returns the first NSEC: bravo sorts after alpha and before delta, so the interval covers it and the name does not exist. A query for delta.example.org with type TXT returns the second NSEC, whose bitmap lacks TXT, so the type does not exist. Both responses carry the NSEC record and its RRSIG, and a validator checks the signature, then checks the ordering claim itself. The ordering check is arithmetic on names, not a lookup, which is what makes the proof verifiable without trusting the server.

The interval logic has to handle the last name in the zone, whose next-name field points back to the apex. The apex is first in canonical order because a name sorts before its descendants, and the wrap at the end of the chain follows from that ordering rather than creating it.

Why NSEC leaks the inventory

The NSEC chain enumerates every name in the zone in order. An attacker who can request the NSEC at any name can walk the chain one record at a time and recover the complete list of names. Each response gives the next name, and the walk continues until the chain returns to its start.

The cost of the walk is one query per name, which is slow for a large zone but entirely feasible for a zone of a few thousand names, and it is not a bug in any implementation: it follows directly from the record’s purpose. A proof that a name is absent must reveal its neighbours, because the neighbours are what makes the absence checkable. There is no way to prove “nothing exists between A and C” without naming A and C.

RFC 4470 defines minimally covering NSEC records, generated on the fly so that the interval covers only the queried name. That removes the next-name pointer a walk would follow, which is what makes the technique a defence against enumeration rather than merely a reduction in what each answer reveals. Online signing also removes the ability to serve the zone from a static signed file, which changes the operational model considerably.

The exposure matters because a zone’s name list is often sensitive: internal hostnames, staging environments, customer-specific subdomains. It is the reason NSEC3 exists.

NSEC3 hashes the names but keeps the ordering

NSEC3 replaces the owner name and next-name fields with hashes. The record’s owner is the hash of a name, and its next-hashed field is the hash of the next name in hash order, not in name order. The zone is sorted by hash, which is a different order from the name order and reveals nothing about adjacency in the namespace.

The record carries a hash algorithm (1 is SHA-1), a flags octet, an iteration count, and a salt. The hash is computed over the name in canonical form, concatenated with the salt, and iterated the specified number of times. A non-empty salt changes the hash of every name in the zone, but because the hashed input is the fully qualified name, a table computed for one zone does not apply to another even with an empty salt.

A NODATA proof for an existing name with NSEC3 requires the NSEC3 record whose owner hash matches the query name’s hash; an empty non-terminal needs the closest-encloser proof instead. A NXDOMAIN proof requires up to three records: the NSEC3 matching the closest encloser, the NSEC3 covering the next closer name, and the NSEC3 proving that the wildcard at the closest encloser does not exist. That three-record structure is what makes NSEC3 negative responses large.

The closest encloser is the longest existing ancestor of the query name. The next closer name is that ancestor plus one more label. An NXDOMAIN must show that the next closer name does not exist, because if it did exist, the query name might exist beneath it. And it must show that no wildcard covers the query, because a wildcard at the closest encloser would have synthesised an answer. Each of those claims needs its own matching or covering NSEC3, and each NSEC3 needs a signature.

Iterations, salt, and the cost that lands on resolvers

The iteration count exists to make offline dictionary attacks on hashed names more expensive. Each iteration is an extra hash computation, so an attacker who wants to test a candidate name must perform the full iteration chain, while the zone owner performs it once per name at signing time.

The cost is not borne only by the attacker. Every validator that receives an NSEC3 must perform the same iteration chain for each proof it checks, and it must do so for every negative answer it validates. A zone with a high iteration count therefore imposes that work on every validating resolver in the world, on every miss. The relationship is inverted from the usual security trade: the party paying is not the party choosing the parameter.

The practical consequence is that RFC 9276 now requires an iteration count of zero and recommends an empty salt: the resolver-side cost and the extra exposure to CPU exhaustion outweigh any dictionary resistance that further hashing buys. A salt earns little either: because the hashed name is already specific to one zone, an attacker must build a dictionary per zone in any case, and a constant salt adds nothing to that cost. Only a salt that changes during an attack would help, and changing it means rebuilding the entire chain.

import base64, hashlib

def nsec3_hash(wire_name: bytes, salt: bytes, iterations: int) -> str:
    """RFC 5155: H(name | salt), then H(previous | salt) per iteration."""
    h = hashlib.sha1(wire_name + salt).digest()
    for _ in range(iterations):
        h = hashlib.sha1(h + salt).digest()
    return base64.b32hexencode(h).decode("ascii").lower().rstrip("=")

Base32hex is the encoding the record uses, and it is chosen so that the resulting strings sort in the same order as the raw hashes, a property plain base32 does not have. That is why the zone’s NSEC3 records can be ordered by their owner names and still produce a valid hash-order chain.

Opt-out and the unsigned-delegation shortcut

An NSEC3 record with the opt-out flag set means the interval it covers may contain unsigned delegations. A validator that accepts an opt-out proof concludes that the name in question either does not exist or exists as an insecure delegation, and it cannot tell which.

The purpose is to avoid creating NSEC3 records for every unsigned delegation in a large zone. A TLD with millions of unsigned child zones would otherwise need an NSEC3 for each one, which is a large amount of signing work and a large zone. With opt-out, unsigned delegations are covered by the intervals between signed names, and the zone stays manageable.

The security cost is that an attacker who strips a DS record from a referral can rely on an opt-out interval to cover the resulting gap, so the downgrade is indistinguishable from a legitimate unsigned delegation. There is no validation rule that separates the two: the flag means the interval may cover unsigned delegations, and a validator cannot tell which names those were. Opt-out is therefore a deliberate acceptance of weaker denial for the delegations it covers, and RFC 9276 advises against using it in small zones, where the saving is negligible.

The size trade is real in both directions. NSEC3 records are larger than NSEC records because of the hash, the salt, and the iteration fields, and a NXDOMAIN proof needs three of them. A signed negative answer that fits comfortably with NSEC can exceed a 512-octet UDP response with NSEC3, which forces a TCP retry and adds a round trip to every miss. That interaction with the size limits described in EDNS(0) and the Truncation Boundary is the reason aggressive negative caching and NSEC3 parameter choices are usually tuned together.

The white lies compromise

A zone that signs on the fly can generate a denial proof for exactly the name queried, with an interval covering only that name. This is the minimally covering NSEC approach, and it means an enumeration walk gets one narrow interval per query rather than a pointer to the next real name. The proof is still valid, since the interval genuinely covers the name and the signature is genuine, but it reveals far less.

The cost is that every negative answer requires a signature computation at answer time, which puts a private key on the answering host and removes the ability to serve a pre-signed zone from a static file. It also makes the response non-deterministic, so caches hold many distinct proofs for the same absence, and a resolver that caches them all uses more memory than it would for a single chain record.

The alternative for zones that cannot sign online is to precompute a chain and accept the enumeration exposure, or to use NSEC3 with the zero iterations and empty salt that RFC 9276 recommends. Neither removes the fundamental tension: a proof of absence must describe the neighbourhood of the missing name, and any description of the neighbourhood is information about the zone.

The tension is the same one that runs through the rest of the protocol. Delegation exposes the shape of the tree to anyone who asks, as described in Delegation and Zone Cuts, and authenticated denial exposes the contents of a zone to anyone who can walk it. The mechanisms that limit that exposure, among them query minimisation, encrypted transports, and narrow intervals, all trade query count or computation for information hiding, and none of them makes the information disappear.