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

From: Eric Rescorla <[email-masked]>
Date: Wed, 16 Aug 2006 21:33:57 -0700

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.

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

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

--
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: Rob Austein <[email-masked]>
Date: Thu, 17 Aug 2006 02:27:40 -0400

> advantage does it give them?

Sorry for jumping in, but I know both correspondants here pretty well
and can tell that they're talking past each other.

Mark, meet Eric.  Eric, meet Mark.  Eric is a protocol security guy.
Mark is a DNS implementation guy.

The attack that Mark is worried about is not the one that Eric thinks
Mark is worried about.

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

Mark's reaction to this, based on twenty years before the mast as a
DNS implementor, is "Good grief, not another flipping event that sends
SERVFAIL.  Every time I follow a spec that tells me to send SERVFAIL,
my phone starts ringing off the hook with people whining about how
their DNS service doesn't work anymore and what have I broken now?"

The sad thing is that Mark is absolutely right about this.

Implementing a spec that says "just send SERVFAIL" leaves Mark's phone
open to a denial of service attack.  Since Eric assures us that Mark's
code will never send SERVFAIL in this particular case and that Mark's
phone will thus never ring, the obvious fix is to forward Mark's phone
to Eric.

All clear now?

---

From: Mark Andrews <[email-masked]>
Date: Thu, 17 Aug 2006 16:43:24 +1000

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

> > 	There are more than 111444219848545291112918149658401217019177846881717
> 006276548100629318214534968256903948922840416256 (36^63) possible labels if y
> ou restrict
> > 	yourself to a-z0-9.
> > 
--
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: bert hubert <[email-masked]>
Date: Thu, 17 Aug 2006 09:53:21 +0200

> 	work please tell me and I'll shutup.

If I've followed the discussion above, the codepath to detect and handle
such a collision is unlikely to be taken once in the lifetime of the
universe. Hence it will bitrot with astounding rapidity.

	Bert

-- 
http://www.PowerDNS.com      Open source, database driven DNS Software 
http://netherlabs.nl              Open and Closed source services

---

From: Alex Bligh <[email-masked]>
Date: Thu, 17 Aug 2006 12:41:15 +0100

--On 17 August 2006 16:43 +1000 Mark Andrews <[email-masked]> wrote:

> 	NXDOMAIN responses.

And with SHA-256 still more infrequently (it's probably more likely
that a packet gets corrupted in transit to look like a SERVFAIL when
it didn't start out that way). Code to implement longer hashes is likely
to last better and be better tested than code to handle the extremely
unlikely event of a collision (of whichever variety).

> 	work please tell me and I'll shutup.

About 18 months ago (I think) we had a thread here where we concluded
under NSEC or NSEC3 it was still possible to spoof errors, such as
SERVFAIL. So it does seem a little bit like a bandaid covering a tiny
hole when there's a great gaping maw by the side. If we did this, I
would be concerned that the behaviour of the resolver receiving such
a SERVFAIL was also specified. If the QNAME is optional, I presume
in its absence, the resolver should assume it is associated with the QNAME
if the associated query. What if it's simply wrong? I presume ignore
the entire SERVFAIL as bogus (more interoperability testing to do there,
then).

Alex

---

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

>SERVFAIL.  Every time I follow a spec that tells me to send SERVFAIL,

My reaction to the the first post on the thread is the same ("Good 
grief...").  But I haven't replied because I don't have a better 
suggestion.

So I'll just second that "yet another requirement to return 'service 
failure' is rather distasteful."  In a way it might be appropriate - 
but thinking more it isn't.

A service failure means (from 1035):
#                2               Server failure - The name server was
#                                unable to process this query due to a
#                                problem with the name server.

In this case, the failure is in the protocol and not the server. 
It's not like the server failed to load the (child) zone, or a 
recursive server could not get a response from another server.  It's 
not like a server only got a corrupted (as in failed DNSSEC 
validation) answer.  The problem here is that the protocol has no 
defined answer to give.

It's not like the server can't retrieve the record it needs for the 
answer, it's like there's no answer to give.

Of course, I'm basing this on a fairly narrow interpretation of "a 
problem with the name server."
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
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: Eric Rescorla <[email-masked]>
Date: Thu, 17 Aug 2006 08:33:35 -0700

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

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.

> 	work please tell me and I'll shutup.

It's not a matter of won't work. It's a matter of it's extra
complexity that's not needed.

-Ekr