Subject: nsec2 example

From: Edward Lewis <[email-masked]>
Date: Mon, 24 May 2004 11:40:10 -0700

(Apparently there's been a thread on NSEC2 on namedroppers.  I 
haven't read it.)

I was asked to look at the NSEC2 proposal.  It's hard to give a 
theoretical analysis of this, so I plucked one example to run against 
it.  I picked an example that I think would present a problem.  I'll 
list the example as well as a few thoughts.

Here's the sample zone I am using:

@       SOA, other stuff; @ is the name of the zone (="example.org.")
*.f     some stuff
d.e.f   some stuff
z.e.f   some stuff

For the purposes of the example, assume every name above has AAAA 
records, as well as all queries, and is in class IN.

I'll also make these assumptions.  I'm going to assume the hash of 
each name is:

hash (@) = 98
hash (*.f) = 17
hash (z.e.f) = 138
hash (d.e.f) = 347

So, the full zone has:

@       SOA, other stuff
*.f     some stuff
d.e.f   some stuff
z.e.f   some stuff
17      NSEC2
98      NSEC2
138     NSEC2
347     NSEC2

(Hopefully I have this correct.  Ben?)

Let's look at a query for a.b.c.d.e.f(.@) AAAA, IN.  Obviously, it 
doesn't exist and is not subject to the wild card synthesis. 
Graphically I see:

                @
                |
                f
               / \
               * e
                / \
                d z
               .
               c
               .
               b
               .
               a

"|,\,/" are links in the tree.  "." is a non-existent link, e.g., 
something below any leaf of the tree. (BTW, because of this, I can't 
imagine that the EXIST RR is needed.  The only nodes that can be 
closest enclosers in a negative answers have to "be there." 
Otherwise, I'd have fallen off the tree earlier.  DNS does not have 
terminal non-empty nodes.)

So, to prove that there is no data to return to my answer, 
specifically that a name error has occurred, the following has to be 
demonstrated:

1) a.b.c.d.e.f does not exist.  (Let's call the hash of it "217")
2) b.c.d.e.f does not exist.  (Let's call the hash of it "130")
3) c.d.e.f does not exist.  (Let's call the hash of it "87")
4) d.e.f does exist
5) *.d.e.f does not exist.  (Let's call the hash of it "112")

To demonstrate this, the response to the name error has to contain 
the following NSEC2 RR's:

1) 138 NSEC2    (because 138 < 217 < 347)
2) 98 NSEC2     ( 98 < 130 < 138 )
3) 17 NSEC2     ( 17 < 87 < 98 )
4) 347 NSEC2    ( 347 = 347 ) - demonstrating that this exists
5) optimized out 98 NSEC2 ( 98 < 112 < 138 )

(At this point, I should ask - is the above example and understanding 
of the NSEC2 RR draft correct?  If not, then the rest of this isn't 
worth reading at this point.)

It seems that this approach does convey the needed information for 
this example.  I suspect that if there was a wild card synthesis 
involved, then #5 is replaced by the results of the synthesis.

My initial concern was that the client can't be sure that an 
inappropriate NSEC2 RR was inserted, possibly via a replay attack (of 
valid data).  Well, it seems unlikely, because both the client and 
server will need to agree on "what needs provin'" and are just 
exchanging evidence for the proof.

What is lost in hashing is the structure of the tree.  Hashing is a 
mapping that flattens an "object".  Because of the flattening (it 
could also be attributed to lossy compression) more information is 
needed to show the structure.  This is manifested in the difference 
between needing just one or two NSEC RR's (or NXT's) and the need for 
extra NSEC2 RR's.  An NSEC RR showing there is no name from d.e.f to 
z.e.f would be all that is needed to prove points 1-5.  In this 
example, we need 4 distinct NSEC2 RR's.

The upper limit of NSEC2 records is linearly proportional to the 
number of labels from the closest encloser to the QNAME.  I am a bit 
worried that this is determined by the querier - I mean it is, but 
that it is worries me.  Hypothesis: this is a potential DOS 
vulnerability.  E.g., let's say there is no arin.net.  If you ask the 
.net servers for a.b.c.d.e.f.g.h.arin.net, then the .net server has 
to perform 8 - 10 hash calculations and include about that many 
records in the reply.

As an aside unrelated to the previous, the use of hashed names 
"changes the shape of the tree" involuntarily from the point of view 
of the administrator.  I'm not sure that this is a problem, but 
thought it should be mentioned.  In the above example, 17.@ is 
introduced into the zone.  Granted, 17 is a lot prettier than a real 
20 byte SHA-1 hash, but what happens is that wild card synthesis may 
be altered because of these hash names.  E.g., if there was a "*.@" 
in the zone, then the answer to "a.17.@, IN , AAAA" is altered.  The 
synthesis isn't applied because of the blocking (hash) name.
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                            +1-703-227-9854
ARIN Research Engineer

Even the voices inside my head are refusing to talk to me anymore.

--
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/>