Subject: proving NAME ERROR (was: Re: [dns-operations] NXDOMAIN vs NODATA for suffixes of existing name)

From: Roy Arends <[email-masked]>
Date: Tue, 18 Apr 2006 17:57:41 +0200

Rob Austein wrote on 04/17/2006 11:10:27 PM:

> That said, Roy's recent work on null-hash NSEC3 suggests that we may
> want to rethink the explanation of the attestations we're supplying
> anyway.  If I understand Roy's work correctly, his claim is that, in
> one or more of the cases where RFC 4035 says there are two things we
> have to prove, there are really three things we have to prove, and
> it's just an accident of ordering that always lets us prove all three
> things with at most two NSEC RRs.  Might be worth thinking through how
> we'd like to explain all this for the bis-updates document.

This is what Rob referred to:

During the NSEC3 pre-workshop, we determined that the content of NSEC3's 
when using the identity hash (effectively no hashing at all) are 
essentially the same as NSEC. And thus the method (proving absence) used
for NSEC3 must work on NSEC as well. It does work, and I'll try to 
describe here how.

The 'closest encloser' (CE) is the magic word. The CE is the nearest 
existing ancestor of QNAME. This terminology was introduced by Ed's 
wildcard-clarify draft. Ben invented this specific proving method 
(mistakes below are all mine).

Proving method:
In order to prove nonexistence of QNAME: assert the CE and prove that
assertion. A two step process.

1) Assert CE using an NSEC record. Since all NSEC records in a response 
   show the same CE (that is a fact, not a requirement), pick any. 

   Given an NSEC and a QNAME, the CE is asserted as follows: 
   Function NCA = Nearest Common Ancestor  (NAME, NAME). 
   CE = longest( NCA(NSEC ownername,QNAME), NCA(NSEC nxtdname,QNAME)) 

2) To prove asserted CE, prove nonexistence of immediate descendent of 
   CE relative to QNAME. 

Since the CE is now known, it is trivial to prove the nonexistence of a 
matching wildcard. (which is *.CE)

As an example

resolver queries server for a.b.c.example A 

server is authoritative for:

ZONE:
example.com SOA ...
example.com NS c.example.com
example.com NSEC c.example.com
c.example.com A
c.example.com NSEC example.com
...

The server responds: 

QNAME: a.b.c.example.com
auth: c.example.com NSEC example.com

1) validator asserts CE:

   CE = longest ( NCA(c.example.com, a.b.c.example.com), 
                  NCA(example.com, a.b.c.example.com))   ->
   CE = longest (c.example.com, example.com)   ->
   CE = c.example.com

   The asserted CE is c.example.com

2) prove that b.c.example.com does not exist (immidiate descendant of CE 
   (CE is c.example.com) relative to QNAME (QNAME is a.b.c.example.com))

   this is proven by the NSEC record: c.example.com NSEC example.com

since we have proven that b.c.example.com does not exist, we can infer 
that
a.b.c.example.com does not exist as well.

The two NSEC's used in (1) and (2) are always the same since the canonical 
ordering of names in the zone is exactly the same as the NSEC chain. This 
is not the case for NSEC3. For NSEC3, asserting the CE is done by taking 
QNAME and continuesly stripping the leftmost label of the QNAME, hash it 
and match it with all NSEC3's ownernames in a response (until the stripped 
qname is equal to the signers name, see NSEC3 draft for the specifics).

So, all in all. With NSEC, A NAME ERROR (rcode=3) response has at most 2 
NSECs. One to prove CE and one to prove absence of *.CE. 
With NSEC3, a NAME ERROR (rcode=3) response has at most 3 NSEC3s. One to 
assert the CE, one to prove the CE and one to prove the absence of *.CE. I 
say at most, since for both NSEC and NSEC3 it is true that less NSEC(3)s 
might be sufficient to satisfy the CE proof, the absence of *.CE and (in 
the NSEC3 case) the assertion of the CE.

What a validator really needs to prove is everything in step 2 and 3 of 
the server algorithm in rfc1034 4.3.2. This might be a good approach for 
the bis-updates draft.

Roy

--
to unsubscribe send a message to [email-masked] with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>

---

From: Edward Lewis <[email-masked]>
Date: Tue, 18 Apr 2006 16:10:51 -0400

I'm going to respond to this email before reading all of it - as a 
thought exercise.

>for NSEC3 must work on NSEC as well. It does work, and I'll try to

Off the cuff, I don't think that's a valid assertion.  The reason is 
that NSEC deals with identities in tree-space, NSEC3 deals with 
identities in a flattened space.  I.e., you can tell how 
a.b.c.example. and c.example. are related according to the tree, but 
what can you tell about 1294753.example. and 938424.example.?  (I 
attached "example" to illustrate that these are domain names.)

...For those following the exercise, this is not a conclusion, but my 
hypothesis is that NSEC3 with a null salt is not a good indicator of 
NSEC3 with a salt.

>(mistakes below are all mine).

