example.org.        SOA ( ... )
                    DNSKEY ( ... )
                    NSEC a.example.org. SOA NSEC DNSKEY RRSIG
                    RRSIG(SOA) ( ... )
                    RRSIG(DNSKEY) ( ... )
                    RRSIG(NSEC) ( ... )
a.example.org.      A 192.0.2.1
                    TXT "a record"
                    NSEC d.example.org. A TXT NSEC RRSIG
                    RRSIG(A) ( ... )
                    RRSIG(TXT) ( ... )
                    RRSIG(NSEC) ( ... )
d.example.org.      A 192.0.2.1
                    TXT "d record"
                    NSEC example.org. A TXT NSEC RRSIG
                    RRSIG(A) ( ... )
                    RRSIG(TXT) ( ... )
                    RRSIG(NSEC) ( ... )

The signed and sorted "example.org" zone with the added NSEC records (and signatures). For brevity, the class is not shown (defaults to IN), the NS records are left out and the SOA, DNSKEY and RRSIG records are shortened.

Figure 3

If a DNSSEC aware resolver asks for b.example.org, it gets back a status: NXDOMAIN packet, which by itself is meaningless as the header can be forged. To be able to securely detect that b does not exist, there must also be a signed NSEC record which covers the name space where b lives. The record:

a.example.org.      NSEC d.example.org.

does just do that: b should come after a, but the next owner name is d.example.org, so b does not exist.

Only by making that calculation, is a resolver able to conclude that the name b does not exist. If the signature of the NSEC record is valid, b is proven not to exist. We have: authenticated denial of existence.

Note that a man-in-the-middle may still replay this NXDOMAIN response when you're querying for, say, c.example.org. But it would not do any harm since it is provably the proper response to the query. In the future, there may be data published for c.example.org. Therefore, the RRSIGs RDATA include a validity period (not visible in the zone above), so that an attacker cannot replay this NXDOMAIN response for c.example.org forever.

3.3. NODATA Responses

NSEC records are also used in NODATA responses. In that case we need to look more closely at the type bitmap. The type bitmap in an NSEC record tells which types are defined for a name. If we look at the NSEC record of a.example.org, we see the following types in the bitmap: A, TXT, NSEC and RRSIG. So for the name a this indicates we must have an A, TXT, NSEC and RRSIG record in the zone.

With the type bitmap of the NSEC record, a resolver can establish that a name is there, but the type is not. For example, if a resolver asks for a.example.org AAAA, the reply that comes back is:

;; status: NOERROR, id: 44638

;; AUTHORITY SECTION:
example.org.        SOA ( ... )
example.org.        RRSIG(SOA) ( ... )
a.example.org.      NSEC d.example.org. A TXT NSEC RRSIG
a.example.org.      RRSIG(NSEC) ( ... )

The resolver should check the AUTHORITY section and conclude that:

(1)

a.example.org exists (because of the NSEC with that owner name) and;

(2)

the type (AAAA) does not as it is not listed in the type bitmap.

The techniques used by NSEC, form the basics of authenticated denial of existence in DNSSEC.

3.4. Drawbacks of NSEC

There were two issues with NSEC (and NXT). The first is that it allows for zone walking. NSEC records point from one name to another, in our example: example.org, points to a.example.org which points to d.example.org which points back to example.org. So we can reconstruct the entire example.org zone even when zone transfers (AXFR) on the server are denied.

The second issue is that when a large, delegation heavy, zone deploys DNSSEC, every name in the zone gets an NSEC plus RRSIG. This leads to a huge increase in the zone size (when signed). This would in turn mean that operators of such zones who are deploying DNSSEC, face up front costs. This could hinder DNSSEC adoption.

These two issues eventually lead to NSEC3 which:

• Adds a way to garble the next owner name, thus thwarting zone-walking;
• Makes it possible to skip names for the next owner name. This feature is called opt-out. It means not all names in your zone get an NSEC3 plus ditto signature, making it possible to "grow into" your DNSSEC deployment. Describing opt-out is out of scope for this document. For those interested, opt-out is explained in RFC 4956 [RFC4956], which is curiously titled "(DNSSEC) Opt-In". Later this was incorporated into RFC 5155 [RFC5155].

But before we delve into NSEC3, let us first take a look at its predecessors: NO, NSEC2 and, DNSNR.

3.5. NO, NSEC2 and DNSNR

The NO record was the first to introduce the idea of hashed owner names. It also fixed other shortcomings of the NXT record. At that time (around 2000) zone walking was not considered important enough to warrant the new record. People were also worried that DNSSEC deployment would be hindered by developing an alternate means of denial of existence. Thus the effort was shelved and NXT remained. When the new DNSSEC specification was written, NSEC saw the light and inherited the two issues from NXT.

