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

From: Eric Rescorla <[email-masked]>
Date: Wed, 16 Aug 2006 16:56:10 -0700

Mark Andrews <[email-masked]> wrote:
> > On Wed, 16 Aug 2006, Mark Andrews wrote:
> > > 	I propose that NSEC3 wire format be extended to optionally
> > > 	include a the original owner name at the end of the existing
> > > 	wire format.
> > 
> > I will support this change if you agree to carry around an oxygen tank
> > for the rest of your life to avoid potential asphyxiation in case all
> > the air molecules in whatever room you happen to be located in
> > suddenly move to the other side.
> > 
> > Seriously, with SHA-1 the possibility of this collision is
> > astronomically low.  More risk would be introduced by increasing code
> > bloat to deal with this case than the possible damage if the case
> > itself occurred.
> > 
> > Does SERVFAIL really need to be disambiguated?  I don't think so.  But
> > if this really bothers anyone, let's burn an extended RCODE to signal
> > this scenario.  But don't burden the NSEC3 wire format with it.
> > 
> > Matt
> 
> 	The chance of collision is non zero.  It will happen.  We have
> 	to detect this anyway.  Applications behave badly to SERVFAIL.

I hear this kind of thing a lot, but it's not true for any practical
value of "will happen". Given a population of n elements drawn from
a pool of d elements (with replacement) the probability that you
will have two values that are the same is approximately:
            
               -(n(n-1))/2d            -(n^2)/2d
p(n;d) ~= 1 - e                ~= 1 - e

[http://en.wikipedia.org/wiki/Birthday_paradox]

We can invert this to find out the number of elements we'd need
to have a probability of collision p. It's:

n(p) ~= sqrt(2 * d * ln(1/1-p))

[http://en.wikipedia.org/wiki/Birthday_attack]

So, let's say we're willing to accept a 10^-9 chance that the 
entire system will have a single collision. This would require
you to have about 2^64 separate names in the system, which is
rather unlikely.

> 	If you have the NSEC3 which corresponds to verisign.com.  Is
> 	it possible to construct a response using that NSEC3 which makes
> 	verisign.com go away?  I suspect the answer to that would be
> 	yes.

Actually, this problem is much harder because you can't take
advantage of the birthday paradox. The cost of generating
an input which digests to a given hash value (a 2nd preimage
attack in this case) is approximately 2^160.

-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: David Blacka <[email-masked]>
Date: Thu, 17 Aug 2006 10:51:49 -0400

I feel a bit late, since there are already 20 more messages in response
to this thread, but Mark said some stuff that I would like to clarify.

> 	to detect this anyway.  Applications behave badly to SERVFAIL.

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

> 	If we choose a new rcode then you need to work out how can it be
> 	abused.  It can't be just a plain RCODE.  It would need to be
> 	a RCODE with the entire proof.  Can one construct a response
> 	with the new RCODE which make a existing name disapear?

Abused?  Why would a new rcode be any more abusable than other existing
rcodes?

> 	verisign.com go away?  I suspect the answer to that would be

The answer is no, you cannot.  I thought that was the problem you were
trying to solve?

-- 
David Blacka                      <[email-masked]>
Sr. Engineer    VeriSign Infrastructure Product Engineering

---

From: Edward Lewis <[email-masked]>
Date: Thu, 17 Aug 2006 11:11:07 -0400

>of behavior you were thinking of.)

I didn't write the original 'plaint - but I've seen apps that don't 
know to give up when they should.  NXDOMAIN - yeah, give up.  But 
SERVFAIL, they may try again.  And again.  And again.

Going out on a limb (meaning I'm speaking on hearsay), I think this 
is why ARIN passed a policy to trim lame delegations.  Resolvers of 
that era didn't stop retransmission when faced with a lame response. 
'Course, most resolvers of that era have been otherwise patched by 
now.

>Abused?  Why would a new rcode be any more abusable than other existing

Well, that's a good point.  If they don't understand "please stop" 
they aren't going to understand "please desist."

-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                                +1-571-434-5468
NeuStar

Soccer/Futbol. IPv6.  Both have lots of 1's and 0's and have a hard time
catching on in North America.

---

From: Mark Andrews <[email-masked]>
Date: Fri, 18 Aug 2006 01:15:31 +1000

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

	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 answer is no, you cannot.  I thought that was the problem you were

	I was playing out rcode solution space senarios.
 
--
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]