Subject: [dnsext] The missing link (was Re: An argument why bname-style delegation is needed)

From: Brian Dickson <[email-masked]>
Date: Fri, 13 Aug 2010 20:03:20 -0300

On Wed, Aug 11, 2010 at 12:33 PM, Brian Dickson <
[email-masked]> wrote:

>
>
> On Wed, Aug 11, 2010 at 10:56 AM, Andrew Sullivan <[email-masked]>wrote:
>
>> Colleagues,
>>
>> Under a provisioning-only regime, the requirement that N1.P and N2.P
>> be "the same name" cannot be guaranteed.  That is because under
>> provisioning, it would be necessary to duplicate all the zones all the
>> way down the tree, and there is no easy way in the DNS to check that
>> two zones are equivalent without walking the zone.
>>
>>
>
> And now I'll use another argument for *non*-Xname changes to DNS,
> as an augmentation of what exists now, to facilitate both provisioning-only
> mechanisms,
> and to facilitate better-scaling DNSSEC signing.
>
> What is missing, is a *server*-side (below-the-zone-cut) apex record, which
> asserts all the names by which the zone is known.
>
>
Actually, I was wrong.

Here's a brief synopsis of what follows:

RFC 4034 and its predecessors, was written with a strict-tree-model of DNS,
modulo CNAME and DNAME.
In a strict tree, there is one path from the root to a leaf, and one path
from any leaf to the root.

It shows up in the logic and wording, whenever the text includes "_the_
name".

In an acyclic graph model, each link is unidirectional (delegation), the
root is by definition the only node to which no delegations are made, and a
leaf is a node from which no delegations are made. There may be more than
one path from the root to a leaf, and more than one path from any leaf to
the root.

The IDN problem (and the general "equivalent zones" problem) *can* be solved
rather neatly, by anchoring the procedures for validation and resolution at
the "last delegation apex", adopting a very slightly modified validation
methodology (which is provably equivalent security-wise), and revising the
appropriate RFCs to say "_a_ name" instead of "_the_ name", wherever that
language exists.

Or so I claim. :-)

The long version follows...

The basic problem here is that, even if there were some way to duplicate or
hard-link zone contents at multiple places in the DNS tree, with unique
forward linkages (NS zone cuts + DS) at unique places (i.e. labels or FQDNs)
in the DNS tree, the DNSSEC validation for RRSIGs presumes a uniqueness to
the back-link of the "signer", i.e. the owner name of the zone.

If zones are to be signed once, even when they are known by multiple names,
this creates a conundrum.

DNSSEC wants to authenticate the DNSKEY used to sign RDATA, and to do so by
name.

If we start the forward/backward label-matching at the RR owner whose RRSIG
we want to check, this can't be solved.

However, if we start the forward/backward label-matching and validation at
the apex of the zone in which the RR exists, the uniqueness problem can be
resolved, as well as preserving the rest of the security validation model.

Here is what we presume to already exist:
The zone Z is known by two names, K and L, where K is Ki.Ki-1...K3.K2.K1,
and L is similarly Lj.Lj-1....L3.L2.L1.
We make no assumptions regarding i and j.
We are interested in node in Z whose owner is x.y.K (and incidentally also
x.y.L, and possibly other names too.)
K and L are both DNSSEC secure entry points into Z. This means there are
apex DNSKEYs signed respectively with owner == K, and owner == L.
The validator may not have all of this information yet, i.e. the full
validation chain of K and L. It *should* have the full validation chain of
K, but may not yet have the full validation chain of L.

If x.y.K is signed only by L, we can still authenticate x.y, if the logic
used goes like this:

We need to find the DNSKEY at L, used to sign x.y.K.
For now, we ignore K != L (lexigraphically at least).
We look for the the DNSKEY at the apex of L (which is one of the names of Z,
although not the name we used to get here),
which matches the keytag of the RRSIG of x.y.K.
Before we can do anything with any of them, we need to validate them, via
their name "L".
This may mean chasing down the authentication chain all the way back to the
root, but presumably results in a validated SEP to L.
There may be more than one matching DNSKEY; if so, we need to try each of
them.
If we find a match, we have succeeded in validating x.y.L.
However, we were trying to validate x.y.K.

IFF we have a DNSKEY which validates x.y.L, which is found on the RRSIG of
x.y.L, AND the DNSKEY itself is signed by both K and L, and K and L are
SEPs, AND x.y.K == x.y.L AND RRSIG(x.y.K) == RRSIG(x.y.L) , THEN we can
claim the key that signed the RR is in the same zone as the RR, and is
valid, and validates the RR, and thus the RR is authenticated, for both
names x.y.K and x.y.L.

The crypto purists should note that the DS uses the owner name, but the
DNSKEY RDATA does not include anything dependent upon its owner name. The DS
values for K and L will be different, even if they are DS's for the same
DNSKEY.

Ideally, having a signed "nonce" at the apex of the zone, of sufficient
number of bits, would establish zone identity (and identity sharing).

However, nothing in the current DNS specs requires zones to be distinct or
unique, per se - and I don't think we want it to.
Ideally, the RRSIG of the ZSK should have enough entropy to satisfy the
crypto crowd -- which is what the SEP incorporates.
Q.E.D.

NB - we always have to prove the chain of delegations and signatures, so the
only change is the order in which certain checks are done, and then only in
the final zone.

NB2 - doing this trick at each layer of the delegation chain for IDNs, turns
O(n^k) to O(n), without using xNAME. Di.P and D1.P have authenticated SEPs
into their child zone, which means the DS Ci.Di is signed by D1 and still
authenticates, and so on.

This suggests that a modest change to the validation rules, can achieve the
desired results without *requiring* xNAME or protocol changes.

Brian