Several years after that NSEC2 was introduced as a way to solve the two issues of NSEC. The NSEC2 draft contains the following paragraph:

"This document proposes an alternate scheme which hides owner names while permitting authenticated denial of existence of non-existent names. The scheme uses two new RR types: NSEC2 and EXIST."

When an authenticated denial of existence scheme starts to talk about EXIST records, it is worth paying extra attention.

NSEC2 solved the zone walking issue, by hashing (with SHA1 and a salt) the "next owner name" in the record, thereby making it useless for zone walking.

But it did not have opt-out. Although promising, the proposal did not make it because of issues with wildcards and the odd EXIST resource record.

The DNSNR record was another attempt that used hashed names to foil zone walking and it also introduced the concept of opting out (called "Authoritative Only Flag") which limited the use of DNSNR in delegation heavy zones. This proposal didn't make it either, but it provided valuable insights into the problem.

3.6. NSEC3

From the experience gained with NSEC2 and DNSNR, NSEC3 was forged. It incorporates both opt-out and the hashing of names. NSEC3 solves any issues people might have with NSEC, but it introduces some additional complexity.

NSEC3 did not supersede NSEC, they are both defined for DNSSEC. So DNSSEC is blessed with two different means to perform authenticated denial of existence: NSEC and NSEC3. In NSEC3 every name is hashed, including the owner name. This means that NSEC3 chain is sorted in hash order, instead of canonical order. Because the owner names are hashed, the next owner name for example.org is unlikely to be a.example.org. Because the next owner name is hashed, zone walking becomes more difficult.

To make it even more difficult to retrieve the original names, the hashing can be repeated several times each time taking the previous hash as input. To thwart rainbow table attacks, a custom salt is also added. In the NSEC3 for example.org we have hashed the names thrice ([RFC5155], Section 5) and use the salt DEAD. Lets look at typical NSEC3 record:

15BG9L6359F5CH23E34DDUA6N1RIHL9H.example.org. (
   NSEC3 1 0 2 DEAD A6EDKB6V8VL5OL8JNQQLT74QMJ7HEB84
        SOA RRSIG DNSKEY NSEC3PARAM )

On the first line we see the hashed owner name: 15BG9L6359F5CH23E34DDUA6N1RIHL9H.example.org, this is the hashed name of the fully qualified domain name (FQDN) example.org. Note that even though we hashed example.org, the zone's name is added to make it look like a domain name again. In our zone, the basic format is SHA1(FQDN).example.org.

The next hashed owner name A6EDKB6V8VL5OL8JNQQLT74QMJ7HEB84 (line 2) is the hashed version of d.example.org. Note that .example.org is not added to the next hashed owner name, as this name always falls in the current zone.

The "1 0 2 DEAD" section of the NSEC3 states:

• Hash Algorithm = 1 (SHA1, this is the default, no other hash algorithms are currently defined for use in NSEC3);
• Opt Out = 0 (disabled);
• Hash Iterations = 2, this yields three iterations, as a zero value is already one iteration;
• Salt = "DEAD".

At the end we see the type bitmap, which is identical to NSEC's bitmap, that lists the types present at the original owner name. Note that the type NSEC3 is absent from the list in the example above. This is due to the fact that the original owner name (example.org) does not have the NSEC3 type. It only exists for the hashed name.

Names like 1.h.example.org hash to one label in NSEC3, 1.h.example.org becomes: 117GERCPRCJGG8J04EV1NDRK8D1JT14K.example.org when used as an owner name. This is an important observation. By hashing the names you lose the depth of a zone - hashing introduces a flat space of names, as opposed to NSEC.

The domain name used above (1.h.example.org) creates an empty non-terminal. Empty non-terminals are domain names that have no RRs associated with them, and exist only because they have one or more subdomains that do ([RFC5155], Section 1.3). The record:

    1.h.example.org.    TXT "1.h record"

creates two names:

1. 1.h.example.org that has the type: TXT;
2. h.example.org which has no types. This is the empty non-terminal. An empty non-terminal will get an NSEC3 records, but not an NSEC record.

3.7. Loading an NSEC3 Zone

Whenever an authoritative server receives a query for a non-existing record, it has to hash the incoming query name to determine into which interval between two existing hashes it falls. To do that it needs to know the zone's specific NSEC3 parameters (hash iterations and salt).

One way to learn them is to scan the zone during loading for NSEC3 records and glean the NSEC3 parameters from them. However, it would need to make sure that there is at least one complete set of NSEC3 records for the zone using the same parameters. Therefore, it would need to inspect all NSEC3 records.

A more graceful solution was designed. The solution was to create a new record, NSEC3PARAM, which must be placed at the apex of the zone. Its sole role is to provide a single, fixed place where an authoritative name server can directly see the NSEC3 parameters used. If NSEC3 were designed in the early days of DNS (+/- 1984) this information would probably have been put in the SOA record.

