Subject: [dmarc-ietf] Doing a tree walk rather than PSL lookup

From: "John R Levine" <[email-masked]>
Date: 20 Nov 2020 19:02:20 -0500

Here's a draft about how DMARC might do a tree walk rather than look up an 
organizational domain in the PSL.

https://datatracker.ietf.org/doc/draft-levine-dmarcwalk/

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

---

From: Jesse Thompson <[email-masked]>
Date: Mon, 23 Nov 2020 12:50:23 -0600

On 11/20/20 6:02 PM, John R Levine wrote:
> Here's a draft about how DMARC might do a tree walk rather than look up an organizational domain in the PSL.
> 

Would it help if there was a new DMARC policy tag to trigger the tree walk?  It's still the same number of DNS lookups, but changes the order and doesn't happen unless the organization wants it, so (aside from potential abuse) it should minimize the overall DNS lookup overhead.

Look up _dmarc.sales.east.widgets.bigcorp.com - find no policy
Look up _dmarc.bigcorp.com - finds a policy with a tw=1 tag
Look up _dmarc.east.widgets.bigcorp.com - find no policy
Look up _dmarc.widgets.bigcorp.com - finds a valid sp tag

Is it also worth considering changing the direction of the lookups under the assumption that the consistency of/control over the sub-organization's sending practices increases with each branch?  This would potentially reduce the number of DNS lookups.

Look up _dmarc.sales.east.widgets.bigcorp.com - find no policy
Look up _dmarc.bigcorp.com - finds a policy with a valid tw=true tag
Look up _dmarc.widgets.bigcorp.com - finds a valid sp tag and no additional tw=1 tag

Jesse

---

From: Dave Crocker <[email-masked]>
Date: Mon, 23 Nov 2020 11:00:45 -0800

On 11/23/2020 10:50 AM, Jesse Thompson wrote:
> Would it help if there was a new DMARC policy tag to trigger the tree walk?

policy tags are useful when one has a dmarc record that might contain 
it.  the challenge here is to find that record.

d/

-- 
Dave Crocker
Brandenburg InternetWorking
bbiw.net

---

From: Jesse Thompson <[email-masked]>
Date: Mon, 23 Nov 2020 15:04:06 -0600

On 11/23/20 1:00 PM, Dave Crocker wrote:
> policy tags are useful when one has a dmarc record that might contain it.  the challenge here is to find that record.

I meant to suggest that the requirement for a tree walk would be that the Organizational Domain would need to have that in its policy.  It seems like a decent compromise for the people worried about unnecessary DNS lookup overhead.

Jesse

---

From: Dave Crocker <[email-masked]>
Date: Mon, 23 Nov 2020 13:06:31 -0800

> I meant to suggest that the requirement for a tree walk would be that the Organizational Domain would need to have that in its policy.  It seems like a decent compromise for the people worried abou…

Except that it can't 'trigger' a tree walk.

On the other hand, it might declare itself to be the (an?) OD.

d/

-- 
Dave Crocker
[email-masked]
408.329.0791

Volunteer, Silicon Valley Chapter
American Red Cross
[email-masked]

---

From: "John Levine" <[email-masked]>
Date: 23 Nov 2020 16:38:46 -0500

In article <[email-masked]> you write:
>> I meant to suggest that the requirement for a tree walk would be that the Organizational Domain would need to have that in its policy. 
>It seems like a decent compromise for the people worried about unnecessary DNS lookup overhead.

If I'm going to go to the effort to download and decode a PSL and find the OD, I'll just use the OD.

One of the points of the tree walk is to get rid of the PSL processing.

It looks to me that a tree walk limited to some modest number of
levels like 7 or 10 would handle close enough to 100% of real mail.
When I brought this up in dnsop last week there was some concern about
super long tree walks but I didn't get the NO NO NO that we got in the
old days. DNS operators now realize that an amazingly large fraction
of DNS traffic is garbage, and a little extra noise from the
occasional tree walk is not a big deal.

In normal mail, the number of labels is usually quite low, here's my distribution by
number of dots:

2404 .
1215 ..
 152 ...
  10 ....

R's,
John

---

