Subject: Re: Avoiding collisions - desirability & possibility thereof (was Re: dictionary attack on nameservers)

From: Mark Andrews <[email-masked]>
Date: Wed, 15 Sep 2004 08:10:36 +1000

> Robert Elz wrote:
> >   | it's trivially easy (and computationally
> >   | efficient) to find a value S such that there are NO values i, j such th
> at
> >   | Y(i) = X(j) - I'll call that finding a non-colliding salt value S such 
> that
> >   | there are no collisions between the range and domain of the hash functi
> on.
> > 
> > I think you're relying upon probabilities, which doesn't work in a situatio
> n
> > like this.
> 
> DNSSEC already relies on the probability that two strings don't have the 
> same hash - if they did, then a signature could be used to prove fake data.

	But collisions over the rdata do not impact on the lookup
	algorithm.  Collisions in the namespace do impact on the
	lookup algorithm.
 
> Cheers,
> 
> Ben.
> 
> -- 
> ApacheCon! 13-17 November! http://www.apachecon.com/
> 
> http://www.apache-ssl.org/ben.html       http://www.thebunker.net/
> 
> "There is no limit to what a man can do or how far he can go if he
> doesn't mind who gets the credit." - Robert Woodruff
> 
> --
> 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/>
--
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: Wed, 15 Sep 2004 08:04:26 +1000

> Edward Lewis wrote:
> > I'm lost on the issue of "avoiding" collisions.
> > 
> > I've been trying not to jump into this as we haven't set up the 
> > requirements (in a draft yet) for the problem, but:
> > 
> > 1) What if authenticated denial was different for sets at an existing 
> > name than for name errors?  I mean, in RFC 1034 returns "no error" if a 
> > name exists but data doesn't, and a "name error" if the name doesn't exist.
> > 
> > 2) So, what if we take care of "no error, no data" by just using NSEC's 
> > like:
> >      owner NSEC owner <types it has>
> > 
> > 3) For name errors, just return:
> >      H(owner1) NXD H(owner2) for any H(owner1) < H(query) < H (owner2)?
> > 
> > The implications - the zone data no longer needs to be sorted (no 
> > lexical ordering of names).  The table of hash records need not sully 
> > the data space, so who cares about collisions?
> 

	The data doesn't have to be sorted but the hashes do.  "6 of 1,
	half a dozen of the other" as far as I am concerned.

> Precisely my point!
> 
> > Okay - maybe H(missing name) = H (owner3)...like I've said, I have been 
> > trying not to think about this until the time has come for the 
> > discussion on solutions.
> 
> Hash collisions are fantastically unlikely. With salt you can make them 
> never occur, anyway. Plus, if they were a problem, then you would have 
> the same issue with signatures, but I don't see anyone bringing that one up.

	You are incorrect.  All the current schemes have a hash of less than
	64 octets.  There will ALWAYS be a possibility of collision even
	after trying every salt as it is impossible to make the hash space
	larger than the pre-hash space.

---

From: Mark Andrews <[email-masked]>
Date: Wed, 15 Sep 2004 21:48:09 +1000

> --On 15 September 2004 08:04 +1000 Mark Andrews <[email-masked]> 
> wrote:
> 
> But the pre-hash space is sparse, and we only care about collisions of
> ACTUAL values in the pre-hash space, not potential values. IE (assuming all
> octet values are OK and 64 byte labels for the sake of argument) there are
> the pre-hash space is size 256^64 and the hash space is smaller (let's say
> we represent them as alphanumerics so 36^64) - which is presumably your
> complaint. Note 256^64 is approximately 10^153, and there are about 10^79
> atoms in the universe, so I predict in applications the pre-hash space will
> be sparse as even if we could represent one RR in just one atom, we are way
> off filling the zone :-) So this doesn't matter provided there is a
> limitation on the number of RR's in a zone - the limitation doesn't have to
> be impactful - If it was 10^76 (number of atoms in the universe over 1000),
> we'd still have 10^79 possible salt values to work through, i.e. about 263
> bits of salt. And as I pointed out earlier, as 76*2<153, the expected
> number of iterations to find a salt that works is less than 2.
> 
> I do not think limiting a zone file to 10^79 RRs is going to have
> a significant deployment impact.
> 
> Alex

	You can't write a draft assuming that there won't be collisions.
	There will ALWAYS be the possibility of collisions (salts only
	reduce the probability) and you have to take those into account.

	You have to describe what to do when you have a collision.  Don't
	say they won't occur because they will.

	For RRSIG the impact of collisions is that there are two (or more)
	RRsets that you cryptographically prove they are different.

	For name hashes you end up with different names with possible
	different sets of types that you some how have to merge.  If the
	sets are identical I don't think there is a issue but it would need
	to be discussed.

	You will also have occasional false matches (names that you
	can't prove that don't exist).  There MUST be names for which
	this will occur.

	Mark

