Ben,

--On 11 March 2005 16:46 +0000 Ben Laurie wrote:

> I've been thinking about this some more, and I can't see how it would
> work.
>
> The idea, as I understand it, is that if one finds a pair of names whose
> hashes cannot (in reasonable time) be disambiguated, then one instead
> inserts an NSEC3 record with the identity hash at that ownername.


No, you misunderstand what I am saying. Probably my fault as I made the
mistake of putting both hash collision types in a single message. Here they
are, completely separately.

HASH COLLISIONS ON NSEC3 CREATION / ZONE SIGNATURE
==================================================

I agree that you should never have two names (call them x1, x2) where
the hashes collide i.e.
H(x1,S) = H(x2,S) where S is the salt and H(x,S) is the hash of x

This type of collision can be detected at signature time. It's a problem
for the reason you mention and no doubt other reasons too. The solution is
to pick another value S' (at signing time - by which I technically mean
NSEC3 creation time which comes prior to signing time and doesn't require
the signature stuff, but that's another story). I presented what I think is
a proof that if the hash function satisfies sensible properties, and the
size of the hash range is more than the square of the number of zone
entries, then the expected value of the number of iterations to find a
suitable salt that produces no collision is less than 2. It can thus
be safely coded in a loop like:
ASSERT ( numberofrecords ^2 < hashfunctionsize, "wrong hash func")
int i=0;
do
{
S = random(...); // with lots of bits
MakeHashes (zone, S)
ASSERT ( (i++ > 1000) , "Please shoot Alex"); // if you must
} while (AreAnyHashesTheSameValue(S));

as the second assert will statistically never trigger (you have more
chance of breaking the 2nd pre-image resistance property).

HASH COLLISIONS BETWEEN A QNAME AND A NAME AT QUERY TIME
================================================== ======

This is where a query for name q is made, and H(q,S)=H(x,S) for
some existent record X. In layman's term, there is an NSEC3 record
with the same hash as existent record x, where q!=x.

Now, because we know (see above) we would not have created the zone
if there were two existent records with the same hash) we also know
(as q!=x by definition), that the record q is non-existent. We would
then have the (arguable) problem where for some queries there will
be an NSEC3 record which has one end equal to H(x), i.e there will
be two records like:
NSEC3 H(x)
H(x) NSEC3
That may imply to a resolver (querying q) that q exists, because
H(q) exists (being H(x)) at an NSEC3, which gives the potential
for things being misled.

Note that whilst I heard the argument that there is a potential
for things being misled here,
a) I was never convinced it was an actual threat (or if I was,
I've forgotten why), and
b) We should detect this and pipe it to a mail program pointing out
we'd found a hash collision if the algorithm is meant never
to generate one,
but some people seem to be worried about this, and it seems to me
a useful thing to sort out (i) to put those people's minds at
rest and (ii) so we can support weak hash functions and/or we
know that if SHA-512 or whatever does turn out to be weak, the
worse that has happened NSEC3-wise is that zones become enumerable,
not that there is a new threat (the one in (a) I don't understand
quite what it is :-) ).

So what I am suggesting, is for those people worried about this
or wanting to support weak hash algorithms that may collide (no
problem with the identity hash), at NSEC3 generation time, NSEC3s
are generated with the identity hash too, so we have:
NSEC3 H(x), ALG=SHA-512
NSEC3 x, ALG=Identity
H(x) NSEC3
x NSEC3 , ALG=Identity
There are thus two NSEC3 chains (linking the records in a different
order, obviously), one using SHA-512, and one using Identity hash,
which is practically identical to existing NSEC treatment.

However, the identity hash NSEC3 is never returned, except under
one circumstance, which is as follows. When it is desired to
deny the existence of a QNAME q, then we see whether H(q) exists
within the current zonefile (we already know q doesn't exist, or
we wouldn't be attempting to deny its existence). If H(q) does
exist, we have found a q and an x, such that
q!=x, H(q)=H(x)
which is the sort of collision we are talking about. So, first
we mail some crypto mailing lists if H was a strong hash. Next
we return the alternate NSEC3 record with the identity hash that
covers the record q. The resolver has now managed to elucidate
two zone entries (the two zone entries at either end of the interval),
but in order to do this, he had to do the computationally infeasible,
i.e. find a hash collision.

> Mark Andrews suggested a related solution, and that is to include in the
> hashed NSEC3 record a field which can be set to the unhashed ownername.
> If there is no collision this field is not set (or is set to ".", or
> something), but if there is a collision, then the zone includes two
> versions of the NSEC3, one for each of the colliding names. This, of
> course, reveals those names, but only the collding names. This prevents
> an attacker being able to use the collision to deny RTYPES at either of
> the names (of course, if they have the same RTYPE bitmap, then collision
> is unimportant in any case).


OK, that might solve the "colliding RRs", but why not just not use
the problematic salt value?

> Since the cost of this proposed solution is, almost always, a single
> byte, it might be as well to include it simply so we can bury this dead
> horse. In fact, we could even reduce the cost to a single bit by
> signalling the existence of the field, rather than always including it.


I think the only problem that needs to be solved (for academic
completeness) is the colliding name and QNAME issue. I can't
see why colliding RRs are a problem. I banged this point to death
on the list before I realized (doh!) people were actually talking
about QNAME and existent RR collisions. Perhaps because I was talking
at such a tangent to the thread at the time, everyone (understandably)
ignored it and/or failed to point out some obvious flaw.

Alex

--
to unsubscribe send a message to namedroppers-request@ops.ietf.org with
the word 'unsubscribe' in a single line as the message text body.
archive: