Subject: RE: NSEC version field (Re: NSEC2- and an Authenticated Denial M echanism Flag)

From: "Scott Rose" <[email-masked]>
Date: Tue, 1 Jun 2004 12:40:17 -0400

> -----Original Message-----
> From: [email-masked]
> [mailto:[email-masked]]On Behalf Of Geoffrey Sisson
> Sent: Tuesday, June 01, 2004 12:27 PM
> To: [email-masked]
> Subject: Re: NSEC version field (Re: NSEC2- and an Authenticated Denial
> M echanism Flag)
>
>
> Edward Lewis <[email-masked]> writes:
>
> > But the cost isn't limited to any kind of zones.  No matter what the
> > "shape" of the zone is, a mischievous client can construct a query
> > that force the server into computing hashes of N names.  E.g., let's
> > say 9.net doesn't exist.  I can ask for 1.2.3.4.5.6.7.8.9.9.net and
> > the net. servers would need to calculate 11 hashes to answer.  If the
> > client asks for 1.2.3.4.5.6.7.8.9.1.2.3.4.5.6.7.8.9.9.net the server
> > now needs to do 20 hashes.
> >
> > My concern is that the client determines the load.
> >
> > Even if the zone is like ip6.arpa, no matter what the existing
> > delegations look like, I can always game the queries to induce the
> > server into a lot of computing cycles.
>
> NSEC2 hashes are generated when the zone is signed, so this shouldn't
> impose any load which NSEC doesn't already?
>

The server needs to generate a hash of the queried name (and to find the
closest encloser) to find which NSEC2 RR's to include in the response.

That's where the client dictates the work to the server, and the point Ed
brought up.  I wonder if something like the EXIST RR can shorten this work.
Just brainstorming, since I have no clue right now.

Scott

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

--
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: Tue, 1 Jun 2004 14:12:15 -0400

>impose any load which NSEC doesn't already?

Not quite.

When I ask for 1.2.3.4.5.6.7.8.9.1.2.3.4.5.6.7.8.9.9.net, the server 
will only have pre-generated the hash for net. and not for anything 
else (that doesn't exist).

The client and server will need to communicate over the fact that 
there is no hash name for

           1.2.3.4.5.6.7.8.9.1.2.3.4.5.6.7.8.9.9.net
  and        2.3.4.5.6.7.8.9.1.2.3.4.5.6.7.8.9.9.net
  and          3.4.5.6.7.8.9.1.2.3.4.5.6.7.8.9.9.net
  and            ...
  and                                        9.9.net
  and                                          9.net
  and                                            net - exists
  and finally                                  *.net

Now wait a minute.  I need think about this a bit differently.

The server knows up front that 9.net doesn't exist - it doesn't need 
to "search" for that.  So what happens if the server just says 9.net 
does not exist?  If the server can say this outright, then the client 
can conclude anything below 9.net is also "not explicitly there." 
Does it matter that the same NSEC2 can be used for 9.net and a longer 
name?  I don't think so.

I suppose the needed parts of the answer are 1) that 9.net doesn't 
exist, 2) that net. does exist, and 3) that *.net doesn't exist.  If 
that's the case, then there isn't a linear growth of calculations and 
response records.

If this is right, then we are pushing the computing power back on the 
client.  The client may still need to compute all of the hashes.  If 
I show a return of

       <hash1>  NSEC2 <hash2> (as the non-existent name closer than the CE)
       <hash3>  NSEC2 <hash4> (as the CE=closest enclosure being there)
       <hash5>  NSEC2 <hash6> (as the *.CE)

The client isn't sure whether hash1 is the hash of the queried name 
or one far shorter.  But that's good, keeping the computing off the 
server.

I think that I've been overstating the cost...NSEC2 is more 
"expensive" than NSEC, but only by a fixed amount (the extra record).

However - is it ambiguous?  What are the chances that the sequence of 
hashs of the sequence of subsequently shorter name having a repeat of 
a triple?  I.e., what if the hashes of the above are:

1,2,3,45,67,43,32,1,2,3,33,77,99,... can the client be confused?  In a bad way?

I don't think an interloper could devastatingly confuse the client 
here - the client will know that it needs to see proof of one name, 
proof of non-existence of a direct descendent, and then proof of the 
missing wild card.  Without the private key, an interloper couldn't 
generate the RRSIGs on the records.

PS I through out an unrelated question earlier today that is related 
to this.  I'd also have to prove, if *.net exists, that nothing.*.net 
exists.  That would be a pain.

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

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

---

From: Ben Laurie <[email-masked]>
Date: Wed, 02 Jun 2004 14:22:06 +0100

Edward Lewis wrote:

> will only have pre-generated the hash for net. and not for anything else 
> (that doesn't exist).
> 
> The client and server will need to communicate over the fact that there 
> is no hash name for
> 
> The server knows up front that 9.net doesn't exist - it doesn't need to 
> "search" for that.  So what happens if the server just says 9.net does 
> not exist?  If the server can say this outright, then the client can 
> conclude anything below 9.net is also "not explicitly there." Does it 
> matter that the same NSEC2 can be used for 9.net and a longer name?  I 
> don't think so.
> 
> client.  The client may still need to compute all of the hashes.  If I 
> show a return of
> 
> The client isn't sure whether hash1 is the hash of the queried name or 
> one far shorter.  But that's good, keeping the computing off the server.
> 
> I think that I've been overstating the cost...NSEC2 is more "expensive" 
> than NSEC, but only by a fixed amount (the extra record).
> 
> hashs of the sequence of subsequently shorter name having a repeat of a 
> triple?  I.e., what if the hashes of the above are:
> 

The chances of hash collisions are very small indeed - you'd need around 
2^80 names to have a 1:2 chance of a single collision.

> I don't think an interloper could devastatingly confuse the client here 
> - the client will know that it needs to see proof of one name, proof of 
> non-existence of a direct descendent, and then proof of the missing wild 
> card.  Without the private key, an interloper couldn't generate the 
> RRSIGs on the records.

This seems correct to me.

> PS I through out an unrelated question earlier today that is related to 
> this.  I'd also have to prove, if *.net exists, that nothing.*.net 

Why would this be a pain? Just because there's an extra record?

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: Wed, 2 Jun 2004 13:13:38 -0400

>The chances of hash collisions are very small indeed - you'd need around 2^80
>names to have a 1:2 chance of a single collision.

The situation is better than that.  Assuming no collisions, there'll 
be one and only one NSEC2 RR owner whose name is the hash of one and 
only one super-domain of the QNAME.  The verifier then has the 
expectation that one of the other NSEC RR's covers the 
"one-more-label" super-domain and yet another covers the germane wild 
card.

If there was a NSEC2 RR owned by a hash that matched more than one 
super-domain of the Qname, then we have a hash collision.

>>  PS I through out an unrelated question earlier today that is 
>>related to this.
>>I'd also have to prove, if *.net exists, that nothing.*.net exists.  That
>>would be a pain.
>

It depends.  Some are saying that "*.net" is still a wild card even 
if there is a 9.*.net.  If so, then there's no need extra pain. 
Otherwise, the pain is the enforcement of the contrary.  (This is the 
kind of topic that takes time for analysis.)