Subject: [DNSOP] How does NSEC record(s) prove the Name Error?

From: Joey Deng <[email-masked]>
Date: Tue, 26 Oct 2021 22:21:29 -0700

Hi Folks,

I have a very basic question about NSEC record in DNSSEC validation:

How does NSEC record(s) prove the Name Error?

In [RFC 4035 5.4. Authenticated Denial of Existence](https://datatracker.ietf.org/doc/html/rfc4035#section-5.4), it says:

>    o  If the requested RR name matches the owner name of an
>       authenticated NSEC RR, then the NSEC RR's type bit map field lists
>       all RR types present at that owner name, and a resolver can prove
>       that the requested RR type does not exist by checking for the RR
>       type in the bit map.  If the number of labels in an authenticated
>       NSEC RR's owner name equals the Labels field of the covering RRSIG
>       RR, then the existence of the NSEC RR proves that wildcard
>       expansion could not have been used to match the request.
> 
>    o  If the requested RR name would appear after an authenticated NSEC
>       RR's owner name and before the name listed in that NSEC RR's Next
>       Domain Name field according to the canonical DNS name order
>       defined in [RFC4034 <https://datatracker.ietf.org/doc/html/rfc4034>], then no RRsets with the requested name exist
>       in the zone.  However, it is possible that a wildcard could be
>       used to match the requested RR owner name and type, so proving
>       that the requested RRset does not exist also requires proving that
>       no possible wildcard RRset exists that could have been used to
>       generate a positive response.
> 

I can understand the first point, because it is an exact name matching. However, what makes me feel confused is the second one:

If the question name appears in-between the current owner name and the next owner name of the NSEC record, which means that there is no exact name matching:
We should prove that
> no possible wildcard RRset exists that could have been used to generate a positive response.

But it does not describe how to prove it,

What are possible wildcard RRsets for a given name?

My understanding about possible wildcard RRsets for a given name are all the possible sources of synthesis.
For example, the possible wildcard RRsets that can be used to answer question wwww.ietf.org <http://wwwwww.ietf.org/> AAAA are:
*.ietf.org <http://ietf.org/>
*.org
* (but I think root can never be a wildcard, so this is impossible)

Is my understanding correct?

————————————————————————————————————————————————————————————————————————

For example, if I send a DNS query for wwww.ietf.org <http://wwwwww.ietf.org/> with DO/CD bit set, there will be two NSEC records returned:

```
$ dig "wwww.ietf.org" AAAA +dnssec +cdflag +tcp @1.1.1.1

; <<>> DiG 9.10.6 <<>> wwww.ietf.org AAAA +dnssec +cdflag +tcp @1.1.1.1
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NXDOMAIN, id: 34013
;; flags: qr rd ra ad; QUERY: 1, ANSWER: 0, AUTHORITY: 6, ADDITIONAL: 1

;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags: do; udp: 1232
;; QUESTION SECTION:
;wwww.ietf.org.			IN	AAAA

;; AUTHORITY SECTION:
ietf.org.		1800	IN	SOA	ns0.amsl.com. glen.amsl.com. 1200000537 1800 1800 604800 1800
ietf.org.		1800	IN	RRSIG	SOA 5 2 1800 20221019014909 20211019005139 40452 ietf.org. GUaWdfXoPWOjb+/1w5Dtn8VoeemBYXdDIQui365JuuIBkEC4YKFLb+m+ u8YJ+cbnTzDb768HkTX8AbWaupZVR2FLn2r06hf6YruVi5jRjzExYLQ6 22Rn8TCvNpNRBZ7fyEcBd9m3aacGr+2iBXgYL9QRXag0tSAAW5oxjI8H CcQLLylwGKDvQv2sNIQLxZlkYFXa+swBOuFQdT8MmymOKjV1d+p3s+S0 1HdUb7JAR2vTK/UVib5zfyXGiQcpD6F3XOQNVTY2dgc2ywAqoudANVmz Rm9rql12MALn2hu5HwrfC0djzXxo6Ry8I0KLmRtAsDoz4ie95Oh1Bnt4 qUhJLA==
wwwtest.ietf.org.	1800	IN	NSEC	xml2rfc.ietf.org. CNAME RRSIG NSEC
wwwtest.ietf.org.	1800	IN	RRSIG	NSEC 5 3 1800 20221019015021 20211019005139 40452 ietf.org. regwKawm6O9BAaHVyBICHjPlGiwDWoXO8OaqH4zJOOgAglrAMXajbEmx XHJsbq3DVEVGkU8NSQJxmGYjklyKzmMbIBpt7+RaXKT7WIGd/zRjSlnI gWSztB6gWTMQq98vQKeFgrt5X8a10p6C36gtJh5sGFq8FpiAvKoKuGO8 tyWKxux7pEQhlhTySr7ipRe8qmGDpy4H+8bkGqvJ7UJ0f3A366bZyD2Q XLdTG4DUrNWt8wKK0FiL2851PegU8FdQb0IXOlBHNF6qXiKCIhBLbK4W 3O3UYKsNLhYPBYuWNGZQ2mlEsfgUC9ddBU1trmMEObm3E+1tR/jemSYA uF+S7Q==
ietf.org.		1800	IN	NSEC	_dmarc.ietf.org. A NS SOA MX TXT AAAA RRSIG NSEC DNSKEY SPF
ietf.org.		1800	IN	RRSIG	NSEC 5 2 1800 20221019015032 20211019005139 40452 ietf.org. PiCNEGBSBbC/ALNR5ebDwk1wQGMH/l6MtV5ZAGYl9M1wf43NrqHapDlU AP2E07FsPIyo9PcWui67PidLgVA4e0rRJbyHK2B92tEeprZbxSOCeIFi NWiLl1oCZt+IQCCnFlzJkbwk2MWOVRYxUdQfmWk0QZZZtRr1c/i4VwPU MAVqCORkGpc6W6LLiTITLphe7X0NHb7e41n8J06tPh1a6GmRYRJCy41c F26Bf6GcEJBpNTvlNuirimbhvjL4Ax+FHBe5MA/Tjp4K1AeUIA0ibBVI 20o14zUqSsph67/Snz9fdpJ/dsvP9QwTNLTKR6Jxofi/ArWEBEheXsm+ pkZTRA== 
```

The two returned NSEC records are:
wwwtest.ietf.org. -> xml2rfc.ietf.org.
ietf.org. -> _dmarc.ietf.org.

If we follow the steps described by [RFC 4035 5.4. Authenticated Denial of Existence](https://datatracker.ietf.org/doc/html/rfc4035#section-5.4), we will find that:

wwwtest.ietf.org. -> xml2rfc.ietf.org. tells us that the exact name match for wwww.ietf.org does not exist, since it appears in-between the two names. Therefore, the remaining ietf.org. -> _dmarc.ietf.org. NSEC should be used to prove that “no possible wildcard RRset exists that could have been used to generate a positive response” for the name wwww.ietf.org <http://wwww.ietf.org/>.

Therefore, my question is:
How can ietf.org. -> _dmarc.ietf.org NSEC be used to prove that there is no wildcard record for the name wwww.ietf.org? Do we need to prove that all the possible sources of synthesis for wwww.ietf.org <http://wwww.ietf.org/> appear in-between ietf.org. and _dmarc.ietf.org <http://dmarc.ietf.org/>?

Or do we only need to prove that *.ietf.org <http://ietf.org/> appears in-between ietf.org. and _dmarc.ietf.org <http://dmarc.ietf.org/>? If so why do we choose *.ietf.org <http://ietf.org/> instead of *.org or *?

Thanks.

--
Joey Deng

---

From: Mark Andrews <[email-masked]>
Date: Wed, 27 Oct 2021 17:25:02 +1100

For a given QNAME there is exactly one possible wild card name it can match depending
on all the other names that exist.  See the rules for when a QNAME matches a wildcard.

NXDOMAIN proves that a QNAME does not exist.  The NSEC record that proves that a QNAME
does not exist also proves the closest encloser name.  It is this name to which you
prepend the * label and it is that name that you prove does not exist.  Similarly for
NSEC3 except that the closest provable encloser may or may not be the NSEC3 record
that proves the QNAME does not exist.

An NSEC NXDOMAIN proof has 1 or 2 NSEC records.  A given record can prove multiple things.

An NSEC3 NXDOMAIN proof has 1, 2, or 3 NSEC3 records. A given record can prove multiple things.

Mark

> On 27 Oct 2021, at 16:21, Joey Deng <qiaoyu_deng=[email-masked]> wrote:
> 
> Hi Folks,
> 
>>       defined in [
>> RFC4034
>> ], then no RRsets with the requested name exist
> For example, the possible wildcard RRsets that can be used to answer question wwww.ietf.org AAAA are:
> *.ietf.org
> *.org
> For example, if I send a DNS query for wwww.ietf.org with DO/CD bit set, there will be two NSEC records returned:
> 
> ```
> wwwtest.ietf.org. -> xml2rfc.ietf.org. tells us that the exact name match for wwww.ietf.org does not exist, since it appears in-between the two names. Therefore, the remaining ietf.org. -> _dmarc.ietf.org. NSEC should be used to prove that “no possible wildcard RRset exists that could have been used to generate a positive response” for the name wwww.ietf.org.
> 
> How can ietf.org. -> _dmarc.ietf.org NSEC be used to prove that there is no wildcard record for the name wwww.ietf.org? Do we need to prove that all the possible sources of synthesis for wwww.ietf.org appear in-between ietf.org. and _dmarc.ietf.org?

wwwtest.ietf.org. -> xml2rfc.ietf.org proves that the closest encloser is ietf.org.  The corresponding wildcard name
is *.ietf.org. ietf.org. -> _dmarc.ietf.org proves that *.ietf.org does not exist.

> Or do we only need to prove that *.ietf.org appears in-between ietf.org. and _dmarc.ietf.org? If so why do we choose *.ietf.org instead of *.org or *?
> 
> Thanks.
> 
> --
> Joey Deng
> 
> 
> 
> _______________________________________________
> DNSOP mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/dnsop

-- 
Mark Andrews, ISC
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742              INTERNET: [email-masked]

---

From: Mark Andrews <[email-masked]>
Date: Wed, 27 Oct 2021 17:37:58 +1100

> On 27 Oct 2021, at 17:25, Mark Andrews <[email-masked]> wrote:
> 

ietf.org is the longest sequence of labels that is in common between wwww.ietf.org and wwwtest.ietf.org giving ietf.org and between wwww.ietf.org and xml2rfc.ietf.org giving ietf.org (the same as the first comparison).  You need to check both names of the NSEC record as the longest match could come from either name.

---

From: Matthijs Mekking <[email-masked]>
Date: Wed, 27 Oct 2021 08:46:38 +0200

Hi,

The short answer is "find the closest encloser and determine the source
of synthesis.

I can recommend reading RFC 4592 "The Role of Wildcards in the Domain
Name System" to understand better how wildcards work.

I can recommend reading RFC 7129 "Authenticated Denial of Existence in
the DNS" to understand how NSEC proofs work.

On 10/27/21 7:21 AM, Joey Deng wrote:
> In [RFC 4035 5.4. Authenticated Denial of
> Existence](https://datatracker.ietf.org/doc/html/rfc4035#section-5.4
> <https://datatracker.ietf.org/doc/html/rfc4035#section-5.4>), it says:
> 
> I can understand the first point, because it is an exact name matching.
> However, what makes me feel confused is the second one:
> 
> If the question name appears in-between the current owner name and the
> next owner name of the NSEC record, which means that there is no exact
> name matching:
> We should prove that

For a given name, find the closest encloser and calculate the source of
synthesis: *.<closest encloser>. The resource records for the source of
synthesis in the zone give you the possible wildcard RRsets.

> For example, the possible wildcard RRsets that can be used to answer
> question wwww.ietf.org <http://wwwwww.ietf.org> AAAA are:
> *.ietf.org <http://ietf.org>
> *.org

No, in this example it can only answer for *.ietf.org, as "ietf.org" is
the closest encloser for "www.ietf.org".

> For example, if I send a DNS query for wwww.ietf.org
> <http://wwwwww.ietf.org> with DO/CD bit set, there will be two NSEC
> records returned:
...
> wwwtest.ietf.org <http://wwwtest.ietf.org>. -> xml2rfc.ietf.org
> <http://xml2rfc.ietf.org>.
> ietf.org <http://ietf.org>. -> _dmarc.ietf.org <http://dmarc.ietf.org>.
> 
> If we follow the steps described by [RFC 4035 5.4. Authenticated Denial
> of Existence](https://datatracker.ietf.org/doc/html/rfc4035#section-5.4
> <https://datatracker.ietf.org/doc/html/rfc4035#section-5.4>), we will
> find that:
> 
> wwwtest.ietf.org <http://wwwtest.ietf.org>. -> xml2rfc.ietf.org
> <http://xml2rfc.ietf.org>. tells us that the exact name match for
> wwww.ietf.org <http://wwww.ietf.org> does not exist, since it appears
> in-between the two names. Therefore, the remaining ietf.org
> <http://ietf.org>. -> _dmarc.ietf.org <http://dmarc.ietf.org>. NSEC
> should be used to prove that “no possible wildcard RRset exists that
> could have been used to generate a positive response” for the name
> wwww.ietf.org <http://wwww.ietf.org>.
> 
> *How can ietf.org <http://ietf.org>. -> _dmarc.ietf.org
> <http://dmarc.ietf.org> NSEC be used to prove that there is no wildcard
> record for the name wwww.ietf.org <http://wwww.ietf.org>?* Do we need to
> prove that all the possible sources of synthesis for wwww.ietf.org
> <http://wwww.ietf.org> appear in-between ietf.org <http://ietf.org>. and
> _dmarc.ietf.org <http://dmarc.ietf.org>?

The NSEC record ietf.org -> _dmarc.ietf.org proves that there is no
source of synthesis for "wwww.ietf.org" so we could not have generated a
wildcard response (note there is only ever one source of synthesis for a
given name).

> Or do we only need to prove that *.ietf.org <http://ietf.org> appears
> in-between ietf.org <http://ietf.org>. and _dmarc.ietf.org
> <http://dmarc.ietf.org>? If so why do we choose *.ietf.org
> <http://ietf.org> instead of *.org or *?

Because "*.ietf.org" is the source of synthesis (the other names are
above the closest encloser.

Hope this clarifies things.

Best regards,

Matthijs

---

From: Viktor Dukhovni <[email-masked]>
Date: Wed, 27 Oct 2021 02:51:28 -0400

On Tue, Oct 26, 2021 at 10:21:29PM -0700, Joey Deng wrote:

> name matching: We should prove that no possible wildcard RRset exists
> that could have been used to generate a positive response.

This is accomplished via a 'closest encloser' proof, in the case of NSEC
this takes up to two records:

    1. An NSEC record that excludes the shortest non-existent ancestor
       of the qname.  The closest encloser is then the longest domain
       equal to or containing both endpoints of the NSEC pair.

    2. An NSEC record showing non-existence of a wildcard below that
       closest encloser (which may be the same as (1) in some cases.

> What are possible wildcard RRsets for a given name?

The label count of the wildcard response must then match the number of
labels in the closest encloser.  That is, the "*" domain would have to
have been an immediate child of the closest encloser (1).

> My understanding about possible wildcard RRsets for a given name are
> all the possible sources of synthesis.  For example, the possible
> wildcard RRsets that can be used to answer question wwww.ietf.org
> AAAA are:
>
> *.ietf.org

That would be the only one, because 'ietf.org' is known to exist.
[ There's presently no "*.ietf.org" wildcard domain. ]

> *.org

No, this lies above the closest encloser.

> * (but I think root can never be a wildcard, so this is impossible)

No, this lies above the closest encloser.  A "*" node in the root zone
is technically possible, but none is likely to ever be published.  If it
were to exist it would become the source of truth for all invalid and
typoed TLDs, which would be rather suboptimal.

> Is my understanding correct?

No.

> For example, if I send a DNS query for wwww.ietf.org with DO/CD bit
> set, there will be two NSEC records returned:
> 
> ```

This is an NXDOMAIN answer, not a NODATA or wildcard sythesised answer.

> wwwtest.ietf.org.	1800	IN	NSEC	xml2rfc.ietf.org. CNAME RRSIG NSEC

This record proves the non-existence of the qname, and also "ietf.org"
as the closest encloser.

> ietf.org.		1800	IN	NSEC	_dmarc.ietf.org. A NS SOA MX TXT AAAA RRSIG NSEC DNSKEY SPF

This record proves that "*.ietf.org" does not exist, and we're done.

> wwwtest.ietf.org. -> xml2rfc.ietf.org. tells us that the exact name
> match for wwww.ietf.org does not exist, since it appears in-between
> the two names.

Correct.

> Therefore, the remaining ietf.org. -> _dmarc.ietf.org. NSEC should be
> used to prove that “no possible wildcard RRset exists that could have
> been used to generate a positive response” for the name wwww.ietf.org.

Which it does, since the only potential wildcard is '*.ietf.org', given
"ietf.org" as the closest encloser. "*.ietf.org" would be between these
if it existed.

> How can ietf.org. -> _dmarc.ietf.org NSEC be used to prove that there
> is no wildcard record for the name wwww.ietf.org?

By virtue of the fact that wildcards never apply at or below sibling
names that exist.  If foo.example.com exists, then wildcards at
"*.example.com", "*.com", or "*" can never apply to any query at or
below "foo.bar.example.com".  The "*.example.com" wildcard can only
apply to names ending in a non-existent sibling of the wildcard
label (<missing>.example.com).

> Do we need to prove that all the possible sources of synthesis for
> wwww.ietf.org appear in-between ietf.org. and _dmarc.ietf.org?

There is only ever one such possible source.  The "*" label under
the closest encloser.

> Or do we only need to prove that *.ietf.org appears in-between
> ietf.org. and _dmarc.ietf.org?

Since there's only one possible source, this is the one to
disprove.

> If so why do we choose *.ietf.org instead of *.org or *?

See above.

-- 
    VIktor.