Subject: Re: Hashed/name collision (Was Re: Removing the SERVFAIL response on hash collisions.)

From: Eric Rescorla <[email-masked]>
Date: Mon, 21 Aug 2006 08:54:50 -0700

=?iso-8859-1?Q?=D3lafur?= =?iso-8859-1?Q?_Gu=F0mundsson?= /DNSEXT  wrote:
> Restart, I lost track of the discussion while reading all the messages
> in bulk this morning.
> 
> There are two cases of hash-to-name collision possibilities:
> 	Y    == H(x) (hashed name collides with an existing name)
> and 	H(z) == W    (New name collides with a hashed name)
> 
> The first one is random and has real low probability, the second is
> likely malicious.
> If the protocol handling of "collisions" causes "bad side effects"
> someone is going to do register new names that collide.

OK. I'm going to stop you right here:
This is what's known as a "2nd preimage attack" and in a secure
hash function of bit-length b has complexity 2^b. I.e., it's
completely impractical if your hash function is strong.

If your hash function is weak enough (i.e., someone has mounted
a successful analytic attack) that this is a practical attack
then you have a real serious problem because they can forge
new signatures based on a single valid signature. In this
case you need a new hash function.

The bottom line here is that if your hash function is secure
than collisions cannot happen. If it's not, then you need to 
change hash functions anyway. 

-Ekr

--
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: Ólafur Guðmundsson<[email-masked]>
Date: Mon, 21 Aug 2006 12:39:43 -0400

>change hash functions anyway.

Eric,
This is not an attack on the hash function is only uses it to cause
confusion.

For sake of argument:
HASH("amazon.com.") == "abcdef01234567890abcdef"

There is nothing that prevents me from registering
abcdef01234567890abcdef.com as a domain.

Now at the same name we have NSEC3 RR for Amazon and Delegation for
my domain.
The question is what does a authorative server return in the case
someone asks for records at "abcdef01234567890abcdef.com".

A orthogonal issue (which you are discussing) is what to do TWO
valid names hash into the same  hashed-name.
I agree with you this the probability is so low we can "safely"
ignore that case, with a note in the security considerations section.

         Olafur