Subject: Re: DNSSEC wildcard optimization.

From: Robert Elz <[email-masked]>
Date: Mon, 04 Nov 2002 17:38:54 +0700

Date:        Tue, 29 Oct 2002 11:42:00 -0500
    From:        <[email-masked]>
    Message-ID:  <5.1.1.6.2.20021029113010.018fe478@localhost>

  | Take following example
  | *.foo
  | c.b.foo.
  | 
  | There is no RR at name b.foo.
  | does the wildcard match a.b.foo or does the presence in of b.foo in c.b.foo
  | terminate the wild card matching rule ?

The latter, no match.   This isn't even slightly unclear.   1034 refers
to names (labels actually) only, and whether they exist or not, not to
whether there's any data attached to them.

The only way this can be confusing is if you somehow allow yourself to
believe that a name can't exist without data attached to it.   There is
nothing in the DNS specs that would lead to that conclusion (though it is
true that there's no way to generate a leaf label without attached data).

kre

--
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, 4 Nov 2002 10:31:35 -0500

I don't mean to argue with Robert, but I'd like a clarification.

>whether there's any data attached to them.

Could you give a document citation saying this?  If it is there, it 
would be useful.  For some reason, I haven't found it.

-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                          +1-703-227-9854
ARIN Research Engineer

---

From: Robert Elz <[email-masked]>
Date: Wed, 06 Nov 2002 19:56:14 +0700

Date:        Mon, 4 Nov 2002 10:31:35 -0500
    From:        Edward Lewis <[email-masked]>
    Message-ID:  <a05111b03b9ec42e28e96@[192.149.252.234]>

  | Could you give a document citation saying this?  If it is there, it 
  | would be useful.  For some reason, I haven't found it.

1034 4.3.2

         c. If at some label, a match is impossible (i.e., the
            corresponding label does not exist), look to see if a
            the "*" label exists.

The "ie" explains exactly what matters.   That step is the only place
where the wildcard is consulted.   "label does not exist" is it.

kre

---

From: Edward Lewis <[email-masked]>
Date: Wed, 6 Nov 2002 10:06:18 -0500

I love it when specification writers hide details in parenthesized 
expressions.   It just adds so much to a coder's quality of life.

So I suppose that the below passage is saying:

if QNAME is a.b.c.d.e and the zone has z.x.c.d.e (but nothing with 
abcde nor bcde and no data at cde):

looking at the tree:

      1st iteration      | 2nd iteration     | 3rd iteration
      search result      | search result     | search result
   e  abcde  branch to d | bcde   br to d    | cde    br to d
   |                     |                   |
   d  abcde  branch to c | bcde   br to c    | cde    br to c
   |                     |                   |
   c  abcde  no branch   | bcde   no branch  | cde    exact match----\
   |\                    |                   |                       |
   x y                   |                   |                       v
   | |                   |                   |
   z w

a.b.c.d.e - a shorter match is possible (?-guessing)
b.c.d.e - a shorter match is possible (?-ditto)
c.d.e - an exact match exists, but no data sets match

(QTYPE is not a member of the set of types at cde = the empty set.)

I think the problem here is lack of clarity in "a match is 
impossible" until you break it down pictorially.

---

From: Robert Elz <[email-masked]>
Date: Thu, 07 Nov 2002 14:33:54 +0700

Date:        Wed, 6 Nov 2002 10:06:18 -0500
    From:        Edward Lewis <[email-masked]>
    Message-ID:  <a05111b07b9eedbd1d0ce@[192.149.252.234]>

  | I love it when specification writers hide details in parenthesized 
  | expressions.   It just adds so much to a coder's quality of life.

Yes.   Saying that 103[45] aren't perfect isn't news...   But nor were
lots of RFCs of that vintage.

  | So I suppose that the below passage is saying:

Sorry, I can't interpret your explanation, something has gotten lost
somewhere.

But the algorithm is simple.   You have a DNS name tree, and a QNAME.
Start at the rhs of the QNAME, and the root of the tree.   Match the
rightmost label in the QNAME against the sub-domains of the root.

Each time you get a match (equality) you remove (figuratively) the
label you just found and move down the tree to its node.   If that
leaves an empty QNAME, then you return whatever (appropriate) data exists
at the node you're at (just moved to) (ie: success).   (If you're not
auth for the node, and not recursive, then "appropriate" would be a referral).