I agree that the CE is the clue you need.  But when comparing the 
hash of the name desired and the hash of its CE, what can you tell 
from two seemingly random numbers?

>qname is equal to the signers name, see NSEC3 draft for the specifics).

So, you are counting on the validator having to pick up the slack, 
i.e., having to do more work to confirm the structure of the 
tree-space from the flattened hash-space, relying on the constrained 
nature of domain relationships.  (Aka, guess-and-test.)

What if the zone is multi-label deep?

example.
*.example.
a.b.c.d.example.
z.x.c.d.example.
e.f.g.h.example.
i.j.g.h.example.

And I query for a.b.c.d.e.g.g.h.example.?

I should get (NSEC-speak):

z.x.c.d.example. NSEC e.f.g.h.example. to prove that the name isn't 
there, plus establish g.h.example. as the CE.  The CE is an empty 
non-terminal.  To show that there is no *.g.h.example., well, I have 
already done that here, as it takes the same record.

NSEC3 (still) adds records to the empty non-terminals, right?

Let's assume this hash value table then:

example.                   21
*.example.                 39
d.example.                 12
c.d.example.               23
b.c.d.example.             48
a.b.c.d.example.           14
x.c.d.example.             2
z.x.c.d.example.           10
h.example.                 26
g.h.example.               13
f.g.h.example.             17
e.f.g.h.example.           5
j.g.h.example.             11
i.j.g.h.example.           4

I also need to define these hashes as these are the ones the 
validator has to guess.

g.g.h.example.             8
e.g.g.h.example.           22
d.e.g.g.h.example.         19
c.d.e.g.g.h.example.       6
b.c.d.e.g.g.h.example.     50
a.b.c.d.e.g.g.h.example.   30

So I would need:

13 NSEC3 14 to show there's a g.h.example.
5  NSEC3 10 to show there's no g....=8
21 NSEC3 22 to show there's no e.g...=22
17 NSEC3 21 to show there's no d.e.g...=19
I've already shown there's no c.d.e.g.g...=6
48 NSEC3  2 to show there's no b.c.d.e.g.g...=50
26 NSEC3 39 to show there's no a.b.c.d.e.f.g...=30

Note that "z.x.c.d.example. NSEC e.f.g.h.example." proves all of that in one.

That's 6 NSEC's to show the CE and prove it is a CE.  (The * proof is 
trivial.)  The problem is that the hashing "destroys" the efficiency 
of hierarchy.

There are details of the records too, zone cut things.  But I'll stop 
here and let someone pick apart my faulty logic.

(I feel deju vu here - I think I typed this message a few years ago 
too.  I know I did, but I can't find it easily in the archives.)

>NSECs. One to prove CE and one to prove absence of *.CE.

Either way, that's the goal, in showing that the algorithm of 4.3.2. 
is properly followed.

PS - A CE can own an NS set without an SOA set only when the query 
type is DS and maybe NSEC and RRSIG.  Humph.
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                                +1-571-434-5468
NeuStar

Nothin' more exciting than going to the printer to watch the toner drain...

---

From: Roy Arends <[email-masked]>
Date: Tue, 18 Apr 2006 22:44:40 +0200

> attached "example" to illustrate that these are domain names.)

For the method I tried to show it does not matter. The method is: assert a 
CE and prove it. Asserting the CE is done differently for NSEC than for 
NSEC3. I was not trying to describe a general one size fits all magic 
algorithm.

> already done that here, as it takes the same record.

'zactly.
 
> NSEC3 (still) adds records to the empty non-terminals, right?

Right.

> 26 NSEC3 39 to show there's no a.b.c.d.e.f.g...=30

Wrong.

The response would include 

13 NSEC3 14 to show there's a g.h.example.
5  NSEC3 10 to show there's no g.g.h.example.

And that is the beauty of the closest encloser. Since you've proved that 
g.h.example is the closest encloser, by showing g.g.h.example does not 
exist, you don't have to prove anything CLOSER exist. 

Since there is no g.... there is no e.g... no d.e.g    etc etc etc.

> Note that "z.x.c.d.example. NSEC e.f.g.h.example." proves all of that in 
one.

Sure.

> That's 6 NSEC's to show the CE and prove it is a CE.

No. I guess you misunderstood the general concept.

> (The * proof is 

Hope I've done it.  Please read the NSEC3 draft.

Roy

---

From: Edward Lewis <[email-masked]>
Date: Wed, 19 Apr 2006 12:48:39 -0400

>exist, you don't have to prove anything CLOSER exist.

Okay, it's not as bad as I thought.  The second NSEC3 record to me is 
a significant difference from the NSEC approach, the difference is 
caused by losing the tree structure in hashing.

I still wonder what the impact of the validator's guessing of the 
"meaning" of the CE hash will be on performance, as well as the rules 
at the cut points.  (The latter is also a problem with the NSEC, you 
need to know if you have the upper or lower NSEC in the proof and if 
it is the right one.)
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                                +1-571-434-5468
NeuStar