---

From: Mark Andrews <[email-masked]>
Date: Wed, 15 Sep 2004 23:53:21 +1000

> At 8:04 +1000 9/15/04, Mark Andrews wrote:
> >
> For a lookup resulting in an answer, you don't need to access the 
> hashes.  So, for all positive hits, you can go back to the old means 
> of storing a zone's contents in memory.
> 
> Only for lookups resulting in negative answers do you have to have a 
> sorted list of things to respond with.

	The same is true of NSEC.

> Well, I believe that.  Still I don't understand why collisions are a 
> problem.  Perhaps because I am assuming that you'd only need to give 
> out hash answers in name errors, so the list of RRSETs doesn't matter.

	The problem is that by using hashes there you are creating
	sets of QNAMES for which you cannot return NXDOMAIN securely.
	One set for each hash in use.
	
	If you have collisions with hashes of names with data you cannot
	hand out NODATA responses securely.  Yes, Roy you can exhaust
	salt space.

> -- 
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
> Edward Lewis                                            +1-703-227-9854
> ARIN Research Engineer
> 
> "I can't go to Miami.  I'm expecting calls from telemarketers." -
> Grandpa Simpson.

---

From: Mark Andrews <[email-masked]>
Date: Thu, 16 Sep 2004 00:04:13 +1000

> At 21:48 +1000 9/15/04, Mark Andrews wrote:
> 
> Why not just include both records as an RRset?

	Because you can now spoof away data that exist.
 
> I think this is why I'm thinking we should have split the problem 
> into solving "name error" proofs and "no data" proofs.
> --

---

From: Mark Andrews <[email-masked]>
Date: Thu, 16 Sep 2004 08:09:03 +1000

> At 23:53 +1000 9/15/04, Mark Andrews wrote:
> ?  I'm probably not on the same wavelength about hashes.  I think the 
> hash space needn't be considered part of the DNS data tree, just a 
> transformation of existing names into an obscured representation. 
> I.e., in a response message with a name error in the return code, the 
> verifier ought to realize that the negative answer proof records are 
> using transformed names, not plain text names.

And the transformed QNAMEs WILL collide on occasions with the transformed
names of the existing names in the zone.

> Let's say the labels in a zone are {chamberlin erving julius wilt} 
> and the corresponding hash values are { 6  9  13 } with a collision.
> 
> Let's say I ask for ( robertson, IN, TXT ) and the hash of robertson is 9.
> 
> Hmmm, I picked out 9 by randomly hitting a key and seeing that I 
> managed to pick a collision between the qname and one or more members 
> of the zone.  Will this still work out?
> 
> So, I get back a "name error" with "9 NSEC7 13" in the authority 
> section.  After verifying the record (via the RRSIG), what next?  I 
> suppose it's then possible to a victim of an insertion attack - an 
> interloper passes back this collision with there being a genuine 
> robertson in the zone.

	The problem is that you can't return 9 NSEC7 13 + NXDOMAIN.
	The NSEC7 says that robertson exists.  The RCODE says that
	it doesn't.  IT DOES NOT WORK.

	To make HASHES works you need to make the HASH longer than the
	namespace and also guarantee that the hashes are unique for
	all possible inputs.  One could then take the hash use the first
	n octets as the name and store the remainder in the record to
	deal with collisions.  This will however make NSEC7s large.

	Instead of hashing into 16 octets you need to hash into 512 octets.
	Something larger than the input space (63 or 255 octets) .

> What if there the qname's hash was 10?  In that case, I don't see a 
> problem in the collision amongst zone members.
> 
> But - it's the collision between qname and zone content - which isn't 
> possible to know at signing or serving time - that might be a problem.
> --

---

From: Ben Laurie <[email-masked]>
Date: Thu, 16 Sep 2004 00:30:40 +0100

Chris Thompson wrote:
> Mark Andrews writes: 
> [...snip...]
> Maybe a different mechanism for securely returning NXDOMAIN is needed
> in these cases? If a name being looked up hashes to something different 
> from every extant name, return the signed NSEC' record to prove it by
> showing an interval of hash values free of extant ones. But if the hash
> matches that of one or more extant names, but the name isn't any of them, 
> then return a signed NSEC'' record that lists all the extant names that 
> hash to that value (proving that the caller's wasn't one of them). That 
> gives away one or more names in the zone, of course, but the caller had 
> to be pretty damn lucky to get a hash match in the first place.
> 
> This idea is somewhat half-baked, in that representing a list of names 
> of potentially unlimited length in a signed answer could pose problems.
> (Although now you really could play "change the salt, Walt" to finesse 
> that.)

