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

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. 
> 
> 
> > 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.  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
> > > 	labels, on average, that hash to a individual value.
> > 
> > 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
> 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/>
> 
> 

--
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: Fri, 18 Aug 2006 00:21:43 +1000

> 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: Edward Lewis <[email-masked]>
Date: Thu, 17 Aug 2006 10:44:23 -0400

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

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: "Larson, Matt" <[email-masked]>
Date: Thu, 17 Aug 2006 10:28:56 -0400

On Thu, 17 Aug 2006, Ed Lewis wrote:
> I'm undecided if a one in a quadrillion chance is a "can enter" or a 
> "can't enter."

This discussion reminds me of a saying, "All probabilities are 50%:
either a thing will happen or it won't."

> So I suggest this.  Let's first assume it's a "can be" and try to 
> prevent the situation via other design or to come up with a slick 
> response to the second question (below).

No.  That would be a continuation of this thread, which is getting
nowhere.  The math has been pointed out.  Just because a thing is
extremely improbable and therefore might conceivably happen does not
mean we need a code path for it, let alone a change to the on-the-wire
protocol to accommodate it.  I could live with the former if an
implementor insisted, but it should be optional.  The latter is
untenable given the probabilities involved.

> If we can design the protocol that the state cannot be entered, 
> nothing has to be signalled in the protocol.  If the state can be 
> entered, we need to know how to back out of it.
> 
> Second question - if the state "can be" entered, what is the signal? 
> My comment about SERVFAIL is a partial response to the second 
> question.

The further discussion since my earlier message has caused me to
withdraw my suggestion for a separate RCODE: even that solution is
overkill.  Let's just use SERVFAIL.  We need to trust the math.  We
need to consider how minor the consequences if the situation actually
occurred.  Encumbering the protocol for this event is not responsible
engineering.

Matt

---

From: David Blacka <[email-masked]>
Date: Thu, 17 Aug 2006 11:08:03 -0400

Edward Lewis wrote:
> At 10:28 -0400 8/17/06, Larson, Matt wrote:
> 
> Then let's document the situation as unlikely, but if it happens, an
> implementation ought to consider it a service failure.

Excellent idea... Fortunately, this is what draft already says.

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

---

From: Alex Bligh <[email-masked]>
Date: Thu, 17 Aug 2006 16:59:48 +0100

--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: Eric Rescorla <[email-masked]>
Date: Thu, 17 Aug 2006 09:07:31 -0700

Paul Vixie <[email-masked]> wrote:
> > ...  Let's just use SERVFAIL.  We need to trust the math.  ...
> 
> i guess i'm lucky, i don't understand the math.  so i'm trusting history.
> history tells me that some day some smart person will break SHA-160 (or
> SHA-256 or RSA-16384 or anything else we might put in there), and that if
> the system does not have design-level resistance to attacks that use the
> new technique, then the Internet is going to have another very bad year.
> that's not unusual, but this time it will be our fault.  my fault if i
> didn't speak up, so i'm speaking up.
> 
> this is a protocol discussion not a math discussion.  if we try to define
> SERVFAIL to mean something in this instance, then what's stop stop a MiTM
> from forging SERVFAILs in order to get clients to believe that this case
> has been hit?

Hang on a second: if an attacker can mount a 2nd preimage attack
on SHA-1, then they can forge all sorts of messages without any
kind of MITM cleverness. The attack you're hinting at is far from
the worst thing you could do.

-Ekr

---

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

> untenable given the probabilities involved.

	The draft already says we have to *detect* and return
	SERVFAIL.  A blind lookup would just return the NSEC3
	record that says the name exists.

	Named already does blind lookups. I've got to add the
	code to check whether we get a covering or exact NSEC3
	and whether it was what was expected.

	As far as the wire is concerned it is a record with a
	optional field at the end the presence of which is detected
	by looking at the rdlen.  There are lots of records that
	detect extra fields (type code/bitmaps) by looking at rdlen.

	The only real change is to how the signature is generated
	and checked.  To implement NSEC3 we have to change both
	existing server behaviour and existing validator behaviour.

	Since you don't expect to see it, existing protocol analysers
	that check signatures will work except for the case were
	we do get a collision or if they are checking a axfr/ixfr
	stream in which case all the NSEC3 records will have the
	extra field.

	Doing what I am suggesting is nothing new.  BIND 4 stored
	the owner of SOA to return in negative responses at the end
	of the SOA rdata.

---

From: Paul Vixie <[email-masked]>
Date: Thu, 17 Aug 2006 15:38:53 +0000

like marka, i don't like the idea of "bad protocol design" of this kind.
like matt, i don't like the idea of adding logic for such a rare case.

in my opinion, the proper response if there's a hash collision is silence.
let the client retry if they want, and eventually give up.  that's not
good design, but silence is something a MiTM can already synthesize (by
DDoS'ing the client/server path in a strategic microburst), and the hole
caused by such an attack is already well understood and already paid for.

---

From: Chris Thompson <[email-masked]>
Date: Thu, 17 Aug 2006 15:43:46 +0100 (BST)

[email-masked] (Matt Larsen) writes:

[...]
>           The math has been pointed out.  Just because a thing is
> mean we need a code path for it, 

There surely has to be _a_ code path for it, even if it's the one that
gives a SERVFAIL response. And yes, it will be rarely exercised (until
someone cracks SHA-n), which is an argument for keeping it simple. But 
I sympathise with those expressing distaste for yet more overloading 
of SERVFAIL.

-- 
Chris Thompson
Email: [email-masked]

---

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

>This whole thread is illogical.

Let's reset the discussion then, going back to the specification of a 
client-server protocol.

First question, is there a state the protocol can enter in which 
there is no available record to use in a response?  "Can enter" - 
that's objective/subjective - as in "can enter a deadlocked state."

I'm undecided if a one in a quadrillion chance is a "can enter" or a 
"can't enter."  I certainly don't have time to think about this 
myself.  I'm sure we could have a real religious row over that too - 
which would be a waste of everyone's time.  And further delay the 
outcome of NSEC3 (positively or negatively.)

So I suggest this.  Let's first assume it's a "can be" and try to 
prevent the situation via other design or to come up with a slick 
response to the second question (below).  If we get no where, let's 
try to dress this up as a "can't be" and pave it over.

---

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

This is kind of what we did for "* NS" already.  Same deal, basically.

The purist in me wouldn't like this, but DNS is so utterly beaten up 
over the years that sticking to puritanical views for the sake of it 
will just further irrelevance.  OTOH, I do push for trying to stick 
as close to the original principles as that is the most efficient way 
to operate the protocol.  (Limits the amount of entropy fighting we 
have to do.)

And someone ought to get started on DNSv6 to clean up this mess.  No 
fair rebranding LDAP as that either. ;)