Subject: [DNSOP] NXDOMAIN and RFC 8020

From: "Murray S. Kucherawy" <[email-masked]>
Date: Tue, 6 Apr 2021 11:11:08 -0700

I'm wondering something about tree walks, which John Levine asked about in
November, as it's a topic of interest to the evolution of DMARC.

I've read RFC 8020 which says an NXDOMAIN cached for "foo.example" also
covers later queries for "bar.foo.example".  Makes sense.

Can this be used (or maybe amended) to cover the queries if they come in
the reverse order?  For instance, if "bar.foo.example" arrives first, but
the authoritative server can determine that the entire "foo.example" tree
doesn't exist, could it reply with an NXDOMAIN for the question plus a
cacheable indication about the entire tree instead of just the name that
was in the question?

This would make an ascending tree walk even for something crazy like
"a.b.c.d.....y.z.foo.example" extremely cheap as the cached NXDOMAIN for
"foo.example" covers the entire subtree, for a caching nameserver
implementing RFC 8020.

Maybe this is discussed somewhere that I missed in the references.  I'm
happy to take a "go read this for the answer" if that's the case.

Thanks,

-MSK

---

From: "libor.peltan" <[email-masked]>
Date: Tue, 6 Apr 2021 20:29:03 +0200

Hi Murray,

if foo.example does not exist and DNSSEC is in place, than the resolver 
actually, even with the queries "in reverse order", obtains and NSEC(3), 
proving non-existence for much more.

For example, the query is bar.foo.example, and the authoritative returns 
an NSEC proving that there is nothing between fa.example and fz.example. 
Thus, the resolver can later deduct nonexistence not only for 
foo.example, but also for fun.example and bar.fun.example, etc...

Without DNSSEC, this deduction (called "aggresive NSEC caching") is not 
possible.

Cheers,

Libor

Dne 06. 04. 21 v 20:11 Murray S. Kucherawy napsal(a):
> I'm wondering something about tree walks, which John Levine asked 
> about in November, as it's a topic of interest to the evolution of DMARC.
>
> I've read RFC 8020 which says an NXDOMAIN cached for "foo.example" 
> also covers later queries for "bar.foo.example".  Makes sense.
>
> Can this be used (or maybe amended) to cover the queries if they come 
> in the reverse order?  For instance, if "bar.foo.example" arrives 
> first, but the authoritative server can determine that the entire 
> "foo.example" tree doesn't exist, could it reply with an NXDOMAIN for 
> the question plus a cacheable indication about the entire tree instead 
> of just the name that was in the question?
>
> "a.b.c.d.....y.z.foo.example" extremely cheap as the cached NXDOMAIN 
> for "foo.example" covers the entire subtree, for a caching nameserver 
> implementing RFC 8020.
>
> Maybe this is discussed somewhere that I missed in the references.  
> I'm happy to take a "go read this for the answer" if that's the case.
>
> Thanks,
>
> -MSK
>
> _______________________________________________
> DNSOP mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/dnsop

---

From: Peter van Dijk <[email-masked]>
Date: Tue, 06 Apr 2021 20:36:49 +0200

And the 'go read this' reference is https://tools.ietf.org/html/rfc8198

On Tue, 2021-04-06 at 20:29 +0200, libor.peltan wrote:
> Hi Murray,
> if foo.example does not exist and DNSSEC is in place, than the resolver actually, even with the queries "in reverse order", obtains and NSEC(3), proving non-existence for much more.
> For example, the query is bar.foo.example, and the authoritative returns an NSEC proving that there is nothing between fa.example and fz.example. Thus, the resolver can later deduct nonexistence not only for foo.example, but also for fun.example and bar.fun.example, etc...
> Without DNSSEC, this deduction (called "aggresive NSEC caching") is not possible.
> Cheers,
> Libor
> > This would make an ascending tree walk even for something crazy like "a.b.c.d.....y.z.foo.example" extremely cheap as the cached NXDOMAIN for "foo.example" covers the entire subtree, for a caching nameserver implementing RFC 8020.
> > 
> > Maybe this is discussed somewhere that I missed in the references.  I'm happy to take a "go read this for the answer" if that's the case.

Kind regards,
-- 
Peter van Dijk
PowerDNS.COM BV - https://www.powerdns.com/

