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

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

At 17:57 +0200 4/18/06, Roy Arends wrote:

>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.

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.

>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).

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?

>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, 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?


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.)

>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.

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

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

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

4/18/2006 8:10:51 PM
comp.protocols.dns.std 2986 articles. 0 followers. Post Follow

0 Replies

Similar Articles

[PageSpeed] 4