Subject: [DNSOP] DNSSEC validation latency

From: Tony Finch <[email-masked]>
Date: Mon, 2 Dec 2013 12:23:06 +0000

Tangentially from the topic of draft-wouters-edns-tcp-chain-query, I have
noticed a gap in performance between what BIND's validating resolver does
and what the DNSSEC specifications allow.

If I run the following commands to prepare the cache ...

$ rndc flush
$ dig dnskey uk
$ dig dnskey ac.uk

... then these commands to watch what happens with a sample query ...

$ rndc trace 11
$ dig www.cam.ac.uk
$ rndc notrace

... I can see the following series of queries and responses, one after
another:

(1) send www.cam.ac.uk IN A ? to ac.uk nameserver
    receive delegation response
(2) send www.cam.ac.uk IN A ? to cam.ac.uk nameserver
    receive answer
(3) to validate www.cam.ac.uk IN A ...
    send cam.ac.uk IN DNSKEY ? to cam.ac.uk nameserver
    receive answer
(4) to validate cam.ac.uk DNSKEY ...
    send cam.ac.uk IN DS ? to ac.uk nameserver
    receive answer

This is twice as slow as it should be.

In RFC 4035 section 3.1.4, authoritative name servers that are returning a
referral are required to include the DS RRset (or a proof of nonexistence)
alongside the delegation NS RRset and glue, all in the same response.

So in the trace above, step (4) is redundant: the resolver already
received the DS in step (1).

Furthermore, the presence of the DS in the referral tells the resolver
that it will need the DNSKEY RRset in order to validate the answer, so it
should send queries (2) and (3) concurrently.

I am aware there was some debate about top-down vs. bottom-up validation,
and that BIND does bottom-up validation. What are the advantages of
bottom-up validation? It seems to be fundamentally twice as slow as
top-down validation.

Tony.
-- 
f.anthony.n.finch  <[email-masked]>  http://dotat.at/
Forties, Cromarty: East, veering southeast, 4 or 5, occasionally 6 at first.
Rough, becoming slight or moderate. Showers, rain at first. Moderate or good,
occasionally poor at first.

---

From: ✅ Roy Arends <[email-masked]>
Date: Mon, 2 Dec 2013 12:44:14 +0000

> received the DS in step (1).

In this case, yes. However, this is not consistent across all delegation points. As an example, UK and ORG.UK are hosted from the same set of servers. When asked about, say, nominet.org.uk, these servers will happily refer to the proper nameservers, including a DS record for nominet.org.uk. However, the validating resolver needs to explicitly ask for the org.uk DS record, since it will not show up in any delegation response. It might be this specific trade-off (asking explicitly for DS instead of opportunistically learning DS along the way, which might fail) why named choses to ask for the DS record.

> should send queries (2) and (3) concurrently.

Not necessarily. www.cam.ac.uk might be an unsigned delegation from the signed cam.ac.uk, so this might be followed by another query (for the www.cam.ac.uk record from the www.cam.ac.uk name servers). If that succeeds, only then validation makes sense.

> bottom-up validation? It seems to be fundamentally twice as slow as