---

From: Shumon Huque <[email-masked]>
Date: Tue, 6 Apr 2021 14:48:41 -0400

> cacheable indication about the entire tree instead of just the name that

Yes, it can answer NXDOMAIN.

Without DNSSEC, there is no current way to provide an indication about the
longest ancestor of the name that did exist. With DNSSEC, the NSEC or NSEC3
records in the response can do this (as well as providing cryptographic
proof of this assertion with their signatures).

As mentioned by others, RFC8198 (which can be considered a superset of 8020
for signed zones) extends the semantics by allowing resolvers to infer
non-existence not only below the name, but for all names that fall in the
NSEC/NSEC3 spans.

Shumon.

---

From: "Murray S. Kucherawy" <[email-masked]>
Date: Tue, 6 Apr 2021 12:03:34 -0700

> proof of this assertion with their signatures).

Thanks, this (and the others) is helpful.

Focusing on "no current way", could the process described in RFC 8020
theoretically be amended to do so?  It's fine if the answer is "no", but
I'd love to understand why if that's the case.

-MSK

---

From: Shumon Huque <[email-masked]>
Date: Tue, 6 Apr 2021 15:51:13 -0400

On Tue, Apr 6, 2021 at 3:03 PM Murray S. Kucherawy <[email-masked]>
wrote:

>> Without DNSSEC, there is no current way to provide an indication about
>> the longest ancestor of the name that did exist. With DNSSEC, the NSEC or
>> NSEC3 records in the response can do this (as well as providing
>> cryptographic proof of this assertion with their signatures).
>>
>

I suspect the most common answer to your question will be "No, just deploy
DNSSEC". I'm sure one could devise a new protocol enhancement that an
authoritative server could use to convey this information, but I'm not sure
it is worth complicating the protocol to do so.

Also, even with 8020, there have been concerns raised that resolvers
implementing it, could be vulnerable to spoofing adversaries easily pruning
entire subtrees from their caches (rather than having to spoof many
individual names). Unbound, for example, implements 8020 only for signed
zones.

Shumon.

---

From: Brian Dickson <[email-masked]>
Date: Tue, 6 Apr 2021 12:56:47 -0700

> cacheable indication about the entire tree instead of just the name that

I think this is another point in favor of doing QNAME minimization. RFC7816
(technically experimental, but recommended.)

It kind of makes the query order moot; the resolver looks up the shorter
name first even while resolving the longer name.

Should be handled by the resolver, so maybe tangential to DMARC (other than
maybe being an included reference and recommendation within any DMARC
draft/RFC).

Brian

---

From: "Murray S. Kucherawy" <[email-masked]>
Date: Tue, 6 Apr 2021 14:15:46 -0700

On Tue, Apr 6, 2021 at 12:56 PM Brian Dickson <[email-masked]>
wrote:

> I think this is another point in favor of doing QNAME minimization.
> RFC7816 (technically experimental, but recommended.)
>

Is there any data or even a hint of how widely that experiment has been
deployed or implemented?

-MSK

---

From: Shumon Huque <[email-masked]>
Date: Tue, 6 Apr 2021 17:28:01 -0400

On Tue, Apr 6, 2021 at 5:16 PM Murray S. Kucherawy <[email-masked]>
wrote:

> On Tue, Apr 6, 2021 at 12:56 PM Brian Dickson <
> [email-masked]> wrote:
>

It's on by default in (recent versions of) a number of popular open source
DNS resolver implementations (BIND, Unbound, Knot).

Shumon.

---

From: "John Levine" <[email-masked]>
Date: 6 Apr 2021 17:41:10 -0400

It appears that Murray S. Kucherawy  <[email-masked]> said:
>-=-=-=-=-=-
>the reverse order?

In this application, no, because it's not doing a strict tree walk:

_dmarc.newjersey.sales.bigcorp.wtf
_dmarc.sales.bigcorp.wtf
_dmarc.bigcorp.wtf

The _dmarc tag means that none of the names is an ancestor of any of
the others. It could also look at, e.g., sales.bigcorp.wtf and see if
it has an NXDOMAIN and prune names below that, but I don't think that
approach is likely to win overall.

