Subject: Re: DNSSEC wildcard optimization.

From: "Olaf M. Kolkman" <[email-masked]>
Date: Tue, 22 Oct 2002 11:05:13 +0200

I'd like to invite some feedback/comments on this draft before
presenting it in Atlanta. Note, if this is to be implemented it will
need to piggy-back on on the DS transition as it is not backwards
compatible with RFC2535 specs.

>  Below is a link to a document describing an optimization to the
>  wildcard algorithm resulting in the need for only 1 NXT/SIG for when
>  there are no wildcards in the zone. Even if there are wildcards in the
>  zone 1 NXT/SIG may be sufficient.
> 
>  http://www.ripe.net/DISI/Notes/draft-olaf-dnsext-dnssec-wildcard-optimization-00.txt

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

--
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: Daniel Massey <[email-masked]>
Date: Tue, 22 Oct 2002 15:58:16 -0400

Hi,

I think this a very good idea and I would also like to propose a minor
change....  what if the NTA bit says no wildcards apply to the name
space covered by this NXT (rather than saying no wildcards in this
zone)

An initial pass came up with some very minor concerns:
    - with the per zone bit, various TTL/caching and misconfig scenarios can
       occur where one NXT in the zone has the bit set and another NXT 
does not
   - with the per zone bit, zones that use wildcards are screwed even if 
the
     wildcard only covers a very small part of the zone
  - the semantics of the NXT change slightly. conceptually the NXT was 
saying
    something about a particular namespace region.  now with the per 
zone bit it
    says something about a namespace region and something about the zone.

So suppose instead the NTA bit just says that no wildcard applies in the 
NXT's
namespace.   For example, a.example.com NXT c.example.com +NTA bit
says "no names exist between a.example.com and c.example.com AND no
wildcards apply for names between a.example.com and c.example.com".
This is the only NXT you need to send to prove b.example.com does not
exisist (and it works even if the zone contains *.d.example.com)

Dan

---

From: Daniel Massey <[email-masked]>
Date: Tue, 22 Oct 2002 16:56:13 -0400

