Subject: Removing the SERVFAIL response on hash collisions.

From: Mark Andrews <[email-masked]>
Date: Wed, 16 Aug 2006 12:30:28 +1000

draft-ietf-dnsext-nsec3-06.txt currently has:

6.2.9.  Server Response to a Run-time Collision

   If the hash of a non-existing QNAME collides with an existing NSEC3
   ownername, then the server will be unable to return a response that
   proves that QNAME does not exist.  In this case, the server MUST
   return a response with an RCODE of 2 (server failure).

   Note that with the hash algorithm specified in this document, SHA-1,
   such collisions are astronomically unlikely.

	We can disambiguate collisions by returning the original
	owner name used to generate the hash.

	I propose that NSEC3 wire format be extended to optionally
	include a the original owner name at the end of the existing
	wire format.  This is *only* returned in AXFR/IXFR and for this
	special case.  The RRSIG will be computed over NSEC3 records
	as if this extra name was not included.  You can verify the
	appended ownername as its hash will be the ownername of the
	NSEC3 record.

	To save space we could exclude the zone name with "."
	representing the zone if we do this.

	Mark
-- 
Mark Andrews, ISC
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE:	+61 2 9871 4742		         INTERNET: [email-masked]

--
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: Mark Andrews <[email-masked]>
Date: Thu, 17 Aug 2006 09:07:49 +1000

> On Wed, 16 Aug 2006, Mark Andrews wrote:
> > 	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.

	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?

	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.

	Has anyone done a test run against COM or the root to see if 
	the current NXDOMAIN responses would generate a collision with
	any NSEC3 hash.

	Mark

---

From: Mark Andrews <[email-masked]>
Date: Thu, 17 Aug 2006 10:46:53 +1000

> Mark Andrews <[email-masked]> wrote:
> 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.

	Which is all fine and dandy when you are looking at the
	names that exist and generating hashes from them.

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

	I'm looking to find the existing hash.  Not to find a
	name which also has the same has value.
 
	To find a the hash of a name that I know to exist is just
	a matter of generating and testing enough sequential DS
	queries (to prevent referrals).  The hash function will
	randomise the NSEC3 selection.  There is only 200 and
	something million names in COM. A ~100 million queries and
	I have nearly a .5 probability of finding the hash I'm
	looking for.  400 million queries you get to several nines.

	This is the same problem of picking 1 ball out of 200 million
	replacing the ball after each pick if it is not the one you
	want and spinning the barrel.  Repeat.

	Something any bot army should produce a result on in a short
	period of time.

	Mark
 
> -Ekr

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 16 Aug 2006 17:55:22 -0700

> 	names that exist and generating hashes from them.

No, the math I just gave you is the probability of having two
names generating the same hash.

> 	Something any bot army should produce a result on in a short

Hang on a second: what at a high level does this attack accomplish?

-Ekr

---

From: Mark Andrews <[email-masked]>
Date: Thu, 17 Aug 2006 11:23:18 +1000

> Hang on a second: what at a high level does this attack accomplish?

	At the moment there is a case where you detect a collision
	at runtime and are not able to send back a valid NXDOMAIN
	response.  i.e. the hash of the QNAME matches the hash of
	a existing name making it impossible to send back a NSEC3
	where the hash is inside the covered range.

	The current draft says, just send SERVFAIL.  I proposed
	that we make a response that contains just enough extra
	information to disprove the collision.

	Matt suggested a new RCODE.  Now for the new RCODE to work
	we need to be able to verify it by looking at the contents
	of the response.  I was looking to see how easy it would be
	to obtain the NSEC3 hashs we need.  For a non delegation
	you just pick some random types at the known name.  For
	a delegation you need to search if the DS record is there.

	Mark

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 16 Aug 2006 19:48:07 -0700

> 	information to disprove the collision.

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.

Where have I gone wrong here?

-Ekr

---

From: Mark Andrews <[email-masked]>
Date: Thu, 17 Aug 2006 14:10:35 +1000

> 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.
> Where have I gone wrong here?

	With SHA1 there are 1461501637330902918203684832716283019655932542976
	potential hashes.
	There are more than 111444219848545291112918149658401217019177846881717006276548100629318214534968256903948922840416256 (36^63) possible labels if you restrict
	yourself to a-z0-9.

	There 76253229556466706119897315261914748347145838923466 different
	labels, on average, that hash to a individual value.

	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 06:44:08 -0700

This whole thread is illogical.

