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

From: Alex Bligh <[email-masked]>
Date: Wed, 15 Sep 2004 10:52:16 +0100

--On 15 September 2004 08:04 +1000 Mark Andrews <[email-masked]> 
wrote:

> 	You are incorrect.  All the current schemes have a hash of less than
> 	64 octets.  There will ALWAYS be a possibility of collision even
> 	after trying every salt as it is impossible to make the hash space
> 	larger than the pre-hash space.

But the pre-hash space is sparse, and we only care about collisions of
ACTUAL values in the pre-hash space, not potential values. IE (assuming all
octet values are OK and 64 byte labels for the sake of argument) there are
the pre-hash space is size 256^64 and the hash space is smaller (let's say
we represent them as alphanumerics so 36^64) - which is presumably your
complaint. Note 256^64 is approximately 10^153, and there are about 10^79
atoms in the universe, so I predict in applications the pre-hash space will
be sparse as even if we could represent one RR in just one atom, we are way
off filling the zone :-) So this doesn't matter provided there is a
limitation on the number of RR's in a zone - the limitation doesn't have to
be impactful - If it was 10^76 (number of atoms in the universe over 1000),
we'd still have 10^79 possible salt values to work through, i.e. about 263
bits of salt. And as I pointed out earlier, as 76*2<153, the expected
number of iterations to find a salt that works is less than 2.

I do not think limiting a zone file to 10^79 RRs is going to have
a significant deployment impact.

Alex

--
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: Wed, 15 Sep 2004 09:29:13 -0400

At 8:04 +1000 9/15/04, Mark Andrews wrote:
>
>	The data doesn't have to be sorted but the hashes do.  "6 of 1,
>	half a dozen of the other" as far as I am concerned.

For a lookup resulting in an answer, you don't need to access the 
hashes.  So, for all positive hits, you can go back to the old means 
of storing a zone's contents in memory.

Only for lookups resulting in negative answers do you have to have a 
sorted list of things to respond with.

>	larger than the pre-hash space.

Well, I believe that.  Still I don't understand why collisions are a 
problem.  Perhaps because I am assuming that you'd only need to give 
out hash answers in name errors, so the list of RRSETs doesn't matter.
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                            +1-703-227-9854
ARIN Research Engineer

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

---

From: Ben Laurie <[email-masked]>
Date: Wed, 15 Sep 2004 16:37:48 +0100

Mark Andrews wrote:
>>Hash collisions are fantastically unlikely. With salt you can make them 
>>never occur, anyway. Plus, if they were a problem, then you would have 
>>the same issue with signatures, but I don't see anyone bringing that one up.
> 
> 

I agree, in theory. However, in practice, there's no way to have a zone 
with size 2^512, or even 2^160, so this is not a problem in real life. 
Even a zone large enough to have a 1 in 2 chance of a hash collision 
(2^80) is mind-bogglingly unlikely. If I'd started at the beginning of 
the Universe[1], I'd have to have generated 30 million domains a second 
to have a zone that large today.

Cheers,

Ben.

[1] 12,000,000,000 years ago, says me.

-- 
ApacheCon! 13-17 November! http://www.apachecon.com/

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