Subject: Re: relevent?

From: Simon Josefsson <[email-masked]>
Date: Sat, 22 May 2004 01:55:06 +0200

Mark Andrews <[email-masked]> writes:

> 	You need to know what names exist to determine which wildcard
> 	to use.  NSEC provides this information in the owner and next
> 	names (yes both of these are required not just the next name).
>
> 	For NO/NSEC2 the information required to determine this has
> 	to be explicitly provided.
>
> 	The actual set of proofs reqired are
>
> 		!f.com + !*.com 
> 	or
> 		!e.f.com + !*.f.com + %f.com
> 	or
> 		!d.e.f.com + !*.e.f.com + %e.f.com
> 	or
> 		!c.d.e.f.com + !*.d.e.f.com + %d.e.f.com
> 	or
> 		!b.c.d.e.f.com + !*.c.d.e.f.com + %c.d.e.f.com
> 	or
> 		!a.b.c.d.e.f.com + !*.b.c.d.e.f.com + %b.c.d.e.f.com
>
> 	! == not exist
> 	% == exist

And how is it impossible for NO/NSEC2 to support this?  How I see it
is that the verifier would compute a hash of all the following
strings:

 a.b.c.d.e.f.com
 *.b.c.d.e.f.com
 *.c.d.e.f.com
 *.d.e.f.com
 *.e.f.com
 *.f.com

The hashes for the positive proofs are also needed, i.e.:

f.com
e.f.com
d.e.f.com
c.d.e.f.com
b.c.d.e.f.com

Using those hash values, together with the returned records, the
client can discover which of your clauses hold (if any).  For example,
let's say we have the following (abbreviated hash values to simplify
reading, imagine they are full length SHA-1 hashes):

H(a.b.c.d.e.f.com) =  181
H(*.b.c.d.e.f.com) =  38383
H(*.c.d.e.f.com)   =  3292
H(*.d.e.f.com)     =  4959
H(*.e.f.com)       =  606
H(*.f.com)         =  1194

H(f.com)           =  5271
H(e.f.com)         =  14
H(d.e.f.com)       =  596
H(c.d.e.f.com)     =  94984
H(b.c.d.e.f.com)   =  903

Now let's assume the query is a.b.c.d.e.f.com and the returned NO
records are:

$ORIGIN _no.f.com
150 IN NO A 200  ;; the main proof that a.b.c.d.e.f.com (181) does not exist
;; Additional proofs:
550 IN NO A 650  ;; proves d.e.f.com (596) does not exist
550 IN NO A 650  ;; proves *.e.f.com (606) does not exist  (by chance, same record)
14  IN NO A 50   ;; proves e.f.com (14) exists

The verifier is able to discover that one out of all relevant wildcard
situations apply, in this case the third of your clause.  To do this
it simply iterates over all possible candidates (a small number).  The
client can now trust that a specific a.b.c.d.e.f.com do not exist, and
that e.f.com do exists but there is no d.e.f.com nor *.e.f.com.  So it
is able to authenticate denial of existence for ab.c.d.e.f.com.

If I'm going to understand why NO/NSEC2 doesn't work, please give more
details.

Thanks,
Simon

--
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: Ben Laurie <[email-masked]>
Date: Mon, 24 May 2004 16:19:06 +0100

> If I'm going to understand why NO/NSEC2 doesn't work, please give more

NSEC2 does work (at least in this respect), but NO didn't. The 
difference is the EXISTS record, and the problem it solves is that 
(despite terminology) the closest encloser may not actually exist (that 
is, there may not be an RR with that exact name, just one with a longer 
name - or, to put it another way, the closest encloser can be an empty 
non-terminal).

We could demonstrate this, I guess, with hashes rather than EXISTS 
records by not _actually_ having an EXISTS record, just claiming it in 
the RR types field of NSEC2 - or even claiming no RR types at all. 
However, whilst this might be neater, it does nothing to hide the 
closest encloser (clearly, since a resolver needs to know exactly what 
it is), so its just another way of expressing the same thing. It also 
makes the logic for NSEC2 rather different from NSEC and, since it seems 
clear that the future is not likely to replace NSEC with NSEC2, but 
rather to offer them as alternatives, this would seem (to me) to be an 
unnecessary burden on implementers.

I suppose it is also worth saying that it wouldn't reduce the size of 
the zone, either, since you'd be swapping an EXISTS record for an NSEC2 
record.

Cheers,

Ben.

---

From: Simon Josefsson <[email-masked]>
Date: Mon, 24 May 2004 19:15:21 +0200

Ben Laurie <[email-masked]> writes:

>> The verifier is able to discover that one out of all relevant
>> wildcard situations apply, in this case the third of your clause.
>> To do this it simply iterates over all possible candidates (a small
>> number).  The client can now trust that a specific a.b.c.d.e.f.com
>> do not exist, and that e.f.com do exists but there is no d.e.f.com
>> nor *.e.f.com.  So it is able to authenticate denial of existence
>> for ab.c.d.e.f.com.  If I'm going to understand why NO/NSEC2
>> doesn't work, please give more details.
>
> (despite terminology) the closest encloser may not actually exist
> (that is, there may not be an RR with that exact name, just one with a
> longer name - or, to put it another way, the closest encloser can be
> an empty non-terminal).

I'm sorry to be dense, but I don't follow how NO didn't work.  What
was wrong in the algorithm verifiers can follow to prove non-existence
using NO records in my previous message?

Don't get me wrong, I'm not trying to push a NO solution (all I have
proposed is to drop one sentence in the security considerations of the
current specifications), but since we're discussing it, I'd might as
well try to learn something.

Thanks,
Simon

---

From: Simon Josefsson <[email-masked]>
Date: Mon, 24 May 2004 23:42:15 +0200

Ben Laurie <[email-masked]> writes:

> The problem is that if (say), in your example, e.f.com only exists by
> virtue of an RR for x.e.f.com, then there will be no NO record for
> e.f.com. This is why I had to invent the EXISTS record.

Ah, I see.  Thanks for explaining!  Edward Lewis' suggestion to (in
this example) populate the otherwise empty node e.f.com with a NSEC2
RR sounds like something that might be simpler.

Thanks,
Simon