> space covered by this NXT (rather than saying no wildcards in this

ignore my "minor change" since I misunderstood when the
bit is set.    This draft is a very good idea as is
and helps greatly with wildcard processing.

Thanks,
Dan

---

From: Ólafur Guðmundsson<[email-masked]>
Date: Wed, 23 Oct 2002 11:45:36 -0400

>compatible with RFC2535 specs.

1. Overloading the SIG bit, in my mind is a "BAD" idea.
I think it is a better design for humans and software to explicitly
state that wild card may apply in the gap between the left hand side
name and the right hand side name of an NXT. We have plenty of bits
to use including the following undocumented type codes
    EID             31 Endpoint Identifier                    [Patton]
    NIMLOC          32 Nimrod Locator                         [Patton]
    ATMA            34 ATM Address                         [Dobrowski]
    SINK            40 SINK                                 [Eastlake]

2. I think the bit should have a more explicit name say "WILD" or "WILDC",
NTAS looks like misspelled NAT.

3. The document does not address at all the issues for dynamic zones
that have wild cards. In this case a creation/deletion of a name can
require the resigning of many NXT records.

4. RFC1035 wild card algorithm is unclear and needs clarification,
publishing this protocol change without fixing the specification is not
prudent, and I encourage the authors on taking on the clarification effort.

5. There is a significant misunderstanding in the community on how
wildcards apply. At a DNSSEC workshop at ARIN earlier this month for
DNS administrators at ISP's, I polled the room about expected answers
in the following setup
*.foo  MX
a.foo  A

Q: a.foo. MX
Majority of people answering thought wildcard applied.

Q: b.a.foo MX ?
slim majority of the people that answered said that the
expanded wild card applied.

Correct answer is wild card does NOT apply in either case.

Based on this and other evidence that I have indicates that wild card
usage is to large extent based on misunderstanding.
There are examples where wild card MX records are used to create mail
domains that exist without any DNS records such as eng.sun.com.
Thus if the misunderstanding is corrected and we explain to the few
application communities that are using wild cards in a legit way
to push names out of DNS, what the DNS problems are, maybe we can make 
wildcards go away.  Furthermore a simple tool that populates a zone
with MX records at all names that have address will be more within
community expectations than wild card is.

6. Overall, IFF wildcards are needed then something like this will help
DNSSEC a lot.

         Olafur

---

From: Roy Arends <[email-masked]>
Date: Wed, 23 Oct 2002 18:48:42 +0200 (CEST)

>     ATMA            34 ATM Address                         [Dobrowski]

Sure, we can also request a new, previously unused type code, if that
clears the path a little. Plenty left.

> NTAS looks like misspelled NAT.

That new typecode can be called "WILD" or "WILDC".

> require the resigning of many NXT records.

I'll look into that one. I imagine the costs are larger then dynups in
dnssec zones without wcard optimization. I don't really know.

> community expectations than wild card is.

The draft proposes optimization, not a textbook definition how wildcards
work, definitly not on why one might use them, though I agree that the
1034/5 description of wildcards left room for improvement.

> 6. Overall, IFF wildcards are needed then something like this will help

Yes.

Roy

---

From: Rob Austein <[email-masked]>
Date: Wed, 23 Oct 2002 14:09:45 -0400

>     ATMA            34 ATM Address                         [Dobrowski]

At the risk of suggesting something insufficiently baroque:

If overloading the SIG code is bad, then please just allocate a brand
new type code for this purpose and have done with it.

["Don't tug on that, you never know what it might be attached to."]

---

From: Edward Lewis <[email-masked]>
Date: Wed, 23 Oct 2002 14:38:59 -0400

>I'd like to invite some feedback/comments on this draft before

Be careful what you wish for.

I have a few problems with the draft, although I think y'alls are on 
to something.

I think the first thing that should be cleared up is that:

It would be good for the signer to indicate that for an NXT's span, 
no wildcard match is available.  (Need to clarify what a "span" is.)

Ignoring opt-in for the time being, when an NXT is generated (whether 
by the off-line signer or the dynamic update signer), the signer can 
reliably determine what wildcard applies to the span of the names 
involved.  E.g.:

       ownername NXT nextname typemap

There are two kinds of names that don't *explicitly* exist between 
ownername and nextname (both of which do explicitly exist in the 
zone).  One kind is subdomains of ownername and the other kind is 
sibling domains.  The distinction is that if there is a wildcard that 
would cover the non-explicit sibling domains  in the range the same 
wildcard would not cover the non-explicit subdomains of ownername.

There is the special case of the ownername being a wildcard itself, 
in which the same wildcard (=ownername) covers both kinds of 
non-explicit names.

So, it seems to me (and this is open to discussion) that the signer 
has the information to determine what wildcard applies to the range 
ownername - nextname.  If this is the case, a resolver could reliably 
determine whether to expect a wild card - because the signer 
indicates one and the queryname is not a subdomain of the ownername. 
(Is it true that only one wildcard will apply to all the sibling 
domains between the ownername and nextname?  Is this different if the 
ownername is also a wildcard?)

I think that the above concept needs to be better defined in the 
draft.  That is, assuming that the above concept is correct. 
(Discussion?)

Where I would like the text to be beefed up is to discuss the role of 
signing in determining whether a wildcard would apply on names 
between ownername and nextname.  Then there needs to be a discussion 
on what happens when preparing a response - i.e., once the server 
sees the indication that there is no wildcard, it can exit the 1034 
algorithm.  Finally, there should be a discussion on how resolvers 
treat the presence/abscence of the indication of wildcards.

Next topic: how to indicate the presence or absence of applicable 
wildcards.  Usurping yet another bit in the typemap is getting to be 
the port-80 of transport protocols.  We have three low-valued bits to 
play with - 0, NXT, and SIG.  If opt-in flys, it takes one of the 
three.  I think 0 has someother reserved value waiting it.  This 
proposal is saying the last of these bits is to be taken.  There's a 
cultural antipathy towards using the last bit in our community, 
usually for good reason.

Yet another topic: The draft should discuss the implication of 
dynamic updates on this.  Yes, there's no significant impact but it 
should be stated that the signing process (in a signed, dynamic 
update zone) will have to regenerate the NXT's anyway.  In addition 
to dynamic update, it would be interesting to run this proposal 
through the opt-in decision making process.  (I had a chat with David 
Blacka last week on opt-in that hasn't yet been fully processed.)

A question: What is a NXT dname (end of section 2)?  We should stick 
to the owner name, next name, and query name terms.

And, while I'm at it, another comment:  In the examples, there should 
be one set of examples showing the "normal" no-wildcard case.  Then a 
zone with the one wildcard (a la * MX ...).  And then a hairier 
example (as you have) showing cases where a wildcard gets blocked 
from application.

In summary - I am always skeptical to any optimization attempts at 
first.  Whenever you are adding an optimization you are inherently 
complicating the architecture and implementation.  At times the cost 
of the complication is offset by the gain in performance - but this 
isn't always so.  So a skeptical eye is needed first.
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                          +1-703-227-9854
ARIN Research Engineer

---

From: Olaf Kolkman <[email-masked]>
Date: Wed, 23 Oct 2002 21:28:20 +0200

* 1. Overloading the SIG bit, in my mind is a "BAD" idea.
 * I think it is a better design for humans and software to explicitly
 * state that wild card may apply in the gap between the left hand side
 * name and the right hand side name of an NXT. We have plenty of bits
 * to use including the following undocumented type codes
 *     EID             31 Endpoint Identifier                    [Patton]
 *     NIMLOC          32 Nimrod Locator                         [Patton]
 *     ATMA            34 ATM Address                         [Dobrowski]
 *     SINK            40 SINK                                 [Eastlake]
 * 

By introducing a new type one looses the packet size optimization as described
in section 1.2:

<quote>
   o  Packet size of answers reduce in most common cases; for the root
      zone the authority section only contains 1 NXT RR with associated
      SIGs instead of two NXT RRs with associated SIGs.
</quote>

Note that the extra NXT RR without the optimization of the new RR-TYPE
will need to come with 1 or more SIG RRs. I think that that warrants
the 'overloading' of the SIG in the  NXT bitmap. 

Out of curiosity: Why is overloading the SIG bit a "BAD" idea? Why is it
worse than overloading the NXT bit?

 * 2. I think the bit should have a more explicit name say "WILD" or "WILDC",
 * NTAS looks like misspelled NAT.

Agreed, seems the DNS protocol is running out of acronyms :-).  What
about NOWILD, if it is set there are no wildcards, which is more
intuitive than WILD. I welcome other ideas.

 * 3. The document does not address at all the issues for dynamic zones
 * that have wild cards. In this case a creation/deletion of a name can
 * require the resigning of many NXT records.

I will add a section on dynamic zones. In short:

When adding a regular name dynamically you do not need to
modify/generate more NXT rrs than in the non-optimized set. You just
need to change the previous NXT nxt-name to point to the name just
inserted and you will have to do determine if the NTAS bit needs to be
set for the new RR.

If one adds wildcards dynamically then you have to possibly modify a
larger number of NXT RRs. Those NXT RR can be identified as described
in the 2nd paragraph of section 2.

If adding wildcards dynamically is allowed by the protocol (an I don't
think there are any restrictions there) then I guess there is a choice
to not set the optimization bit at all for the zone and that choice
needs to be made explicit in the draft.

 * 
 * 4. RFC1035 wild card algorithm is unclear and needs clarification,
 * publishing this protocol change without fixing the specification is not
 * prudent, and I encourage the authors on taking on the clarification effort.
 * 

Agreed.

 * 5. There is a significant misunderstanding in the community on how
 * wildcards apply. 

I agree with that, I remember it took me a long time to fully
understand what was happening, and it is still a difficult topic to
explain clearly during courses. But the understanding and (ab)use of
wildcards are outside the scope of the draft. The draft assumes that
wildcards and DNSSEC go hand-in-hand.

 * 
 * 6. Overall, IFF wildcards are needed then something like this will help
 * DNSSEC a lot.

Has the discussion on that conditional ever converged?

--Olaf

---

From: Edward Lewis <[email-masked]>
Date: Wed, 23 Oct 2002 16:57:11 -0400

A look at opt-in and this.  Olaf asked for some more clarity in my 
comments, I thought I'd bring this to the list:

I just want to go through the mental exercise of thinking how opt-in 
impacts this. E.g.,

       *.b.com      TXT signed (opt-in)
       a.b.com      NS signed
       d.b.com      NS signed
       e.b.com      NS unsigned (opt-out)
       g.b.com      NS signed

QNAME=c.e.b.com -> no wildcard vs.
QNAME=c.f.b.com -> wildcard

but both are covered by the same "d.b.com NXT g.b.com opt-in."  Does 
this NXT indicate wildcard or no wildcard?  There is a conflict 
between name existence and opt-in signing.
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                          +1-703-227-9854
ARIN Research Engineer

---

From: Derek Atkins <[email-masked]>
Date: 23 Oct 2002 17:52:14 -0400

> between name existence and opt-in signing.

The flag indicates "wildcard POSSIBLE" or "wildcard NOT POSSIBLE".  If
the "wildcard POSSIBLE" is set, and you have opt-in, then you still
have this ambiguity.  However, if you have the "wildcard NOT possible"
bit set, then QNAME=c.e.b.com would return the NS record, and
QNAME=c.f.b.com would return NXDOMAIN.

-derek

PS: I should note that you don't specify which particular NXT records
are 'opt-in' vs. 'non-opt-in'.  The only one you specify is the
wildcard.  You don't say whether d.b.com. NXT g.b.com. is opt-in or
not.

-- 
       Derek Atkins
       Computer and Internet Security Consultant
       [email-masked]             www.ihtfp.com

---

From: David Blacka <[email-masked]>
Date: Wed, 23 Oct 2002 18:35:55 -0400

> between name existence and opt-in signing.

What conflict?  If the NXT is Opt-In, it does not matter what the NOWILD (or 
whatever it is called) flag is.  At least if the wildcard processing rules in 
the opt-in-03 draft are correct.

-- 
David Blacka    <[email-masked]> 
Sr. Engineer    Verisign Applied Research

---

From: Bob Halley <[email-masked]>
Date: 23 Oct 2002 15:53:26 -0700

> prudent, and I encourage the authors on taking on the clarification effort.

What is unclear?

> wildcards go away.

Some people are confused, certainly.  But I find it very hard to
believe that most uses of wildcards are erroneous or unwarranted.

Wildcards can be made to work with DNSSEC as it is.  Why don't we just
leave features like wildcards that people are already using in,
stop adding more features, and let it deploy?  Removing wildcards
from DNSSEC will discourage and delay deployment.

/Bob

---

From: David Conrad <[email-masked]>
Date: Wed, 23 Oct 2002 16:13:56 -0700

Olafur,

> 1. Overloading the SIG bit, in my mind is a "BAD" idea.

Modifying the DNSSEC specs in non-backwards compatible ways _yet again_ is a
"BAD" idea.

Can we please stop?  I would personally like to see DNSSEC deployed in my
lifetime.

> to push names out of DNS, what the DNS problems are, maybe we can make

Don't be silly.

Wildcards are seen as providing useful functionality.  Attempts to remove
them, regardless of the validity of the attempt, will get dragged down into
non-terminating IETF politics.

Given wildcards exist, any attempt to remove them from DNSSEC will simply
mean disincentives for DNSSEC deployment.  We do NOT need more disincentives
to deploying DNSSEC.

Can we please stop?  I would personally like to see DNSSEC deployed in my
lifetime.

I guess it would be too much to ask that if someone is going to propose
modifications to the DNSSEC specifications that those modifications MUST be
backwards compatible with the evolved (?) form of DNSSEC+DS?

By the way, just where is 2535bis?

Thanks,
-drc

---

From: Roy Arends <[email-masked]>
Date: Thu, 24 Oct 2002 04:45:35 +0200 (CEST)

> > prudent, and I encourage the authors on taking on the clarification effort.

It is not 1034/5 that is unclear, though the 2535 description of handling
secure wildcards is unclear.  Last time I looked a widely known
implementation of a DNS server did not get secure wildcards right.

You tell me what is unclear.

> from DNSSEC will discourage and delay deployment.

Since non-implemented secure wildcards is currently the default, how is it
that not implementing secure wildcards will delay or discourage deployment
? Why isn't it implemented by now ?

Roy

---

From: Edward Lewis <[email-masked]>
Date: Thu, 24 Oct 2002 12:50:23 -0400

>>  prudent, and I encourage the authors on taking on the clarification effort.

Perhaps the fact that the algorithm is in RFC 1034. ;)

