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

From: Alex Bligh <[email-masked]>
Date: Thu, 16 Sep 2004 15:03:49 +0100

--On 16 September 2004 09:57 +1000 Mark Andrews <[email-masked]> 
wrote:

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

Aaahhhhhhh - you are talking about a different type of hash collision.

I have previously been talking about collisions either between the hashed
values of two RR labels, or between the hashed value of one label and the
unhashed value of the other. These are avoidable [1] because the number of
labels (and thus the number of hashed labels) in the zone is limited.

You are (here), I think, talking about potential collisions between the
hashed value of a QNAME, and hashed values of RR labels in the zone file,
where the unhashed QNAME does not correspond to the RR label.

I now understand the comment "if you find one of these you get to be famous
on serving the record".

However, I don't think it necessarily breaks anything.

Let's assume you agree with [1] above (that you can create a zone without
collisions with "itself") which I'm pretty sure is correct.

Now the problem to be solved is that there is a very large number of
possible QNAMEs and it is possible (albeit unlikely) that a query is made
with a QNAME which has the same hash with something already in the zone
file.

So let's assume that there are a set of labels P(1)..P(n) in the zone which
are ordered by hashed order, and that they we have a non-colliding salt,
meaning there is a value S such that:
* For no i,j, H( P(i), S ) = P(j)
* For no i,j, i!=j, H( P(i), S ) = H ( P(j), S)

And let's further assume we have a colliding Query Q, such that
for some k,

  H(Q, S) = H( P(k), S ), but P(k) != Q

Now, if someone makes a query for Q, BY ASSUMPTION the zone is non-self
colliding, so RR Q does not exist (else RR Q would have the same hash as
P(k) and we'd have chosen a different salt - as we could detect this at
zone preparation time).

So if we return an NSEC-x record that says "there are no RR's in the [open]
interval H(P(k), S) ... H(P(k+1), S)", that also implies that there ARE
RR's at P(k), and P(k+1), and thus BECAUSE the zone is non-colliding with
itself (see [1]), that OTHER than the exact label names P(k), P(k+1), there
are no other RR's with the same hash and thus "there are no RR's in the
[closed] interval H(P(k), S) ... H(P(k+1), S)) other than P(k) and P(k+1)".
Provided the reply contains the QNAME whose existence is being denied,
the "other than" cases can be distinguished.

Thus I think that provided we have (as described in a previous email)
prevented the zone from colliding with itself, we can still effectively
do an authenticated denial of existence for a QNAME whose hash collides
with an RR which is present, and for that RR.

Alex

--
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: Roy Badami <[email-masked]>
Date: Thu, 16 Sep 2004 15:38:58 +0100

Alex> Now the problem to be solved is that there is a very large
    Alex> number of possible QNAMEs and it is possible (albeit
    Alex> unlikely) that a query is made with a QNAME which has the
    Alex> same hash with something already in the zone file.

I think even that will make you famous, assuming you're using
full-length SHA-1.

Someone needs to do that maths and estimate an upper bound on the
probability of this ever happening.

ie assume that:

   * the distribution of the output of SHA-1 is uniformly distributed
   * we have the largest zone we can ever imagine
   * we have the largest number authorative namesservers we can imagine
   * these nameservers are the fastest we can imagine
   * they are speding all their time answering queries for random non-existent
     names

And then work out the probability of *ever* seeing a collision
assuming 160 bit hashes.

Let's choose some figures for the above, and then work out whether
this is worth worrying about.

     -roy

---

From: Robert Elz <[email-masked]>
Date: Fri, 17 Sep 2004 01:39:26 +0700

Date:        Thu, 16 Sep 2004 15:38:58 +0100
    From:        Roy Badami <[email-masked]>
    Message-ID:  <[email-masked]>

  | 
  |     Alex> Now the problem to be solved is that there is a very large
  |     Alex> number of possible QNAMEs and it is possible (albeit
  |     Alex> unlikely) that a query is made with a QNAME which has the
  |     Alex> same hash with something already in the zone file.
  | 
  | I think even that will make you famous, assuming you're using
  | full-length SHA-1.

Perhaps.

But that isn't really the one that is interesting.   Assuming the hashes
are in the zone as owner names (if they're not, then I don't care in the
slightest about clashes - others might - but that's just the security
algorithms, etc, which are outside my field of interest) then the clash
that matters (in this area) is when the QNAME clashes with a NSEC' hash.

And that isn't even slightly hard to imagine - I simply query for any
random nonsense, get back the NXDOMAIN/NODATA, along with the NSEC' record,
take the hash value from it, and do a query on that as a QNAME.

So, let's assume that in the example.com. zone I have

	* IN MX 10 target.
	www IN A 10.11.12.13

(along with the NS and SOA records for the zone itself of course, but they're
not adding any new names).   That's it.

