Subject: Re: Proof of nonexistence for NSEC3

From: Edward Lewis <[email-masked]>
Date: Thu, 3 Mar 2005 11:02:36 -0500

For some reason I've popped open this message without reading any 
other parts of the threads on this.  Yet I am compelled to write...;)

At 15:18 +0000 3/3/05, Ben Laurie wrote:
>Following a revelation about NSEC3 nonexistence proofs, I have 
>proposed language to add to the I-D. Comments, please...
>
>"If a wildcard ownername appears in a zone, the wildcard label ("*")
>is treated as a literal symbol and is treated in the same way as any
>other ownername for purposes of generating NSEC3 RRs.  RFC 2535 describes the
>impact of wildcards on authenticated denial of existence.

In wcard, I've defined "asterisk label" for "*".

>In order to prove there are no wildcards for a domain, as well as no
>RRs that match directly, an RR must be shown for the closest encloser,
>and non-existence must be shown for all enclosers that could be
>closer.

More terminology that has to be fixed.  "In order to prove there are 
no wildcards (source of synthesis) applicable to a lookup..."  Also, 
by definition there cannot be enclosers closer that the closest 
enclosure.  I.e., you establish the closest encloser by showing that 
the span "beyond" it includes the sought name.

>If we are attempting to prove the non-existence of some domain,
>then in general the domain is of the form P.x.C where C is the closest
>encloser in the zone (there is always one, if nothing else, the apex
>of the zone), x is the label immediately preceding the closest
>encloser (again, there must always be one, since if there weren't then
>the domain would be C, which exists), and P is the (possibly empty)
>remainder of the domain. To prove the nonexistence of P.x.C, we must
>show that C exists, x.C does not exist and *.C does not exist. Because
>x.C does not exist, all possible closer enclosers and wildcards also
>cannot exist (if they did, there would at least be an empty
>non-terminal at x.C), so these three facts are always sufficient to
>prove the nonexistence of P.x.C.

The goal is to prove that there are no records to return in an 
answer.  One strategy is to show that the static parts of the tree 
which would have been the source of an answer (exact match, source of 
synthesis) do not exist.  Another strategy is to have the name server 
craft a "take my word for it, there's nothing."  I say this so that 
no one remains fixated on the existence question - that ain't the 
real problem.

Think of source of synthesis and closest enclosers in the dynamic 
context of a lookup.  They mean nothing with staring at the static 
tree of domains.

There is no x...in the tree.  I guess you mean that x is the most 
significant label in the sought name that does not match one in the 
tree?

I don't get the need to prove anything about P.x.C.  If x is in the 
tree, then x.C is the closest encloser.  If x isn't, then there isn't 
P.x either.

>In practice, then, we must show an NSEC3 record that encloses the
>hash of x.C, one that encloses the hash of *.C, and any RR owned by C
>(which could be an NSEC3, in which case it would be owned by the hash
>of C). A resolver verifying this proof would have to try longer and
>longer closest enclosers to determine which was being demonstrated as
>C, if an NSEC3 is presented. If any other RR was used, then C would be
>the owner. Once C has been determined, the resolver can easily check
>x.C and *.C against the proof."

In order to return an RCODE=name error when dealing with hashes 
instead of names, three stipulations have to be made.

1) You need to demonstrate that the hash of the searched name falls 
into a span of hashes not in the zone (not necessarily it's closest 
encloser).

2) You have to reveal (and prove) the closest encloser.

3) You have to show that the would-be source of synthesis has a hash 
that falls in to the span of hashes not in the zone.

Number 2 may be the trickiest part.

Maybe that's what you said...what do you mean by "[i]f any other RR 
was used..."?  RR as in the QTYPE?
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                                +1-571-434-5468
NeuStar

Achieving total enlightenment has taught me that ignorance is bliss.

--
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: Thu, 03 Mar 2005 17:06:31 +0000

Edward Lewis wrote:
> For some reason I've popped open this message without reading any other 
> parts of the threads on this.  Yet I am compelled to write...;)
> 

You mean we should change "wildcard label" to "asterisk label"?

> More terminology that has to be fixed.  "In order to prove there are no 
> wildcards (source of synthesis) applicable to a lookup..."  Also, by 
> definition there cannot be enclosers closer that the closest enclosure.  
> I.e., you establish the closest encloser by showing that the span 
> "beyond" it includes the sought name.