If there is a risk of hash collision in NSEC3 there is the identical risk in the signature and no DNSSEC record is secure.

> -----Original Message-----
> From: [email-masked] 
> [mailto:[email-masked]] On Behalf Of Mark Andrews
> Sent: Thursday, August 17, 2006 2:43 AM
> To: Eric Rescorla
> Cc: Larson, Matt; [email-masked]
> Subject: Re: Removing the SERVFAIL response on hash collisions. 
> 
> 
> > > > 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 
> > > > 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?
> > > > 
> > > > 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.
> > > 
> > 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.  A couple of extra lines of code will deal
> 	with the problem.  The code is testable using a truncated
> 	hash.  In fact it would be useful to specify a really short
> 	hash for test purposes only, 2^16 values would be fine as it
> 	would be useless for any zone of significant size.
> 
> 	No one has stated that my solution will not work.  If it won't
> 	work please tell me and I'll shutup.
> 
> > > 	With SHA1 there are 
> 1461501637330902918203684832716283019655932542976
> > > 	potential hashes.
> > > 	There are more than 
> > > 111444219848545291112918149658401217019177846881717
> > 006276548100629318214534968256903948922840416256 (36^63) possible 
> > labels if y ou restrict
> > > 	yourself to a-z0-9.
> > > 
> > > 	There 
> 76253229556466706119897315261914748347145838923466 different
> > Sure, but so what? Actually finding a second preimage is 
> > computationally intractable.
> >
> > How does this add up to an attack? What does the attacker 
> do and what 
> > advantage does it give them?
> > 
> > -Ekr
> --
> ISC Training!  October 16-20, 2006, in the San Francisco Bay 
> Area, covering topics from DNS to DHCP.  Email [email-masked].
> --
> Mark Andrews, ISC
> to unsubscribe send a message to 
> [email-masked] with the word 'unsubscribe' 
> in a single line as the message text body.

---

From: Mark Andrews <[email-masked]>
Date: Fri, 18 Aug 2006 00:16:10 +1000

> Mark Andrews wrote on 08/16/2006 04:30:28 AM:
> 
> > 
> Note that I'd like to see some kind of consensus on the need to document 
> ANY text about 2nd pre-image resistance failover before actually 
> documenting the following solution.
> 
> iff there is a collision, (enough has been said already about possibility) 
> why not return the following:
> 
> H(X)=H(Y), X!=Y, X exists, Y does not exist.
> 
> rcode=3
> QNAME=Y
> empty answer section
> authority section: 
> H(Y) NSEC3 ... ... ...
> H(Y) RRSIG NSEC3
> X A 10.1.1.1
> X RRSIG A ...
> 
> Since it is impossible to prove that Y does not exist 'the nsec3 way', we 
> prove that X exist, by returning both X and H(X). Since collisions between 
> existing names have been avoided during the generation of the NSEC3 
> records, we can safely assert that Y does not exist.
> 
> This avoids (perceived) SERVFAIL allergy. This avoids fondling with RDATA. 
> This is not spoofable, since the deletion of X,RRSIG(X) will leave the 
> response broken.

	This does not handle empty nodes.
 
> Roy

---

From: Edward Lewis <[email-masked]>
Date: Thu, 17 Aug 2006 10:44:23 -0400

At 0:21 +1000 8/18/06, Mark Andrews wrote:

>	With the NSEC3 collision you can't get a answer unless we extend
>	the protocol.

True (or not), but let's just solve this by redirecting all your 
complaint calls on this to Matt's desk.  (I do mean that in jest.)

BTW - some have confused my alleged moderation of the mail list for 
the week as me being the temporary chair.  No, not me, I didn't get 
any stinkin' badge for this.  I just log in and look at the spam 
namedroppers gets.  I say this because I'm not declaring any 
consensus here, just trying to keep the WG moving along.

-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
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: "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)

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

---

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

Eric Rescorla <[email-masked]> wrote:
> > > 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.
> > 
> > 	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

---

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Thu, 17 Aug 2006 08:59:02 -0700

> > 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 09:15:53 -0700

Almost, if SHA-n is broken the whole edifice of *DNSSEC* is broken.

No Paul you are not entitled to selectively posit a weakness in a cryptographic algorithm. Either the algorithm is good or it is vulnerable. If the algorithm is vulnerable then the possibility of the vulnerability being exploited MUST be considered equally likely in all parts of the system.

If SHA-n is broken then so are your possible recovery mechanisms. 

