Subject: Re: Removing the SERVFAIL response on hash collisions.

From: Eric Rescorla <[email-masked]>
Date: Thu, 17 Aug 2006 08:36:26 -0700

Eric Rescorla <[email-masked]> wrote:
> Mark Andrews <[email-masked]> wrote:
> > > Mark Andrews <[email-masked]> wrote:
> > > > > Hmm... I think I'm still missing something.
> > > > > 
> > > > > Let's take a step back and walk through things again. We have a server
> > > > > for zone example.com. It has a bunch of names N_1, N_2, ... N_n
> > > > > registered so we have N_1.example.com, N_2.example.com,
> > > > > ... N_n.example.com. So far so good, right?  These correspond to a
> > > > > series of hashes H_1, H_2, ... H_j.  For convenience, we order the
> > > > > indices in hash order so that H_1 < H_2 < H_3 ... < H_n.
> > > > > 
> > > > > So, when someone asks for a name Q that isn't one of the registered
> > > > > names, the name server computes H(Q) and then finds H_i and H_i+1
> > > > > st. H_i < Q < H_i+1. He then returns the NSEC records for H_i and
> > > > > H_i+1. Right?
> > > > > 
> > > > > Now, the collision problem occurs when H(Q) is equal to one of our
> > > > > hashes H_j even though N_j != Q. At this point, even though Q doesn't
> > > > > exist, the nameserver can't generate a valid negative response because
> > > > > there is no pair of records which encloses H(Q). Do I have this right so
> > > > > far?
> > > > > 
> > > > > Now, my assertion is that as a practical matter this case can't occur
> > > > > because the number of names (n) in the domain would have to be well
> > > > > outside of any plausible bounds (order 2^80) in order to have a 
> > > > > reasonable chance of a collision. Now, it's true that an attacker
> > > > > can mount an offline attack and try to generate a name that has
> > > > > a hash that matches one of the known hashes, but the computational
> > > > > cost of that is roughly 2^160/n, which is even more unreasonable.
> > > > 
> > > > 	We are not talking about the number of names in a zone.
> > > > 	We are talking about names in the namespace that are NOT
> > > > 	in zone.
> > > 
> > > Well, we're talking about both. We're talking about the chance that
> > > an arbitrary name *not* in the zone will have a hash that is the
> > > same as the hash of one of the names in the zone.
> > 
> > 	Which will happen, with SHA1, on average once every (2^160)/n
> > 	NXDOMAIN responses.  n = the number of names in the zone.
> > 	Yes I'm well away of how many years between collisions it is
> > 	at current query rates.
> >
> > 	It most probably will never happen in our lifetimes.  But
> > 	it still could.
> 
> So, now we're circling back to the beginning again, where I said
> that, no, it wouldn't happen for any practical value of the number
> of queries. By which I mean that if every computer on the Internet
> (order 2^32) did 1000 (2^10) queries per second for the
> next million years (2^20) years, and if your zone has a billion
> (2^30) names in it, the chance of even one of those queries 
> generating a collision would be less than 2^(-60).

Oops. I dropped a place here, since there are about 2^24 seconds
in a year. Now we're down to 2^(-36), which is still a ridiculously
small number.

-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: "Hallam-Baker, Phillip" <[email-masked]>
Date: Thu, 17 Aug 2006 08:59:02 -0700

> [mailto:[email-masked]] On Behalf Of Mark Andrews

> > Please define "applications behave badly to SERVFAIL".  In 
> what sense?
> > (I'm not arguing with the statement per se, but want to 
> know what sort 
> > of behavior you were thinking of.)
> 
> 	They tend to repeatedly ask the same question over and over and
> 	over and over and over and over and over and over and over and
> 	over in a vain hope that the SERVFAIL will go away.  The usually
> 	cope well with NXDOMAIN and SUCCESS.

You have a coding bug then. I thought you said you had tested this code path?

Changing the spec at a late date is not normally considered a good way to eliminate coding errors. 

Regardless of how DNSSEC is specified clients have to be capable of tollerating interaction with buggy implementations. That has nothing to do with NSEC.

> 	MTA's hold onto messages for several days before giving up on
> 	SERVFAIL.  The fail immediately on NXDOMAIN.  Lets hope you 
> 	don't want a quick response when the typo in the mail domain
> 	happens to trigger a NSEC3 has collision.

The chance of the server being hit by a meteor is rather larger.

5 nines reliability is hard to do. You are arguing for 48 nines reliability and have failed to demonstrate that there is a significant problem if a collision should occur.

What is completely surreal about this argument is the fact that due to the support for caching a DNS client is certain to be relying on stale data a statistically significant proportion of the time.

Quite what the MTA argument is meant to prove is equally beyond me. All my bounce mail goes straight to the bit bucket and has done for four years ever since spammers started to abuse that path. Email is at best a two nines application these days due to spam filtering.

Security is a risk control mechanism. You cannot achieve perfect security, all you can do is to reduce it to a negligible level. As EKR will no doubt shortly point out there is a negligible chance of a single collision occuring during the expected lifetime of the solar system. 

I doubt that fixing NSEC3 will be the only change we need to make to the Internet when we move on to the next solar system.

---

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Thu, 17 Aug 2006 07:48:43 -0700

The signature attack is indeed different, it DOMINATES the collision attack.

There is nothing that you can do with the collision attack that cannot be done by attacking the signature. The reverse is not true.

Ergo it does not matter whether you use NSEC3, a modified NSEC or plain old NXT. The security risks are identical with respect to hash compromise.

The probability of machine failure or coding failure is vastly greater than 1/(2^80)

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] 
> Sent: Thursday, August 17, 2006 10:22 AM
> To: Hallam-Baker, Phillip
> Cc: Eric Rescorla; Larson, Matt; [email-masked]
> Subject: Re: Removing the SERVFAIL response on hash collisions. 
> 
> 
> > This whole thread is illogical.
> > 
> > If there is a risk of hash collision in NSEC3 there is the 
> identical 
> > risk in the si gnature and no DNSSEC record is secure.
> 
> 	Yes, there is some risk that you will find two RRsets which have
> 	the same signature.  The effects of a collision however are
> 	different.  With the signature collision you can replace the
> 	answer.
> 
> 	With the NSEC3 collision you can't get a answer unless we extend
> 	the protocol.
>  
> 	Mark
> 
> --
> ISC Training!  October 16-20, 2006, in the San Francisco Bay 
> Area, covering topics from DNS to DHCP.  Email [email-masked].
> --
> Mark Andrews, ISC
> 1 Seymour St., Dundas Valley, NSW 2117, Australia
> PHONE: +61 2 9871 4742                 INTERNET: [email-masked]
> 
>

---

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Thu, 17 Aug 2006 13:45:01 -0700

> [mailto:[email-masked]] On Behalf Of Rob Austein

> The draft says "this will never happen, but just in case it 
> does, you must check for it and send SERVFAIL when it does.  
> Which it won't."

OK change the draft to state:

"The hash algorithm chosen must ensure that the likelihood of this condition occurring is sufficiently negligible. Implementations may respond to this highly improbable state in any manner they damn well choose."