Subject: Re: [dns-operations] NXDOMAIN vs NODATA for suffixes of existing name

From: [email-masked]
Date: Mon, 17 Apr 2006 14:11:28 +0000

folks, i think florian's got a valid point here.

(i'm not cross-posting, i'm changing mailing lists for this thread.  i'll post
a summary back to dns-operations@ when namedroppers@ is done chewing on this.)

re:

> From: Florian Weimer <[email-masked]>
> To: [email-masked]
> Date: Mon, 17 Apr 2006 11:16:26 +0200
> Subject: Re: [dns-operations] NXDOMAIN vs NODATA for suffixes of existing
> 	name
> Sender: [email-masked]
> 
> * Paul Vixie:
> 
> > to me, b.example.net exists because that's what we decided for dnssec,
> 
> Post-RFC-4035, I assume?  Because RFC 4035 says, in section 3.1.32:
> 
> | Note that this form of response includes cases in which SNAME
> | corresponds to an empty non-terminal name within the zone (a name
> | that is not the owner name for any RRset but that is the parent name
> | of one or more RRsets).
> 
> This also follows from the prohibition of NSEC generation for empty
> non-terminals (section 2.3, "An NSEC record (and its associated RRSIG
> RRset) MUST NOT be the only RRset at any particular owner name."), as
> you would need such an NSEC RR for responding with NODATA.  This means
> that the draft-ietf-dnsext-wcard-clarify (thanks Peter and Edward!) is
> in conflict with DNSSEC (as a simple update of the DNSSEC spec is not
> possible).
> 
> Ah, draft-ietf-dnsext-nsec3 handles this case differently, maching the
> draft-ietf-dnsext-wcard-clarify.
> _______________________________________________
> dns-operations mailing list
> [email-masked]
> http://lists.oarci.net/mailman/listinfo/dns-operations

--
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: Mon, 17 Apr 2006 10:47:46 -0400

I don't get the point.  (I need clarification.)

I will say I don't understand the last paragraph of 3.1.3.2 in 4035 
(as quoted by Florian).  When it comes to name errors, empty 
non-terminals need not apply.

NSEC3 breaks rules.  It has to.  The reason is that when the design 
choices were make for NSEC (nee NXT), a set of rules were included 
assuming NXT and making NXR more reasonable.  Deviating from NSEC 
into NSEC3 means upending design decisions and rules set forth.

I don't see the conflict between DNSSEC and the wild card document. 
Maybe this is the missed point:

You don't need an NSEC at a name to prove it has no RRsets.

example.     NSEC a.example. soa ns nsec dnskey rrsig
a.example.   NSEC a.b.example. a txt nsec rrsig
a.b.example. NSEC c.example. a txt nsec rrsig
c.example.   NSEC example. ns nsed rrsig

These records indicate that there are 5 names in the zone, 4 of which 
have records. "b.example." does not have any records, not even an 
NSEC.  A query for "b.example. A" would get 0 answer records, and 
"a.example.   NSEC a.b.example. a txt nsec rrsig" in the authority 
section.  The verifier can infer that b.example exists (since 
a.b.example exists) and that by "pointing" past b.example, the NSEC 
says there is nothing to see at b.example.

At 14:11 +0000 4/17/06, [email-masked] wrote:
>>  Ah, draft-ietf-dnsext-nsec3 handles this case differently, matching the

-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                                +1-571-434-5468
NeuStar

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

---

From: Rob Austein <[email-masked]>
Date: Mon, 17 Apr 2006 13:38:45 -0400

> non-terminals need not apply.

The text in question:

   Note that this form of response includes cases in which SNAME
   corresponds to an empty non-terminal name within the zone (a name
   that is not the owner name for any RRset but that is the parent name
   of one or more RRsets).

DNSSECbis talks about existance and non-existance of -RRsets-; it does
-not- talk about existance or nonexistance of -names-.  The first
paragraph of 3.1.3.2 describe the case covered by this kind of
response: "the zone does not contain any RRsets matching <SNAME,
SCLASS> either exactly or via wildcard name expansion".

Ie, for the purposes described in 3.1.3.2, an empty node is an empty
node ("name error") whether it's terminal or not.  The proof described
in 3.1.3.2 applies regardless of the RCODE.  DNSSECbis does not cover
the RCODE, that'd have to be covered by a channel security mechanism.

This bugaboo about whether a name exists when there are no RRsets
attached to it has been a source of confusion for twenty years.
DNSSECbis takes pains to avoid it.  Please don't reintroduce it. :)

---

From: Roy Arends <[email-masked]>
Date: Mon, 17 Apr 2006 20:30:15 +0200

> > draft-ietf-dnsext-wcard-clarify.

Yes. During the Dallas IETF dnsext wg meeting I gave a presentation 
(rfc4035 omissions) on this exact point.

I noted that rfc4035's statement (3.1.3.2) is wrong. 

One example why this is wrong is that a resolver implementing negative 
caching will cease to resolve a.b.example if it previously received and 
cached a name error for the empty non-terminal b.example.

regards,

Roy

---

From: Roy Arends <[email-masked]>
Date: Mon, 17 Apr 2006 20:37:46 +0200

> SCLASS> either exactly or via wildcard name expansion".

If we're about to re-issue the term NAME ERROR to mean 'non-existance of 
RRsets" we should introduce a new rcode. Otherwise this is just confusing. 