Independent of top-down vs bottom up, I think it makes sense to complete the delegation chain first, then complete the validation chain (which happens in named, that is, you first see (1) and (2), then (3) and (4). I agree there is some room for optimisation, using previously obtained information (like the DS record and its signature) to complete the validation chain, which has a complexity cost as well.

Roy

---

From: Tony Finch <[email-masked]>
Date: Mon, 2 Dec 2013 16:36:22 +0000

✅ Roy Arends <[email-masked]> wrote:
> In this case, yes. However, this is not consistent across all delegation
> points. As an example, UK and ORG.UK are hosted from the same set of
> servers. When asked about, say, nominet.org.uk, these servers will
> happily refer to the proper nameservers, including a DS record for
> nominet.org.uk. However, the validating resolver needs to explicitly ask
> for the org.uk DS record, since it will not show up in any delegation
> response.

Happily, unless there is more than one intermediate zone cut, the resolver
can get the missing DS and DNSKEY RRs in the same round trip it uses to
follow the referral.

But yes, that is a good example of a situation where you have to do
at least a little upwards validation.

> Not necessarily. www.cam.ac.uk might be an unsigned delegation from the
> signed cam.ac.uk, so this might be followed by another query (for the
> www.cam.ac.uk record from the www.cam.ac.uk name servers).

Right, but having got the referral at www.cam.ac.uk and the cam.ac.uk
DNSKEY RRset, we are in the same situation as in my original example, but
one level further down the hierarchy.

> If that succeeds, only then validation makes sense.

Why? Why not validate the chain of referrals as you follow them? The
protocol is designed to support that otherwise it would not include the DS
in the referral.

Tony.

---

From: Mark Andrews <[email-masked]>
Date: Tue, 03 Dec 2013 13:45:59 +1100

In message <[email-masked]>, Tony Finch writes:
> 
> =E2=9C=85 Roy Arends <[email-masked]> wrote:

Tony,
       why did you put a WHITE HEAVY CHECK MARK before Roy's name?
As far as I can tell it is just extraneous noise being transmitted
for no benefit to anyone.

> protocol is designed to support that otherwise it would not include the DS

It's more because we havn't coded for it yet, especially the non
existence case, than anything else.

Mark

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

---

From: Tony Finch <[email-masked]>
Date: Tue, 3 Dec 2013 10:06:40 +0000

Mark Andrews <[email-masked]> wrote:
> Tony Finch <[email-masked]> wrote:
> > Roy Arends <[email-masked]> wrote:
> >

Yes, and that's perfectly fine :-) I'm just puzzled why Roy thinks it
doesn't make sense to reduce validation latency.

I'm also wondering what the advantages are to bottom-up validation. It
gets really knotty when the leaf records have broken signatures - you
have to keep walking up the tree to see if there's an insecure delegation
to work out whether to return bogus or insecure.

Tony.

---

From: ✅ Roy Arends <[email-masked]>
Date: Tue, 3 Dec 2013 10:42:54 +0000

> doesn't make sense to reduce validation latency.

I said "I agree there is some room for optimisation, using previously obtained information (like the DS record and its signature) to complete the validation chain, which has a complexity cost as well.”

The additional complexity hasn’t been added yet, and I highlighted some of the corner cases that comes with it, if it would be added.

i.e. I never said that it doesn’t make sense to reduce validation latency. On the contrary.

I also said that it makes sense to complete the delegation chain first, then complete the validation chain. To be clear, I’m all for reducing validation latency. Hence if there is stuff to validate and the keys are there, go for it. If the keys (or DS records) are not yet present, I’d prioritise getting the records in for the delegation chain before getting the records for the validation chain. If there is no complete delegation chain (something is lame), SERVFAIL early on it. The client might not care about validation (CD=1). 

> to work out whether to return bogus or insecure.

I don’t think it actually matters, (bottom-up vs top-down). It is simply a chain of TA-DNSKEY-(DS-DNSKEY)-ANSWER. Since DNSKEYs have to be explicitly queried for (and sometimes DS records), just fill them in. You can issue a set of queries for all the missing DNSKEYs in parallel (not waiting for one to finish before issuing the second missing DNSKEY/DS). It is then either complete or not. If not, all bets are off. I personally don’t like the effect of querying all authoritative servers for a single zone in order to get a proper validation path, and then backtracking to get an alternative delegation path. That leads to the “Rollover and Die” issues we saw a couple of years ago.

Roy

---

From: Tony Finch <[email-masked]>
Date: Tue, 3 Dec 2013 11:06:56 +0000

Roy Arends <[email-masked]> wrote:
> I also said that it makes sense to complete the delegation chain first,
> then complete the validation chain.

But those two statements are a contradiction. The main opportunity to
reduce latency is by getting the two chains concurrently.

Tony.

---

From: ✅ Roy Arends <[email-masked]>
Date: Tue, 3 Dec 2013 11:36:30 +0000

> reduce latency is by getting the two chains concurrently.

Both can be done concurrently. You’re right. I was wrong.

I was worried (and the worry led to the confusion) that _if_ the delegation chain fails to complete, cycli are wasted by trying to validate this incomplete delegation chain (and I remember the redundant Rollover and Die traffic related to this exact issue). 

Hope this helps.

Roy