Alex Bligh wrote:
> --On 11 March 2005 00:42 +0000 Roy Badami 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.

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

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.



to unsubscribe send a message to with
the word 'unsubscribe' in a single line as the message text body.