> [mailto:[email-masked]] On Behalf Of Alex Bligh
> Sent: Thursday, August 17, 2006 12:00 PM
> To: Paul Vixie; [email-masked]
> Cc: Alex Bligh
> --On 17 August 2006 15:38 +0000 Paul Vixie <[email-masked]> wrote:
> 
> > let's stop dividing large numbers by other large numbers 
> and arguing 
> > about probabilities.  the worry here is not that a hash 
> collision will 
> > occur naturally, but rather unnaturally.  let's stop 
> arguing about how 
> > secure SHA-160 is and whether anybody knows how to break it or how 
> > hard it will be to break it.  if there's an ALG-ID in the protocol, 
> > then we're assuming that SHA-160 will become unsuitable 
> some day, and 
> > we're allowing for the possibility that breakage will occur.
> 
> I think the probability point being made is not that we 
> should rely on SHA-n never being broken, but that if this 
> "exploit" in probabilistic terms becomes breakable, then the 
> whole structure of NSEC (and NSEC-3) will necessarily have 
> already come tumbling down some years earlier. Why bother 
> with SERVFAIL when the intrepid malefactor can spoof much 
> more interesting positive replies?
> 
> Alex
> 
> --

---

From: Alex Bligh <[email-masked]>
Date: Thu, 17 Aug 2006 17:50:24 +0100

> Almost, if SHA-n is broken the whole edifice of *DNSSEC* is broken.

Quite. That is what I meant but inadequately expressed. Thank-you for
clarifying.

Alex

---

From: Roy Arends <[email-masked]>
Date: Thu, 17 Aug 2006 21:51:56 +0200

>    This does not handle empty nodes.

Return a node that is a sub of the empty node.

Roy

---

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

---

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

> So, yes, in some sense it *could* happen, but it's far exceeded by the
> chance of any number of other improbable things (for instance, values
> spontaneously changing in program memory) that we don't bother to
> do anything about.
> 
> 
> It's not a matter of won't work. It's a matter of it's extra
> complexity that's not needed.

	SERVFAIL is a BAD response.

	SERVFAIL can mean I don't understand EDNS
	SERVFAIL can mean I don't understand CD
	SERVFAIL can mean I detected a error loading the zone
	SERVFAIL can mean I expired

	and thats just the list from auth servers.  Some of those SERVFAILs
	you can recover from.
	
	Returning SERVFAIL is just adding additional complexity to
	a already complex part of the answer analysis path.

	As a implementer I say that it is actually less complex to
	return the variable NSEC than to have to deal with the SERVFAIL.
	
	Yes, I'm written NSEC3 validator.  I'm well aware of how
	much more code I would need to be added to do this.

	SERVFAIL would cause you to requery with plain DNS (see the
	recovery comment above).  Once you got the plain DNS answer
	you would then attempt to prove that the answer was unsecure
	which would fail.  You would then try the next nameserver.
	Once you had tried all the nameservers for the zone that
	you could reach you would then return SERVFAIL.
	
	We already have to special case how we digest multiple records so
	this one is not really any different.

	This get a answer through to the validator that it can understand.

---

From: Edward Lewis <[email-masked]>
Date: Fri, 18 Aug 2006 09:28:07 -0400

Reading further...

And with that he closed his mail reader put down the laptop he was 
carrying and seating himself on a cask began to cry. And he cried and 
cried and cried - for all the time spent reading mail on a nice warm 
summer day.

But all ends happily:

So they deployed DNSSEC, and if they didn't live happy ever after, 
that has nothing to do with the story of the three sillies.

At 23:51 -0600 8/17/06, The Purple Streak, Hilarie Orman wrote:
>... one evening when she had gone down to check her email she happened
>to look up at the ceiling, and there she saw a big wooden mallet stuck
>in one of the beams, held by a relay that would release if her DNS
>server had to deal with an NSEC3 collision.
>
>It must have been there for ages and ages, for it was all covered with
>cobwebs; but somehow or another she had never noticed it before, and
>at once she began thinking how dangerous it was to have the mallet
>just there.
>
>"For," thought she, "supposing him and me was married, and supposing
>we was to have a son, and supposing he were to grow up to be a man,
>and supposing he were to come down to draw cider like as I'm doing,
>and supposing there were a hash collision and the mallet were to fall
>on his head and kill him, how dreadful it would be!"
>
>Ormative reference:
>http://www.mainlesson.com/display.php?author=steel&book=english&story=sillies
>
>Hilarie
>
>--