>believe that most uses of wildcards are erroneous or unwarranted.

Amen.

If we can settle on a means to indicate in the NXT whether a span of 
names is or is not covered by a wildcard, then I see the wildcards in 
DNSSEC as a trivial problem.

During the signing process, the signer knows what exists between an 
NXT's ownername and the nextname in the NXT RDATA.  There are three 
possibilities floating now:

       non-existent names that are subdomains of ownername, which cannot
       ever be matched by a wildcard.

       unsecured delegations (per the opt-in proposal) which exist but are
       not secured.  (I'll defer a discussion on this implication to below.)

       non-existent names that are siblings of the ownername, which are
       eligible for a wildcard match, if one exists.  If one does, the signer
       can determine which applies - so the NXT can indicate definitively
       yes or definitively no IF there is a wildcard to be expected.

The latter case I think is pretty clear - if the wildcard isn't at 
one label up, there still is a need to prove it's not there before 
accepting a higher wildcard.

As far as unsecured delegations as per opt-in, there's a conflict 
between signed wildcards and unsecured names that is hanging out 
there, begging for more analysis and discussion.  But, neglecting 
opt-in, I'm beginning to be ever more convinced that wildcards and 
dnssec are not a problem.

I think it's best to defer the opt-in rathole to a new thread so as 
to not screw up threaded mail readers on this just yet.

---

From: Edward Lewis <[email-masked]>
Date: Thu, 24 Oct 2002 16:49:24 -0400

The author of this is obviously a moron.

(I bet that got y'alls attention.)

>       yes or definitively no IF there is a wildcard to be expected.

After chatting VoPOTS with Olaf, I realized I missed a case - a wild 
card may apply to just some of the siblings.

E.g. looking at a zone with this in it.

      *.c
    a.b.c
        f

a.b.c has the following non-existent labels in the span before f:

               z.a.b.c   -- a subdomain blocked from *.c
                 b.b.c   -- a sibling of a.b.c that matches *.c
                     d   -- a sibling of a.b.c that does not match *.c

Although the signer knows whether *, *.c or *.b.c is present and how 
much of the a.b.c to f span is covered by a wildcard, the signer 
can't anticipate the query name in advance when calculating a.b.c's 
NXT RR.  There's no algorithmic way to determine from just the query 
name, owner name, and the so-called WILDC bit over what part of the 
span a wildcard match applies.

Ergo - you can only way "there is definitely no wildcard" or there is 
"possibly a wildcard."  And ergo again, opt-in isn't going to create 
a special case.

Perhaps we should eliminate multi-label zones from DNS.  (Just kidding folks.)

---

From: Ólafur Guðmundsson<[email-masked]>
Date: Tue, 29 Oct 2002 11:42:00 -0500

> > prudent, and I encourage the authors on taking on the clarification effort.

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 ?

>believe that most uses of wildcards are erroneous or unwarranted.

How many people out there do *  MX ... and think they do not have to
put MX records at every host name ? (answer: a lot).

>from DNSSEC will discourage and delay deployment.

I buy this argument but,
The only new features being discussed are "DS" and "opt-in", there is
one clarification ("AD-secure"), one usage restriction "key-restrict" and
one optimization "wildcard presence signaling"

You are the one that got the AD ball rolling by forcing me and Brian
to write that one.
DS was caused by operational difficulties, Key-restrict motivation
is to separate DNS operation from other uses of KEY's (simplification),
Opt-in is about choice (or lack there off).
Once we have these all nailed down (I hope by end of November) there
MUST be a feature freeze in DNSSEC for a while.

         Olafur