Sure. Perhaps I should change the wording to "an RR must be shown for 
the _alleged_ closest encloser" to make it clear?

> The goal is to prove that there are no records to return in an answer.  
> One strategy is to show that the static parts of the tree which would 
> have been the source of an answer (exact match, source of synthesis) do 
> not exist.  Another strategy is to have the name server craft a "take my 
> word for it, there's nothing."  I say this so that no one remains 
> fixated on the existence question - that ain't the real problem.
> 
> context of a lookup.  They mean nothing with staring at the static tree 
> of domains.
> 
> significant label in the sought name that does not match one in the tree?

Yes - as I said "x is the lebel immediately preceding the closest encloser".

> tree, then x.C is the closest encloser.  If x isn't, then there isn't 

This is almost my point precisely (up to now, people have thought you 
had to prove every possible encloser separately), except that C is in 
the tree and x.C isn't.

> In order to return an RCODE=name error when dealing with hashes instead 
> of names, three stipulations have to be made.
> 
> 1) You need to demonstrate that the hash of the searched name falls into 
> a span of hashes not in the zone (not necessarily it's closest encloser).

No, if the x.C (being one longer than the closest encloser) doesn't 
exist, then the searched named does not exist.

> 2) You have to reveal (and prove) the closest encloser.

Indeed, that is why you show an NSEC3 for (i.e. owned by the hash of) C 
(or some other RR owned by C) and show the nonexistence of x.C.

> that falls in to the span of hashes not in the zone.

And that is why you show the nonexistence of *.C.

> Maybe that's what you said...what do you mean by "[i]f any other RR was 
> used..."?  RR as in the QTYPE?

I mean that to prove the existence of C any RR owned by C suffices.

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

---

From: Edward Lewis <[email-masked]>
Date: Thu, 3 Mar 2005 12:22:57 -0500

>You mean we should change "wildcard label" to "asterisk label"?

Yeah.

>Sure. Perhaps I should change the wording to "an RR must be shown for the
>_alleged_ closest encloser" to make it clear?

That wording is also unclear.  (What RR? A TXT record?)  The response 
message needs to demonstrate to the validator/evaluator what the 
closest encloser is.

>Yes - as I said "x is the lebel immediately preceding the closest encloser".

Still confused.  "Preceding" from the root to the closest encloser? 
Or the label at which the match failed?

>This is almost my point precisely (up to now, people have thought you had to
>prove every possible encloser separately), except that C is in the tree and
>x.C isn't.

Once we understood the concept of the closest encloser, it became 
apparent that the higher (in the tree) enclosers are unimportant. 
'Course, this assumes the tree structure is apparent.

>No, if the x.C (being one longer than the closest encloser) doesn't exist,
>then the searched named does not exist.

Existence isn't the point.  It's whether there are answers available. 
You don't set a return code of name error when the answer is 
synthesized.

>And that is why you show the nonexistence of *.C.
...
>I mean that to prove the existence of C any RR owned by C suffices.

I guess the point I'm trying to make is that DNS is a client-server 
protocol.  It's more important to achieve the goal of information 
transfer than to bury ourselves in mathematics of proofs.

The server generates a response.  The server needs to know what 
statements are needed to express a certain result - such as an 
answer, a synthesized answer, no data available, or no applicable 
domain name.  The protocol does not assign different credibilities to 
stock and synthesized answers, the only reason the server indicates 
any difference is to demonstrate that it has dutifully followed the 
algorithm in RCFC 1034.

The response is interpreted by the client.  It is the one that 
"proves" to itself the assertions in the response.  It's up to the 
client to decide how to do the proof - e.g., take everything at face 
value.  A more prudent client would be looking for statements it can 
use to verify that the server followed the protocol.  Not for 
correctness, mind you, but to make sure that the message originated 
from an authoritative source.

I'm not picking on the math in the draft.  I'm picking on the tone of 
the description.  DNSSEC in 2065 and 2535 spent too much time trying 
to get the theory right and not enough time understanding that DNS is 
a client-server protocol.  I.e., it's not existence that I care 
about, it's whether there is an answer.
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                                +1-571-434-5468
NeuStar

---

From: Ben Laurie <[email-masked]>
Date: Fri, 04 Mar 2005 10:57:49 +0000