> DNSSECbis takes pains to avoid it.  Please don't reintroduce it. :)

This confuses even more. 

So, what do you suggest the rcode (yeah yeah unsigned) is on the specific 
response that is covered by rfc 4035 3.1.3.2 ?

Roy

---

From: Edward Lewis <[email-masked]>
Date: Mon, 17 Apr 2006 14:46:04 -0400

>the RCODE, that'd have to be covered by a channel security mechanism.

My confusion is from the title of the section:
     "3.1.3.2.  Including NSEC RRs: Name Error Response"

When I read that I assume the section is all about situations with a 
return code of "name error."  That's why I say that the quoted 
paragraph is oddly placed.

>The quoted paragraph:

---

From: Rob Austein <[email-masked]>
Date: Mon, 17 Apr 2006 15:11:42 -0400

> RRsets" we should introduce a new rcode. Otherwise this is just confusing. 

None of the other three cases in 3.1.3 exactly corresponds to an
RCODE.  Why do you expect that this one will?

People, please -read- the entire section (3.1.3 and its children).
The cases (all four of them) are spelled out, and nowhere does it say
that -any- of this corresponds to any particular RCODE.

I guess some text about this (that these cases do not correspond to
RCODEs) needs to go into the bis clarification doc, since apparently
people are reading this as isolated paragraphs without checking the
immediately preceding definitions.

> response that is covered by rfc 4035 3.1.3.2 ?

RCODE zero or three, depending on whether the name is an empty
nonterminal or not, not that a validating resolver should care.

---

From: Edward Lewis <[email-masked]>
Date: Mon, 17 Apr 2006 15:35:30 -0400

>that -any- of this corresponds to any particular RCODE.

After doing that, I would conclude the 3.1.3 needs more work.  Not in 
content, but in language.  At least make "Name Error" mean the same 
thing in RFC 1035/1034 as in RFC 4035.

---

From: Roy Arends <[email-masked]>
Date: Mon, 17 Apr 2006 21:48:33 +0200

> RCODE.  Why do you expect that this one will?

Because NAME ERROR (in the 3.1.3.2 section title) is an explicit rcode. 

> that -any- of this corresponds to any particular RCODE.

Confusion happens when a document redefines (or re-uses) the term NAME 
ERROR, but apparently not talking about the rcode.....
 
> immediately preceding definitions.

This is a wrong assumption.

Wrt including NSEC in a response I expect that the sections under 3.1.3 
would cover all different response types including the NOERROR/NODATA 
response for an empty non-terminal. This NOERROR/NODATA response type is 
under the section that deals with (some definition of) NAME ERROR.

> nonterminal or not, not that a validating resolver should care.

The validating resolver might not care. But something talking to it might 
care. 

Roy

---

From: Rob Austein <[email-masked]>
Date: Mon, 17 Apr 2006 16:15:25 -0400

> thing in RFC 1035/1034 as in RFC 4035.

Well, the conditions in 3.1.3 don't exactly map to anything from RFC
1035.  As Roy may recall, at one point the DNSSECbis drafts had made
up terms for all of these, for precisely this reason.  We changed to
the current wording because the made up terms were unreadable.

So, while accepting your criticism, I'd phrase it a bit differently.
Serious question: what would you suggest as names for the four
DNSSECbis-specific conditions described in 3.1.3 and its children?

---

From: Edward Lewis <[email-masked]>
Date: Mon, 17 Apr 2006 16:47:23 -0400

>DNSSECbis-specific conditions described in 3.1.3 and its children?

I understand that desire to divorce the notion of names existence 
from RRset existence because of how negative answers work in DNSSEC, 
but I think you can't.  Well, completely divorce them, that is.

My personal way to classify the cases is:

1) For return code of "name error" - NSECs are needed proving that 
neither the sought name nor a source of synthesis exists.

2) For an answer count of 0 - NSECs are needed proving that either 
the sought name exists without a matching set or the triple of the 
sought name does not exist, a source of synthesis does, and there is 
no matching set (from which to synthesize).

3) For synthesized answers - NSECs are needed proving that the sought 
name does not exist but that there is a source of synthesis with a 
matching set (from which to synthesize).

I have three cases because the "answer count of 0" includes two of 
the original four cases.  (Mind you, this is all textual, the 
underlying content is okay.)

As DNSSEC is an extension to the base protocol, if we can show the 
extensions as building upon the response messages, we'll likely have 
a cleaner description.  (Granted, that's a hypothetical statement.) 
Likely - because we may discover hidden inconsistencies in the base 
specification as in the conflict of an NS RRset at a source of 
synthesis.

Of course, this is one way to answer this.  Maybe tomorrow I'd have 
answered differently.  The perspective I've adopted is from the 
protocol's architecture.  It might be better to describe this from 
the protocol server's state machine.  But that might be too obtuse as 
none of the rest of the documents use that perspective.

---

From: Rob Austein <[email-masked]>
Date: Mon, 17 Apr 2006 17:10:27 -0400

The organization we used in RFC 4035 is based on grouping the cases
that return identical NSEC attestations together.  I may be missing
something, but Ed's three case grouping doesn't appear to do that,
thus to my mind is at least as confusing as the current text.  Note
that even before DNSSEC we were well down the path of protocol that
had to be deduced from the packet rather than just being read off
cleanly (see, for example, the gyrations that Mark had to go through
in classifying RCODE 3 responses in RFC 2308).

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.

---

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

> 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

---

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

---

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