The way to fix this is to show an NSEC record when NSEC' fails because 
of a hash collision.

Since a good fraction of the world thinks that NSEC' is pointless, 
there's no chance that NSEC is going away, making this solution cheap, 
as well as (of course) 100% effective.

People actually bothering to sign NSECs in case this happens before the 
Sun burns out will spend twice as much on hardware, but the edge case 
has been handled totally.

Excellent suggestion. Superb. Thankyou.

Cheers,

Ben.

---

From: Mark Andrews <[email-masked]>
Date: Thu, 16 Sep 2004 09:57:38 +1000

> Jim Reid wrote:
> >>>>>>"Ben" == Ben Laurie <[email-masked]> writes:
> > 
> > 
> >     Ben> I agree, in theory. However, in practice, there's no way to
> >     Ben> have a zone with size 2^512, or even 2^160, so this is not a
> >     Ben> problem in real life.
> > 
> > Once upon a time people said that about MD5. There was supposedly no
> > realistic chance of two different input strings yielding the same hash.
> 
> People said it was practical to have a zone of size 2^128?
> 
> The unrelated fact that there exist broken hashes is by no means a 
> disproof of the general concept that there are an awful lot of possible 
> outputs from cryptographic hash functions.

	The zone size is irrelevent.

	If the number of QNAMES > number of hash function outputs
	(true of all the proposals todate).

	You will have collisions.  They CANNOT be prevented.

	The only way to prevent this is to change the hash function
	so that the number of QNAMES <= number of hash outputs *and*
	that for all QNAMES the output is unique.  You then have
	the problem of how to store the resultant hash.

	For NSEC the hash function returns its input.  It also meets
	all the required properties above.

	Now we know the QNAME space.  You need to pick a hash
	function that has the properties above.  So far I have
	yet to see anyone propose one.

	Mark

---

From: Peter Koch <[email-masked]>
Date: Fri, 17 Sep 2004 12:02:08 +0200

Alex Bligh <[email-masked]> wrote:

> You get "IN MX 10 target.". The zone is generated to be non-SELF-colliding
> so the only record at H is an NSEC' record. Returning an NSEC' record
> for ANY type of query other than NSEC' is ALWAYS a bad idea.

but that interferes with how wildcards work. The name H exists (per the NSEC
RR), so the wildcard doesn't apply - regardless of QTYPE.

> The situation is no different from the zone
>     * IN MX 10 target.
>     www IN A 10.11.12.13
>     H IN TXT "foobar"
> 
> If you do a query of type MX for H, you would not expect the TXT record
> to be returned, you'd expect the wildcard MX to be returned. And just

One might expect that, but it again isn't how wildcards work (see parallel
thread).

The basic problem is that hashes, if they use the same namespace (and currently
there is no alternative) will introduce new names into the zone. The not so
trivial question is whether this is an academic problem or whether it can
lead to problems or be abused. Look, for example, at those NSEC' RRs which
deny their own existence.

-Peter

---

From: Alex Bligh <[email-masked]>
Date: Fri, 17 Sep 2004 11:27:18 +0100

> One might expect that, but it again isn't how wildcards work (see parallel

OK - I wondered if Robert might mean that, so I set up a test before
posting. Try
  dig MX H.example.alex.org.uk

I get:

;; ANSWER SECTION:
H.example.alex.org.uk.  494     IN      MX      10 target.example.com.

No mention of:
;; ANSWER SECTION:
H.example.alex.org.uk.  360     IN      TXT     "HASH"

Or are you saying that's changed in DNSSEC?

Alex

---

From: Edward Lewis <[email-masked]>
Date: Fri, 17 Sep 2004 09:29:24 -0400

>>  Let's say I ask for ( robertson, IN, TXT ) and the hash of robertson is 9.
...
>	it doesn't.  IT DOES NOT WORK.

You can - if it's defined to be allowed.  Name error means that the 
name desired is not found - not that the hash of the name is not 
found.  (We've never defined any semantics for hashes of names.)

OTOH, even if you define a hash mess to avoid collisions at signing 
time, you can't guarantee against a query name's hash clash.

And OTOH - I agree with KRE, this is a lot of noise about a non-issue.

---

From: Mark Andrews <[email-masked]>
Date: Sat, 18 Sep 2004 08:04:20 +1000

> time, you can't guarantee against a query name's hash clash.

	Thank you Ed.  You at least are repeating (if not hearing)
	what I have been saying.
 
	robertson was the QNAME the has was 9.