Edward Lewis wrote:
> message needs to demonstrate to the validator/evaluator what the closest 
> encloser is.
> 
> Still confused.  "Preceding" from the root to the closest encloser? Or 
> the label at which the match failed?

The label at which the match failed (surely this is obvious from the 
general form P.x.C?).

>> had to

Or lower, depending which way up you draw your trees ;-)

> You don't set a return code of name error when the answer is synthesized.

Point taken.

> statements are needed to express a certain result - such as an answer, a 
> synthesized answer, no data available, or no applicable domain name.  
> The protocol does not assign different credibilities to stock and 
> synthesized answers, the only reason the server indicates any difference 
> is to demonstrate that it has dutifully followed the algorithm in RCFC 
> 1034.
> 
> The response is interpreted by the client.  It is the one that "proves" 
> to itself the assertions in the response.  It's up to the client to 
> decide how to do the proof - e.g., take everything at face value.  A 
> more prudent client would be looking for statements it can use to verify 
> that the server followed the protocol.  Not for correctness, mind you, 
> but to make sure that the message originated from an authoritative source.
> 
> the description.  DNSSEC in 2065 and 2535 spent too much time trying to 
> get the theory right and not enough time understanding that DNS is a 
> client-server protocol.  I.e., it's not existence that I care about, 
> it's whether there is an answer.

OK, so are you saying that you agree that the response is sufficient, 
but you would prefer the way it is presented to be more client-centric?

Cheers,

Ben.

---

From: Edward Lewis <[email-masked]>
Date: Fri, 4 Mar 2005 09:10:10 -0500

At 10:57 +0000 3/4/05, Ben Laurie wrote:

>The label at which the match failed (surely this is obvious from the general
>form P.x.C?).

Part of the comment is that, no, it wasn't obvious.  It took me quite 
a few readings to get a grip on it.  The P.x.C form is rather alien - 
the notion that there's a 'P' hanging off an 'x' that doesn't exist.

>Or lower, depending which way up you draw your trees ;-)

Per RFC 1034, section 3.1:

"The domain name of a node is the list of the labels on the path from the
node to the root of the tree.  By convention, the labels that compose a
domain name are printed or read left to right, from the most specific
(lowest, farthest from the root) to the least specific (highest, closest
to the root)."

I've taken that to be "how DNS draws the tree."  It's also where I 
got the most/least specific terminology I used in wcard.

>OK, so are you saying that you agree that the response is sufficient, but you
>would prefer the way it is presented to be more client-centric?

Well, my comments were in response to the mail, I haven't made it 
through what's in the draft.  What I am encouraging is to take the 
mathematical lingo you are using and try to force it into the context 
of a client-server protocol, and in particular, using the verbiage 
built up in years of DNS documents.

The first step helps hammer out where wrinkles will need ironing, 
makes you think of the impacts at authoritative servers and caches, 
the impact of dynamic update, etc., the basic "corner cases."  The 
latter - using consistent terminology - makes it easier to get a 
quality review.

(Nothing of substance, more of a lecture I'm afraid.)
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                                +1-571-434-5468
NeuStar

---

From: Ben Laurie <[email-masked]>
Date: Fri, 04 Mar 2005 16:07:28 +0000

Edward Lewis wrote:
>> general
> Part of the comment is that, no, it wasn't obvious.  It took me quite a 
> few readings to get a grip on it.  The P.x.C form is rather alien - the 
> notion that there's a 'P' hanging off an 'x' that doesn't exist.

Better ways to express that are welcome!

> I've taken that to be "how DNS draws the tree."  It's also where I got 
> the most/least specific terminology I used in wcard.

Oh, then we both draw them the same way and I misunderstood your comment.

>> but you
> through what's in the draft.

The mail was what I intended to add to the draft.

> What I am encouraging is to take the 
> mathematical lingo you are using and try to force it into the context of 
> a client-server protocol, and in particular, using the verbiage built up 
> in years of DNS documents.
> 
> The first step helps hammer out where wrinkles will need ironing, makes 
> you think of the impacts at authoritative servers and caches, the impact 
> of dynamic update, etc., the basic "corner cases."  The latter - using 
> consistent terminology - makes it easier to get a quality review.
> 

Hmmm. Guess I'm buying you beer until I get substance then ;-)

Cheers,

Ben.