Subject: Re: dictionary attack on nameservers

From: Paul Vixie <[email-masked]>
Date: Mon, 06 Sep 2004 21:37:34 +0000

olaf said:

> > > I want to close this thread by giving every participant the
> > > opportunity to state their concluding argument in not more than 20
> > > lines of text.

i said:

> >  1: my observations are:
> > ...
> > 12: my recommendations are:
> > ...
> > 20: ...

someone else said:

> [whatever]

but i'm not debating these topics.  olaf asked me to state my concluding
argument in 20 lines or less, which i've done.  anyone who has a different
view, whether outright opposed to what i said or completely independent,
ought to give olaf 20 lines (or fewer) of text.  as tempting as it is to
stand my ground and fight for what i believe in, that time, for nsec++, is
over.

--
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: Jim Reid <[email-masked]>
Date: Wed, 15 Sep 2004 17:19:46 +0100

>>>>> "Ben" == Ben Laurie <[email-masked]> writes:

    Ben> I agree, in theory. However, in practice, there's no way to
    Ben> have a zone with size 2^512, or even 2^160, so this is not a
    Ben> problem in real life.

Once upon a time people said that about MD5. There was supposedly no
realistic chance of two different input strings yielding the same hash.

---

From: Roy Arends <[email-masked]>
Date: Wed, 15 Sep 2004 20:34:42 +0200 (CEST)

> realistic chance of two different input strings yielding the same hash.

And thats it, there's the crux.

If a collision would be found we're en-masse shifting to a different hash
algorithm, instead of desperately trying to avoid collisions.

Roy

---

From: Simon Josefsson <[email-masked]>
Date: Wed, 15 Sep 2004 21:59:04 +0200

> realistic chance of two different input strings yielding the same hash.

In what way do you believe that is relevant?

If it is possible to find two (useful) inputs that have the same hash,
then the signature schemes in DNSSEC are dead.

Whether the hash function is collision resistant isn't critical for
the NSECbis idea.  One necessary property is that the output space is
large enough, so that with salting it is possible to find unique
output hashes for all owner names in existence.

This isn't something you have to trust some hash function designer on,
you can show this empirically yourself.  Compute hashes H(i) for
i=0...2^40 and count the number of distinct hash outputs you get.  If
that number is close to 2^40, the hash function is good enough to
avoid collisions by repeated salting, since DNS zone doesn't contain
more than 2^40 owner names.  Replace by 2^41 if you think 2^40 is too
small...

You can base the NSECbis idea on CRC-128 plus salting, and I think it
would still work.  As you know, it is trivial to find two inputs that
have the same CRC-128 output.  I think your argument is simply flawed.

I believe the hash function property that is needed for the NSECbis
idea is a large enough output space and non-reversibility.

Thanks,
Simon

---

From: Ben Laurie <[email-masked]>
Date: Thu, 16 Sep 2004 00:35:56 +0100

> realistic chance of two different input strings yielding the same hash.

People said it was practical to have a zone of size 2^128?

The unrelated fact that there exist broken hashes is by no means a 
disproof of the general concept that there are an awful lot of possible 
outputs from cryptographic hash functions.

Cheers,

Ben.

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