In a somewhat different world where we used RRTYPEs rather than _tag names, we
could do tree walks a lot more efficiently.

R's,
John

---

From: Manu Bretelle <[email-masked]>
Date: Tue, 6 Apr 2021 15:16:17 -0700

On Tue, Apr 6, 2021 at 12:51 PM Shumon Huque <[email-masked]> wrote:
>
> On Tue, Apr 6, 2021 at 3:03 PM Murray S. Kucherawy <[email-masked]> wrote:
>>
>>> Without DNSSEC, there is no current way to provide an indication about the longest ancestor of the name that did exist. With DNSSEC, the NSEC or NSEC3 records in the response can do this (as well as providing cryptographic proof of this assertion with their signatures).
>>
>>
>> Focusing on "no current way", could the process described in RFC 8020 theoretically be amended to do so?  It's fine if the answer is "no", but I'd love to understand why if that's the case.
>
>
> I suspect the most common answer to your question will be "No, just deploy DNSSEC". I'm sure one could devise a new protocol enhancement that an authoritative server could use to convey this information, but I'm not sure it is worth complicating the protocol to do so.
>
> Also, even with 8020, there have been concerns raised that resolvers implementing it, could be vulnerable to spoofing adversaries easily pruning entire subtrees from their caches (rather than having to spoof many individual names). Unbound, for example, implements 8020 only for signed zones.

Murray, an organization we both know very well, do not implement
ENT/RFC8020 for instance... In the case of DNSSEC you get proper
coverage with NSEC even if at best you use White (RFC4470) and Black
(https://tools.ietf.org/html/draft-valsorda-dnsop-black-lies-00) lies.

Manu

---

From: "Murray S. Kucherawy" <[email-masked]>
Date: Tue, 6 Apr 2021 15:39:31 -0700

> approach is likely to win overall.

Sure, but if I query "_dmarc.newjersey.sales.bigcorp.wtf" and I get back an
NXDOMAIN for "sales.bigcorp.wtf", I can eliminate at least one query,
because I know right away that the second one in your list isn't there
either.  Extend that out to a name with a dozen or more labels in it and
you're getting somewhere.

-MSK

---

From: "John R Levine" <[email-masked]>
Date: 6 Apr 2021 20:01:11 -0400

> NXDOMAIN for "sales.bigcorp.wtf", I can eliminate at least one query,

But you won't, you'll get back an answer for the name you looked up.

You could do a seprate check first for sales.bigcorp.wtf but as I said I 
don't think that will usually win.  It is my impression that the domain 
name tree is pretty flat, and if you limited a tree walk to four or five 
levels, that would catch every real DMARC record.

Also, if your DNS cache is synthesizing NXDOMAIN results either under a 
higher NXDOMAIN (RFC 8020) or using DNSSEC (RFC 8198) those queries will 
be pretty cheap to haandle since they won't cause any upstream queries, so 
you might as well just do the tree walk.

Regards,
John Levine, [email-masked], Taughannock Networks, Trumansburg NY
Please consider the environment before reading this e-mail. https://jl.ly

---

From: Andrew Sullivan <[email-masked]>
Date: Tue, 6 Apr 2021 21:06:21 -0400

>could do tree walks a lot more efficiently.

I guess we're now in the world-record running for "somewhat" doing the most amount of work in a sentence?  <ducks>

A

-- 
Andrew Sullivan
[email-masked]

---

From: "John R Levine" <[email-masked]>
Date: 6 Apr 2021 22:09:17 -0400

On Tue, 6 Apr 2021, Andrew Sullivan wrote:
>> In a somewhat different world where we used RRTYPEs rather than _tag names, 
>> we could do tree walks a lot more efficiently.
>

Hey, I'm the guy who wrote the DNS extension language so the web crudware 
that manages your DNS can automatically handle new RRTYPEs.  It's even 
part of perl's Net::DNS but it otherwise hasn't caught on.  Bummer.

Regards,

---

From: [email-masked]
Date: Wed, 07 Apr 2021 07:52:37 +0200 (CEST)

> DNS resolver implementations (BIND, Unbound, Knot).

And PowerDNS Recursor, see

    https://doc.powerdns.com/recursor/settings.html#qname-minimization

Steinar Haug, AS2116