Subject: Re: Minor editorial NSEC3 comments

From: Alex Bligh <[email-masked]>
Date: Fri, 11 Mar 2005 08:42:08 +0000

--On 11 March 2005 00:42 +0000 Roy Badami <[email-masked]> wrote:

> Collision resistance is another specific property of cyrtographic
> hashes, namely that it is computationally infeasable to construct a
> pair of messages that hash to the same value, and AFAICS NSEC3 doesn't
> actually require a collision resitant hash function.
>
> Collision restistance implies second pre-image resitance: if you've
> managed to break second pre-image resitance then you have necessarily
> constructed a collision, but second pre-image resitance is a weaker
> property of a hash than collision resitance.

I think there are actually 2 separate requirements:

* Second pre-image resistance - to stop enumeration "the obvious way"
  (work backwards from the hashes).

* Collision resistance - to stop a "nit" in the protocol. This is the
  one everyone talked about for a ages here. If there isn't collision
  resistance, then can't an attacker find QNAMEs with the same hash
  value as labels in the zone? If they do this, we are then left with
  the problem of what the server should return when a query is made
  for that (presumably nonexistant) QNAME. I think the consensus was
  to return an NSEC3 record with the identity (1:1) hash. This enumerates
  a single label. This isn't dangerous if the main algorithm is
  collision resistant.

No caffeine yet so my brain may not work, but I *think* this means
that both collision resistance AND second-preimage resistance are
necessary. I think you are right that collision resistance implies
second pre-image resistance, but I don't think that's the issue
here, as both are required anyway.

You are right in another way though: NSEC3 doesn't (well IMHO shouldn't)
require ANY of those properties of its hash function, UNLESS you
care about enumeration. NSEC3 should be able to cope with ANY function
(whatsoever) as the hash function, though the worse hash function it
is (and the smaller its range is compared to its domain), the more
important a functional fall-back to the identity hash becomes.

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: Ben Laurie <[email-masked]>
Date: Fri, 11 Mar 2005 14:57:58 +0000

Roy Badami wrote:
> 6.4.2 says....
> 
>     A collision resistant hash function has a second-preimage resistance
>     property.  The second-preimage resistance property means that
> 
> I am not a cryptographer, but...  While true, I don't think this is
> relevent. I would reword this to say
> 
>     A cryptographic hash function has a ...

I managed to miss this one, you are, of course, correct.

> Weaker in the sense that it is possible to break the collision
> resistance of a hash without breaking second pre-image resistance (ie
> I may be able to construct one or more pairs of messages that hash
> to the same value, assuming I get to choose both messages, but that
> doesn't mean I can construct a message that hashes to the same value
> as a message _you_ choose...
> 
>    The probability of finding a second preimage is 1 in 2^160 for
>    SHA-1 on average
> 
> This is clearly not true, unless the adversary simply tries one
> possible preimage at random and gives up if he hasn't succeeded.  Just
> by trying two random preimages you can increase the probability to 1
> in 2^159, and perfoming two SHA-1 operations within a reasonably
> timeframe is possible even on the most modest of hardware :-)

I thought I'd already fixed this language.

> 
> An attacker can clearly attempt a very large number of test hashes,
> but also cryptanalysis of SHA-1 may allow less computationally
> intensive attacks than random tests...
> 
> You can't put a figure on the probability of breaking second preimage
> resistance; cryptography doesn't work that way.  It's conceivable
> (though incredibly inplausible) that someone (perhaps the NSA?) is
> capable of producing a second preimage with probablility 1.

Yes, what we should say is that the work factor for finding a second 
preimage is of the order of 2^160.

Cheers,

Ben.

---

From: Ben Laurie <[email-masked]>
Date: Fri, 11 Mar 2005 16:46:30 +0000

> important a functional fall-back to the identity hash becomes.

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. 
However, it seems to me that this would then require the zone to use the 
identity hash for the whole zone. Why? Because the colliding hash cannot 
be included in a hashed NSEC3, since that was the problem in the first 
place, but if it is not included, then there will be an NSEC3 record 
that denies the existence of the colliding pair. This NSEC3 could be 
replayed by an attacker, instead of the identity NSEC3 the server would 
prefer.

Hence, there will be a hash range for which there can be no denial 
records. All names falling into that range will have to be identity 
hashed (OK, perhaps the problem doesn't spread to the whole zone, but it 
certainly spreads, and I can't quite get my head around whether the 
spread is limited at this time - in any case, this strikes me as a 
significant problem).

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

On a related note, I keep wondering I continue to care about collisions, 
despite there obvious bogosity, and there appear to be two answers. 
First, just for academic completeness, and second to reduce the impact 
of a broken hash function.

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.

Cheers,

Ben.

---

From: Alex Bligh <[email-masked]>
Date: Fri, 11 Mar 2005 18:26:08 +0000

Ben,

> 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:
	<something>		NSEC3	H(x)
	H(x)			NSEC3	<somethingelse>
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:
	<something>		NSEC3	H(x),	ALG=SHA-512
	<anotherthing>	NSEC3	x,	ALG=Identity
	H(x)			NSEC3	<somethingelse>
	x			NSEC3	<yetanother>,	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.

> is unimportant in any case).

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

> 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

---

From: Mark Andrews <[email-masked]>
Date: Sat, 12 Mar 2005 03:24:10 +1100

> important a functional fall-back to the identity hash becomes.

	Not quite ANY function.  The size of the hash space must be
	bigger than the number of records in the NSEC3 chain.

--
Mark Andrews, ISC
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742                 INTERNET: [email-masked]