Now, I query for foo.example.com (type A), get back NODATA and a NSEC' record
that demonstrates that "foo" doesn't exist (along with whatever else is
required to generate the right answer proof, which I don't care about here).
For the purposes here, let a hash value in the NSEC' be H.

Now I query for H.example.com. (MX).

What do I get here?    If I get NODATA, then you have just broken my
wildcard MX.   If I get "IN MX 10 target." then you have just broken the
DNS lookup algorithm.

Neither is acceptable.

More than that, I assert that my domain (as example.com. in the above)
is mine - I registered it, and I decide what names go in it.   You (being the
IETF or any other standards body) have no business whatever creating names
in my zone - no names whatever.   That's my ballpark to play in.   And this
is a much more fundamental principle than having non-enumerable zones.

kre

---

From: Alex Bligh <[email-masked]>
Date: Fri, 17 Sep 2004 10:42:42 +0100

--On 17 September 2004 01:39 +0700 Robert Elz <[email-masked]> wrote:

> (along with the NS and SOA records for the zone itself of course, but
> they're not adding any new names).   That's it.
>
> Now, I query for foo.example.com (type A), get back NODATA and a NSEC'
> record that demonstrates that "foo" doesn't exist (along with whatever
> else is required to generate the right answer proof, which I don't care
> about here). For the purposes here, let a hash value in the NSEC' be H.
>

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.

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
the same happens with the example you have above with
   * IN MX 10 target.
   www IN A 10.11.12.13
   H IN NSEC' blah

Alex

---

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

(Replying to myself).

> with an RR which is present, and for that RR.

Hmmm... I've been thinking about this a bit more.

Here is a demonstrable potential problem with hash collision:

Let us assume you have a non-self-colliding zone with salt S - which
I allege one can generate:

; exampel.com presented out of order for clarity

	xxx	IN	MX	1.1.1.1 ; Hash is 1000
	foo	IN	MX	2.2.2.2 ; Hash is 2000
	bar	IN	MX	3.3.3.3 ; Hash is 3000

	...	IN	NSEC'	1000
	1000	IN	NSEC'	2000
	2000	IN	NSEC'	3000
	3000	IN	NSEC'	...

As the hash space is smaller than the QNAME space (assuming we don't want
to use all 8 bits to represent hashes that's always the case), then there
WILL always be a finite number of QNAMEs having the same hash values as
some of the labels in the zone (though they will be stupendously difficult
to find).

Let's assume, however, that we have one, for instance baz.example.com which
ALSO has hash value 2000.

I do an MX query for baz.example.com. I get back a proof (manner
irrelevant) that says hash values 2000 - 3000 (exclusive) don't exist. Now
according to my previous posting, I could infer from getting that back that
baz.example.com does not exist, as I know there is a label with hash value
2000 that does exist, and the record with hash value 2000 WAS
baz.example.com, then I'd have got back an MX record (not a denial of
existence).

But a (potential) problem arises here: If I do an MX query for
foo.example.com, and some interloper captures the response and substitutes
it for the same denial of existence as above (i.e. the same one I'd have
got asking for foo.example.com), then by my own logic, I'd have to conclude
that foo.example.com didn't exist (or I'd have received an MX record back).

What I think this means is that any NSEC' proof of the sort above can only
disprove the existence of hash values 2001-2999 (etc.) and the existence of
a single (unspecified) record with hash value 2000 (and similarly with
3000). One cannot draw an implication as to whether that record is, or is
not, the QNAME (if one worries about hash collisions with QNAMEs).

Now clearly the label could always be returned in the NSEC' reply, but that
would get us back to enumerability.

I think the way to fix this is as follows: if the QNAME does not
have the same hash as any record (i.e. falls into the open interval
between NSEC' records), then simply return then NSEC' record. So
if the QNAME has hash 1001, the resolver, seeing there are no records
between (open interval) 1000 and 2000, can assume the QNAME does not
exist.

In the circumstance where there *IS* a hash match, in the response,
return the original label that generated that hash. So in the case
above of a query for baz.example.com (hash 2000), return foo.example.com,
as well as the normal NSEC' proof. Now this could either be done
by returning additional records (though I'm not sure those always
get passed through the system enough) which would be cleaner, or
failing that by having two presigned NSEC' proofs for the
interval 1000,2000, one with foo.example.com (to be returned to
deny existence of QNAMES with hashes of 1000 exactly), and one without
(to be returned to deny existence of QNAMES with hashes of 1001-1999
inclusive) - (NB QNAMES with hash exactly 2000 go into the next pair
of NSEC' records). This doesn't enable enumerability for a strong
hash as in order to get the record back with foo.example.com in,
you'd either have to already know foo (which is hard), or to be
able to break the hash (i.e. generate an arbitrary QNAME with hash
1000). The latter as we know is computationally extremely difficult.

The unlikelihood of the second form NSEC' records ever occurring might
make interoperability testing difficult. This could be resolved by
making a deliberately weak hashing mechanism mandatory for interoperability
testing.

Alex