From: Alessandro Vesely <[email-masked]>
Date: Tue, 24 Nov 2020 13:19:54 +0100

> One of the points of the tree walk is to get rid of the PSL processing.

The PSL processing is a local lookup on an in-memory suffix tree.  How is it a 
progress to replace it with a tree walk?  A PSL search is lightning faster than 
even a single DNS lookup, isn't it?

Best
Ale
--

---

From: Joseph Brennan <[email-masked]>
Date: Tue, 24 Nov 2020 10:00:16 -0500

I will ask why the recipient system should look up anything but the dmarc
record for the specific domain in the Header From.

In some cases looking up related domains is useful, and in some cases it
can lead to disruption. We don't look up SPF records for related domains,
because they are deliberately different in many cases, e.g. one domain for
mail from end users, another for mail sent by a vendor, yet another for
another vendor. Why is dmarc different?

-- 
Joseph Brennan
Lead, Email and Systems Applications
Columbia University Information Technology

---

From: Dave Crocker <[email-masked]>
Date: Tue, 24 Nov 2020 07:15:42 -0800

On 11/24/2020 7:00 AM, Joseph Brennan wrote:
> I will ask why the recipient system should look up anything but the 
> dmarc record for the specific domain in the Header From. 

Hmmm.  Unless I've missed it, the DMARC spec does not explain the reason 
for needing the Organizational Domain.

d/

-- 
Dave Crocker
[email-masked]
408.329.0791

---

From: Todd Herr <[email-masked]>
Date: Tue, 24 Nov 2020 10:28:40 -0500

> for needing the Organizational Domain.
There are two reasons (at least) for needing the Organizational Domain, and
they are discussed in RFC 7489:

   1. DMARC also allows for the explicit or implicit expression of policy
   for sub-domains at the Organizational Domain level. This matters for those
   times when _dmarc.RFC5322.From.domain is non-existent and
   RFC5322.From.domain is a sub-domain of the Organizational Domain.
   2. The default mode for authenticated identifier alignment, relaxed,
   requires only that the Organizational Domains for both identifiers are the
   same, and so the Organizational Domain must be known in order for relaxed
   alignment to be ascertained.

What is perhaps missing from RFC 7489 is the reason that the authors chose
to make these two items part of the specification.

-- 

*Todd Herr* | Sr. Technical Program Manager
*e:* [email-masked]
*p:* 703.220.4153

This email and all data transmitted with it contains confidential and/or
proprietary information intended solely for the use of individual(s)
authorized to receive it. If you are not an intended and authorized
recipient you are hereby notified of any use, disclosure, copying or
distribution of the information included in this transmission is prohibited
and may be unlawful. Please immediately notify the sender by replying to
this email and then delete it from your system.

---

From: Dave Crocker <[email-masked]>
Date: Tue, 24 Nov 2020 07:36:40 -0800

Just to be clear, I'm not challenging the need.  Rather I'm just looking 
for text that explains the need.  And I'm not finding it...

On 11/24/2020 7:28 AM, Todd Herr wrote:
> There are two reasons (at least) for needing the Organizational 
> Domain, and they are discussed in RFC 7489:
>
>  1. DMARC also allows for the explicit or implicit expression of
>     policy for sub-domains at the Organizational Domain level. This
>     matters for those times when _dmarc.RFC5322.From.domain is
>     non-existent and RFC5322.From.domain is a sub-domain of the
>     Organizational Domain.
>     requires only that the Organizational Domains for both identifiers
>     are the same, and so the Organizational Domain must be known in
>     order for relaxed alignment to be ascertained.
>
Except that I do not find either of these points provided in the document.

> What is perhaps missing from RFC 7489 is the reason that the authors 
> chose to make these two items part of the specification.

That would, of course, also be nice to include.

d/

-- 
Dave Crocker
[email-masked]
408.329.0791

---

From: Todd Herr <[email-masked]>
Date: Tue, 24 Nov 2020 10:52:30 -0500

On Tue, Nov 24, 2020 at 10:37 AM Dave Crocker <[email-masked]> wrote:

