Subject: Re: Avoiding collisions - desirability & possibility thereof (was Re: dictionary attack on nameservers)

From: Edward Lewis <[email-masked]>
Date: Wed, 15 Sep 2004 10:15:31 -0400

At 23:53 +1000 9/15/04, Mark Andrews wrote:
>	The problem is that by using hashes there you are creating
>	sets of QNAMES for which you cannot return NXDOMAIN securely.
>	One set for each hash in use.

?  I'm probably not on the same wavelength about hashes.  I think the 
hash space needn't be considered part of the DNS data tree, just a 
transformation of existing names into an obscured representation. 
I.e., in a response message with a name error in the return code, the 
verifier ought to realize that the negative answer proof records are 
using transformed names, not plain text names.

>
>	If you have collisions with hashes of names with data you cannot
>	hand out NODATA responses securely.  Yes, Roy you can exhaust
>	salt space.

Let's say the labels in a zone are {chamberlin erving julius wilt} 
and the corresponding hash values are { 6  9  13 } with a collision.

Let's say I ask for ( robertson, IN, TXT ) and the hash of robertson is 9.

Hmmm, I picked out 9 by randomly hitting a key and seeing that I 
managed to pick a collision between the qname and one or more members 
of the zone.  Will this still work out?

So, I get back a "name error" with "9 NSEC7 13" in the authority 
section.  After verifying the record (via the RRSIG), what next?  I 
suppose it's then possible to a victim of an insertion attack - an 
interloper passes back this collision with there being a genuine 
robertson in the zone.

What if there the qname's hash was 10?  In that case, I don't see a 
problem in the collision amongst zone members.

But - it's the collision between qname and zone content - which isn't 
possible to know at signing or serving time - that might be a problem.
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                            +1-703-227-9854
ARIN Research Engineer

"I can't go to Miami.  I'm expecting calls from telemarketers." -
Grandpa Simpson.

--
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: Chris Thompson <[email-masked]>
Date: Wed, 15 Sep 2004 15:27:06 +0100 (BST)

Mark Andrews writes: 

[...snip...]
> 	One set for each hash in use.

Maybe a different mechanism for securely returning NXDOMAIN is needed
in these cases? If a name being looked up hashes to something different 
from every extant name, return the signed NSEC' record to prove it by
showing an interval of hash values free of extant ones. But if the hash
matches that of one or more extant names, but the name isn't any of them, 
then return a signed NSEC'' record that lists all the extant names that 
hash to that value (proving that the caller's wasn't one of them). That 
gives away one or more names in the zone, of course, but the caller had 
to be pretty damn lucky to get a hash match in the first place.

This idea is somewhat half-baked, in that representing a list of names 
of potentially unlimited length in a signed answer could pose problems.
(Although now you really could play "change the salt, Walt" to finesse 
that.)

Chris Thompson
Email: [email-masked]