When you don't get a match (ie: there is no sub-domain of the current node
in the tree that is exactly the same (after case independence is allowed for
of course) as the label you have from QNAME), what you do depends upon your
auth status for the zone containing the node in question.   If you aren't
auth, then you send a referral (or if you're being recursive, you make a query).

If you are auth, then you look and see if the current node in the tree
(and no others) has a '*' sub-domain in the zone (ie: a wildcard exists).
If it does, then you use whatever data (RRs) exist for the wildcard as
the answer for the (whole) QNAME from the query.   If there's no wildcard
directly under the current node, then you NXDOMAIN.

Note: this explanation assumes a slightly different data structure than the
one assumed by 1034, but the effect is the same I believe.

  | I think the problem here is lack of clarity in "a match is 
  | impossible" until you break it down pictorially.

It just means "there is no label equal to the one being sought".

kre

---

From: "Olaf M. Kolkman" <[email-masked]>
Date: Thu, 7 Nov 2002 09:32:59 +0100

FYI, in Apendix A.1.2. of version 01 of the draft (still in the drafts
queue but available on:
http://www.ripe.net/disi/Notes/draft-olaf-dnsext-dnssec-wildcard-optimization-01.html=anchor17)

I have added an example of the denial of wildcard proof as, I think,
it is supposed to be given. As it is bind 9.3s20020722 returns a few
answers to many. I hope that the argumentation is clear enough, and
correct.

--Olaf

PS. In version 01 we have tried to clarify servers MAY choose to not
use the optimizations but that resolvers MUST understand the
optimisation.  Besides we have changed the typecode from SIG to
NOWILD, which had as a consequence that the optimization takes place
when the bit is set to 1 iso 0. Finally DDNS considerations where
added.

PSS. Roy and Johan did not have a change to look at the document before
the deadline, all errors that sneaked in after 00 are to blame on me. :-)

--------------------------------------------| Olaf M. Kolkman
                                            | www.ripe.net/disi

---

From: Ólafur Guðmundsson<[email-masked]>
Date: Fri, 08 Nov 2002 16:52:42 -0500

>the deadline, all errors that sneaked in after 00 are to blame on me. :-)

After reading this much improved version I realized there are
three possible paths forward from standards perspective:
         1. Do nothing and require wildcard proof in all cases
         2. Adopt something like this draft that always minimizes the
                 number of records sent.
         3. Adopt a simpler approach, in which the NXT signals if a wild
                 card EXISTS in the zone. In this case full wild card
                 proof is needed for all answers for the zone even
                 if no wild card matches or if the wild card only matches
                 a small part of the zone.

The ONLY reason for adopting #2 or #3 is if the savings on the wire are
going to be significant. In order to answer that we need some idea about
how widespread the use of wild cards is and coverage inside the
zone. (I have no idea how to derive this information).

If the feeling is that wild cards are not frequent and when present they
cover most of the zone (eg *.<zone> is more common than *.<some>.<zone>)
then approach #3 may effectively yield the same savings (on the wire) as
#2.

         Olafur

---

From: "Olaf M. Kolkman" <[email-masked]>
Date: Sat, 9 Nov 2002 07:10:29 +0100

Note that scheme #3 can be adopted without major changes to the
current draft (that is, with a clarification here and there). The flag
as it is defined now basically is a message from the zone owner to the
resolver saying 'you can stop further denial of wildcard proof'. If it
is on a resolver does not have to do further denial of existence proof,
if it is off you have to fall back to 2535 style proof.

If do not want to make things difficult for dynamic zones with
wildards than toggling the bit for the whole zone as soon as a
wildcard appears or disappears will work.

In other words, from resolver perspective nothing needs to change to
implement #3, from server side perspective it needs to be made more
explicit that toggling the bit zone-wide is an option too.

--Olaf