> There are two reasons (at least) for needing the Organizational Domain,
> and they are discussed in RFC 7489:
>
For point 1, this is from Section 6.6.3, Policy Discovery:

   1.  Mail Receivers MUST query the DNS for a DMARC TXT record at the
       DNS domain matching the one found in the RFC5322
<https://tools.ietf.org/html/rfc5322>.From domain in
       the message.  A possibly empty set of records is returned.

   2.  Records that do not start with a "v=" tag that identifies the
       current version of DMARC are discarded.

   3.  If the set is now empty, the Mail Receiver MUST query the DNS for
       a DMARC TXT record at the DNS domain matching the Organizational
       Domain in place of the RFC5322
<https://tools.ietf.org/html/rfc5322>.From domain in the message (if
       different).  This record can contain policy to be asserted for
       subdomains of the Organizational Domain.  A possibly empty set of
       records is returned.

For point 2, this is from Section 3.1.1, DKIM-Authenticated Identifiers:

   In relaxed mode, the Organizational Domains of both the [DKIM
<https://tools.ietf.org/html/rfc7489#ref-DKIM>]-
   authenticated signing domain (taken from the value of the "d=" tag in
   the signature) and that of the RFC5322
<https://tools.ietf.org/html/rfc5322>.From domain must be equal if
   the identifiers are to be considered aligned.  In strict mode, only
   an exact match between both of the Fully Qualified Domain Names
   (FQDNs) is considered to produce Identifier Alignment.

Also for point 2, this is from Section 3.1.2, SPF-Authenticated Identifiers:

   In relaxed mode, the [SPF
<https://tools.ietf.org/html/rfc7489#ref-SPF>]-authenticated domain
and RFC5322 <https://tools.ietf.org/html/rfc5322>.From
   domain must have the same Organizational Domain.  In strict mode,
   only an exact DNS domain match is considered to produce Identifier
   Alignment.

--

---

From: Dave Crocker <[email-masked]>
Date: Tue, 24 Nov 2020 07:56:10 -0800

On 11/24/2020 7:52 AM, Todd Herr wrote:
> ...

Perhaps I am misreading these, but I see them only as 'what' and 'how', 
not 'why'.  The 'why' is important.  It is often noted in our 
discussions, but seems to be missing from the spec.

d/

-- 
Dave Crocker
[email-masked]
408.329.0791

---

From: "Murray S. Kucherawy" <[email-masked]>
Date: Tue, 24 Nov 2020 08:46:46 -0800

> discussions, but seems to be missing from the spec.

Seems like something the -bis document should tackle.

-MSK

---

From: "Murray S. Kucherawy" <[email-masked]>
Date: Tue, 24 Nov 2020 08:50:20 -0800

> even a single DNS lookup, isn't it?

Sure, but only if you think the PSL is accurate.  Otherwise you're basing
your shortcut up the tree on data you don't have reason to trust.  On the
other hand, a tree walk, while more expensive in terms of queries, isn't a
heuristic based on possibly stale information.

-MSK

---

From: Jesse Thompson <[email-masked]>
Date: Tue, 24 Nov 2020 10:55:12 -0600

On 11/24/20 9:52 AM, todd.herr=[email-masked] wrote:
> On Tue, Nov 24, 2020 at 10:37 AM Dave Crocker <[email-masked] <mailto:[email-masked]>> wrote:
> 
>     Just to be clear, I'm not challenging the need.  Rather I'm just looking for text that explains the need.  And I'm not finding it...
> 
>>     There are two reasons (at least) for needing the Organizational Domain, and they are discussed in RFC 7489:
>>
>>      1. DMARC also allows for the explicit or implicit expression of policy for sub-domains at the Organizational Domain level. This matters for those times when _dmarc.RFC5322.From.domain is non-existent and RFC5322.From.domain is a sub-domain of the Organizational Domain.
>>      2. The default mode for authenticated identifier alignment, relaxed, requires only that the Organizational Domains for both identifiers are the same, and so the Organizational Domain must be known in order for relaxed alignment to be ascertained.
>>
>        DNS domain matching the one found in the RFC5322 <https://tools.ietf.org/html/rfc5322>.From domain in
>        Domain in place of the RFC5322 <https://tools.ietf.org/html/rfc5322>.From domain in the message (if
>    In relaxed mode, the Organizational Domains of both the [DKIM <https://tools.ietf.org/html/rfc7489#ref-DKIM>]-
>    the signature) and that of the RFC5322 <https://tools.ietf.org/html/rfc5322>.From domain must be equal if

The end of Section 3.1 might need to be clarified:

"Relaxed mode can be used when the operator also wishes to affect message flows bearing subdomains of the verified domains."

* I assume that relaxed mode can be set in the DMARC policy of a subdomain even if the Organizational Domain doesn't have (or want) that in its policy

* The subdomains in this context are the subdomains of the Organizational Domain, rather than the subdomains of the domain that published the relaxed mode in its policy

So if acme.example publishes aspf=s adkim=s 
It does not prevent finance.acme.example from publishing aspf=r adkim=r
Which would align widgets.acme.example with finance.acme.example even if the intent was to only align delegated-esp.finance.acme.example with finance.foo.example

Suggested better wording:

"Relaxed mode is determined from the policy of the RFC5322.From domain or from the Organizational Domain policy if the RFC5322.From domain has no policy.  It can be used when the operator also wishes to affect message flows bearing subdomains of the Organizational Domain."

If "walking the tree" is viable, then perhaps it should be:

"Relaxed mode is determined from the policy of the RFC5322.From domain or from [something about walking the tree to determine the policy].  It can be used when the operator also wishes to affect message flows bearing subdomains of the domain that published the relaxed mode policy."

Jesse

---

From: "John Levine" <[email-masked]>
Date: 24 Nov 2020 12:03:51 -0500

>even a single DNS lookup, isn't it?

You have to download a copy of the PSL, read it into your program, and
parse it into some internal form. The PSL is over 200K of text and
13,000 lines, so while it's not a large file, it's not zero either.

If you're lucky you can amortize your PSL parsing across multiple
DMARC checks, but your DNS cache amortizes DNS lookups across mutiple
checke, too.

The DNS approach has the advantage that you don't have to depend on a
third party's text file updated at unknown intervals, and also makes
it easier to deal with what I've called the Holy Roman Empire problem.

R's,
John

---

From: "John Levine" <[email-masked]>
Date: 24 Nov 2020 12:21:41 -0500

In article <[email-masked]> you write:
>Which would align widgets.acme.example with finance.acme.example even if the intent was to only align
>delegated-esp.finance.acme.example with finance.foo.example

With the tree walk, I was thinking that if the tree walk finds a _dmarc record, that acts
as the organizational domain, so finance.acme.example can only allow alignment with itself
or its descendants.

This is different from the way that OD works now, but the questions are is it worse, and what
will break if we do it.

R's,
John

---

From: Dave Crocker <[email-masked]>
Date: Tue, 24 Nov 2020 10:19:15 -0800

> This is different from the way that OD works now, but the questions are is it worse, and what

Let's consider some attributes, starting with a trivial initial set...

*Accuracy:*       How accurate is the data that gets retrieved?

*Reliability*:    How likely is it that a query will complete successfully?

*Latency:*        How long does it take for a query to complete?

*Vulnerability:*  How easily/likely is it that the service can be 
compromised?

*Scaling:*        How well does it operate, at Internet scale?

*PSL* *Tree-Walk*

*Accuracy: *       Known problematic        100%

*Reliability:* High                     Mixed

*Latency: * None                     Potentially high

*Vulnerability:*     Generally none           DOS

*Scaling:*           Poor admin, good ops     Good admin, potentially 
poor ops

d/

-- 
Dave Crocker
[email-masked]
408.329.0791

---

From: Alessandro Vesely <[email-masked]>
Date: Tue, 24 Nov 2020 19:47:55 +0100

On Tue 24/Nov/2020 17:50:20 +0100 Murray S. Kucherawy wrote:
>>> If I'm going to go to the effort to download and decode a PSL and find
>>> the OD, I'll just use the OD. >>>
>> The PSL processing is a local lookup on an in-memory suffix tree.  How is 
>> it a progress to replace it with a tree walk?  A PSL search is lightning
>> faster than even a single DNS lookup, isn't it? >>
> 

The PSL is the result of a community-maintained effort.  They do not follow 
intricate naming restrictions that ccTLDs might theorize, but actively track 
subdomains as they become visible/ noticed.  It is remarkably good.

The reason why one may happen to use stale information is because updates are 
not so well organized.  Arguably, it's not going to reach a stable state until 
it's considered a sort of hack.

For one, the CA/Browser forum had that stance:

On Feb 1, 2013, at 10:25 AM, Phillip wrote:
     The public suffix list is a hack. It should go away. There needs to be a
     mechanism for determining if a domain is a public suffix or not but that
     information should be distributed through the DNS and not through an ad hoc
     list that a third party is meant to be maintaining under ill-defined
     criteria and without the active participation of the TLD operators.
         https://archive.cabforum.org/pipermail/public/2013-February/001146.html

That stance is justified by Section 8.2 of RFC 6454.  However, their current 
Baseline Requirements state the following:

     Determination of what is “registry-controlled” versus the registerable
     portion of a Country Code Top-Level Domain Namespace is not standardized
     at the time of writing and is not a property of the DNS itself. Current
     best practice is to consult a “public suffix list” such as the Public
     Suffix List (PSL), and to retrieve a fresh copy regularly.
        https://cabforum.org/wp-content/uploads/CA-Browser-Forum-BR-1.7.3.pdf

And, noticeably, the URL Living Standard references the PSL plainly.  They call 
*registrable domain* what we call Organizational Domain.  See:
https://url.spec.whatwg.org/#host-public-suffix

Best
Ale
--

---

From: "Doug Foster" <[email-masked]>
Date: Tue, 24 Nov 2020 13:49:26 -0500

Better a correct answer slowly than an incorrect answer quickly.

For the existing PSL, it is not just the accuracy of the document itself, but also the accuracy of the parsing process.   Is there a well-trusted parser floating around?

DF

From: dmarc [mailto:[email-masked]] On Behalf Of Dave Crocker
Sent: Tuesday, November 24, 2020 1:19 PM
To: [email-masked]
Subject: Re: [dmarc-ietf] Doing a tree walk rather than PSL lookup

 

Accuracy:       How accurate is the data that gets retrieved?

Reliability:    How likely is it that a query will complete successfully?

Latency:        How long does it take for a query to complete?

Vulnerability:  How easily/likely is it that the service can be compromised?

Scaling:        How well does it operate, at Internet scale?

                   PSL                      Tree-Walk

Accuracy:          Known problematic        100%

Reliability:       High                     Mixed

Latency:           None                     Potentially high

Vulnerability:     Generally none           DOS

Scaling:           Poor admin, good ops     Good admin, potentially poor ops

d/

-- 
Dave Crocker
[email-masked]
408.329.0791

---

From: Alessandro Vesely <[email-masked]>
Date: Tue, 24 Nov 2020 20:24:23 +0100

> 13,000 lines, so while it's not a large file, it's not zero either.

Right.  The optimal solution would be to load the list and the lookup algorithm 
as a shared object.  Currently, my filter has its private copy of it.  But then 
I don't reload the filter so often that parsing the file is noticeable.  To 
wit, loading the virus database takes much much longer.

> DMARC checks, but your DNS cache amortizes DNS lookups across multiple
> checks, too.

I doubt I'd get comparable efficiency, even if my mail server has a dedicated 
caching resolver.  Mail servers that rely on stub resolvers would experience a 
noticeable degradation.

> third party's text file updated at unknown intervals,

Agreed.

> and also makes it easier to deal with what I've called the Holy Roman Empire
> problem.

Uh?  The Holy Roman Empire became a disconnected tree soon after Charlemagne's 
death, so that looks like some of the dystopic scenarios that ISOC conceived a 
few years ago.  Not sure what you mean.

Best
Ale
--

---

From: "John R Levine" <[email-masked]>
Date: 24 Nov 2020 14:29:11 -0500

> Right.  The optimal solution would be to load the list and the lookup 
> algorithm as a shared object.  Currently, my filter has its private copy of 
> it.  But then I don't reload the filter so often that parsing the file is 
> noticeable.  To wit, loading the virus database takes much much longer.

Indeed.  I don't think that processing the PSL is an overwhelming amount 
of work, but I also don't think there is much difference in performance 
between using the PSL and making DNS queries that are likely to be 
answered from a local cache.

> "Holy Roman Empire"

Organizations, typically universities, where the nominal organization tree 
and the actual control are different.  The PSL isn't useful because the 
party that controls their Org domain often doesn't control lower parts of 
the DNS tree.

Regards,

---

From: "Murray S. Kucherawy" <[email-masked]>
Date: Tue, 24 Nov 2020 17:06:49 -0800

> subdomains as they become visible/ noticed.  It is remarkably good.

I'm curious as to whether this is the consensus opinion of the PSL.  It's
my impression that it is not, given the arguments that supported the
creation of the DBOUND working group in the first place, for instance.

The citations you made here appear to support that notion as well.

-MSK

---

From: "John Levine" <[email-masked]>
Date: 24 Nov 2020 21:03:47 -0500

In article <[email-masked]> you write:
>-=-=-=-=-=-
>> The PSL is the result of a community-maintained effort. ...

>creation of the DBOUND working group in the first place, for instance.

The PSL lives at github and has three committers.

https://github.com/publicsuffix

Anyone can send in a pull request and they have a process to decide
what to accept. I agree they do a pretty good job but it is a tiny
project run by a few volunteers. They do not go looking for changes
beyond tracking what's in the root.

Keep in mind that the purpose of the PSL is to manage cross-site
cookies in web browsers. If it works for anything else, it's a
coincidence.

---

From: [email-masked]
Date: Tue, 24 Nov 2020 18:23:11 -0800 (PST)

> > even a single DNS lookup, isn't it?

We added PSL support for other reasons some time back.

FWIW, there were some intricacies I didn't like in the suffix tree approach.
And since memory use really isn't a consideration for something this small, I
opted for multiple lookups in a hash table instead. We have our own hash table
code and loadable format, but there are compile-to-loadable-format tools out
there if you don't want to roll your own.

> You have to download a copy of the PSL,

Hopefully you're doing that in the background...

> read it into your program, and

Our implementation processes a bunch of text files from various sources, of
which the PSL is less than 5% of the total size, into our loadable format.

I just checked, and it takes a litle over 2 CPU seconds to run the program. On
an 333Mhz Alpha.

I really don't think this is a concern.

> DMARC checks, but your DNS cache amortizes DNS lookups across mutiple

Parse only happens when one of the input files changes. Why would you
implement it any other way? 

> it easier to deal with what I've called the Holy Roman Empire problem.

So you download and check every week or whatever. Still not seeing a problem.

Finally, there's the HRE issue. Which I guess could be a problem. But so can
DNS usage, which is subject to what I'll now call the fiefdom problem, where
you're required to use a DNS service operated by someone else in your org and
they are ... problematic.

Of course DNS use is unavoidable. Even so, the fiefdom problem has led to
requests to minimize DNS usage by any means possible.

The HRE problem remains theoretical for us at least.

				Ned

---

From: Alessandro Vesely <[email-masked]>
Date: Wed, 25 Nov 2020 09:08:36 +0100

On Tue 24/Nov/2020 20:29:11 +0100 John R Levine wrote:
> 
>> "Holy Roman Empire"
> 
> Organizations, typically universities, where the nominal organization tree and 
> the actual control are different.  The PSL isn't useful because the party that 
> controls their Org domain often doesn't control lower parts of the DNS tree.

The PSL takes care of particular cases, listing suffixes like cloudfront.net or 
various flavors of amazonaws.com, which officially look like any other 2nd 
level domain, but actually host independent organizations.  Those entries are 
commented with the names and email addresses of the principal who submitted 
them.  In their own words:

     In addition, owners of privately-registered domains who themselves issue
     subdomains to mutually-untrusting parties may wish to be added to the
     PRIVATE section of the list.
                         https://github.com/publicsuffix/list/wiki/Guidelines

Best
Ale
--