3.8. Wildcards in the DNS

So far, we have only talked about denial of existence in negative responses. However, denial of existence may also occur in positive responses, i.e., where the ANSWER section of the response is not empty. This can happen because of wildcards.

Wildcards have been part of the DNS since the first DNS RFCs. They allow to define all names for a certain type in one go. In our example.org zone we could for instance add a wildcard record:

*.example.org.      TXT "wildcard record"

For completeness, our (unsigned) zone now looks like this:

example.org.        SOA ( ... )
*.example.org.      TXT "wildcard record"
a.example.org.      A 192.0.2.1
                    TXT "a record"
d.example.org.      A 192.0.2.1
                    TXT "d record"

;; status: NOERROR, id: 13658

;; ANSWER SECTION:
z.example.org.      TXT "wildcard record"

;; status: NOERROR, id: 51790

;; ANSWER SECTION:
z.example.org.      TXT "wildcard record"
z.example.org.      RRSIG(TXT) ( ... )

;; AUTHORITY SECTION:
d.example.org.      NSEC example.org. A TXT RRSIG NSEC
d.example.org.      RRSIG(NSEC) ( ... )

;; status: NOERROR, id: 31827

;; ANSWER SECTION
a.example.org.      TXT "wildcard record"
a.example.org.      RRSIG(TXT) ( ... )

example.org.        SOA ( ... )
*.example.org.      TXT "wildcard record"
a.example.org.      A 192.0.2.1
                    TXT "a record"
*.a.example.org.    CNAME w.b
*.b.example.org.    CNAME w.c
*.c.example.org.    A 192.0.2.1
d.example.org.      A 192.0.2.1
                    TXT "d record"
w.example.org.      CNAME w.a

;; status: NOERROR, id: 4307

;; ANSWER SECTION:
w.example.org.      CNAME w.a.example.org.
w.example.org.      RRSIG(CNAME) ( ... )
w.a.example.org.    CNAME w.b.example.org.
w.a.example.org.    RRSIG(CNAME) ( ... )
w.b.example.org.    CNAME w.c.example.org.
w.b.example.org.    RRSIG(CNAME) ( ... )
w.c.example.org.    A 192.0.2.1
w.c.example.org.    RRSIG(A) ( ... )

;; AUTHORITY SECTION:
*.a.example.org.    NSEC *.b.example.org. CNAME RRSIG NSEC
*.a.example.org.    RRSIG(NSEC) ( ... )
*.b.example.org.    NSEC *.c.example.org. CNAME RRSIG NSEC
*.b.example.org.    RRSIG(NSEC) ( ... )
*.c.example.org.    NSEC d.example.org. A RRSIG NSEC
*.c.example.org.    RRSIG(NSEC) ( ... )

<asterisk label>.<closest encloser>

example.org.        SOA ( ... )
1.h.example.org.    TXT "1.h record"
3.3.example.org.    TXT "3.3 record"

15BG9L6359F5CH23E34DDUA6N1RIHL9H.example.org. (
 NSEC3 1 0 2 DEAD 1AVVQN74SG75UKFVF25DGCETHGQ638EK SOA 
        RRSIG DNSKEY NSEC3PARAM )

75B9ID679QQOV6LDFHD8OCSHSSSB6JVQ.example.org. (
 NSEC3 1 0 2 DEAD 8555T7QEGAU7PJTKSNBCHG4TD2M0JNPJ TXT
        RRSIG )

1AVVQN74SG75UKFVF25DGCETHGQ638EK.example.org. (
    NSEC3 1 0 2 DEAD 75B9ID679QQOV6LDFHD8OCSHSSSB6JVQ )

                    example.org
                       ** 
                   +-- ** . . . . . . . . . . .
              (1) /  . /\ .                    .
                 /  .  |   .                    .
                |  .   |    .                    .
                v .    |     .                    . 
                **     |      **                  --
  h.example.org ** ----+----> ** 3.example.org    -- 2.example.org
                .     /   (3)  . |                .
                .    /         . | (2)            . 
                .   /          . |                .
                .  /           . v                .
1.h.example.org **            **                  -- 
                ** <--------- ** 3.3.example.org  -- x.2.example.org

example.org.        SOA ( ... )
*.example.org.      TXT "wildcard record"
1.h.example.org.    TXT "1.h record"
3.3.example.org.    TXT "3.3 record"

x.2.example.org.    TXT "wildcard record"

8555T7QEGAU7PJTKSNBCHG4TD2M0JNPJ.example.org. (
    NSEC3 1 0 2 DEAD 15BG9L6359F5CH23E34DDUA6N1RIHL9H TXT RRSIG )