Subject: Collisions irrelevant

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Sat, 18 Sep 2004 08:11:44 -0700

I read part of the collisions thread.

The whole discussion is irrelevant. Consider the requirements:

We have a set of names A = {a0, a1,... an }

We have a bag of hashes H = {H(a0), H(a1), ... }

Let us imagine that we do have a collision such that

H(ai) = H(aj)

All this means is that the number of intervals that we need to sign is less
than the number of names.

The real issue that comes up is when you have a collision in the compliment
set X = A' = {x0, x1, ... xm}

H(ai) = H(xj)

This means that you will be unable to provide a response that proves xj does
not exist.

If we use SHA1 we can reduce the probability of this occurring to 2^160 / n.

The probability that the machine will have a failure is much greater than
that.

If people are really worried we can use SHA256. and still only need 32 bits.

--
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: "Olaf M. Kolkman" <[email-masked]>
Date: Mon, 20 Sep 2004 08:39:13 +0200

>This means that you will be unable to provide a response that proves xj does

As in A'  is the set of names that are not in the zone?

Let me see if I understand this.  If I cannot proof that the record does 
not exist I'd would expect data that I queried for (Q-truple). At least 
a piece of data that provides proof that at the xj ownername (QNAME) 
there is no such type as QTYPE.

I get no such data and I get no data of the nonexistence of the 
ownername xj.... error case. This could be used for a DOS attack on the 
server, if the client requeries in case of the above error case. 
Security considerations can address this.

handwave, handwave, :-)

--Olaf
  namedropper.

---

From: Alex Bligh <[email-masked]>
Date: Mon, 20 Sep 2004 11:24:53 +0100

--On 20 September 2004 08:39 +0200 "Olaf M. Kolkman" <[email-masked]> wrote:

> not exist I'd would expect data that I queried for (Q-truple). At least a
> piece of data that provides proof that at the xj ownername (QNAME) there
> is no such type as QTYPE.
>
> I get no such data and I get no data of the nonexistence of the ownername
> xj.... error case. This could be used for a DOS attack on the server, if
> the client requeries in case of the above error case. Security
> considerations can address this.

You have to distinguish between a query for the Q-tuple relating to
ai and a query relating to xj, remembering that in the denial of
existence record, UNIFORM non-enumerability as proposed thusfar suggests
that you cannot reveal the QNAME for ai.

The problem is that you cannot deny x(j) as the only available interval for
denial is H(a(i)) ... H(a(i+1)). You have two strategies:

1. If you treat that as an open interval, you are not denying H(a(i)) and
H(a(i+1)) (just the hash values between them) and thus can't use this to
deny x(j) which has the same hash as H(a(i)).

2. If you treat it as a closed interval (i.e. as denying H(a(i)) itself and
thus denying x(j)), you have to make an exception for a(i) itself
(obviously) which can only be done by the presence of other records (QTYPE
for instance). If resolvers worked that way (by policy, to cope with
potential hash collisions), they'd then be open to an attack (even with out
an ACTUAL hash collision) involving interception and removal of the all
replies except the NSEC', which would lead the resolver to ASSUME a hash
collision had occurred and say "I have an NSEC' but no other records, I
thus assume this is the xj case, IE something with the same hash as
something in the zone", i.e. an easy man-in-the-middle attack which falsely
denies the existence of any RR (and indeed falsely makes the resolver think
the server has become 'famous').

There is a third strategy which I outlined earlier, and which Ben
independently came up with a far better version (off-list). That is simply
that if there is a query x(j), which is non-existent but has a hash equal
to an existing record, you simply return a traditional NSEC record [*],
rather than an NSEC' record (as the resolver has to cope with either for
denial anyway, this complicates nothing). This will allow zone
enumerability only to the extent the attacker can find a colliding hash for
each RR (i.e. in practice not at all). This addresses Phil's problem (which
is the same as the one I posted marked "this *is* a problem"), and together
with salting for non-self colliding, I think this addresses all the hash
collision problems.

[*] this has the minor nit that you'd clearly want to avoid returning NSEC
records in response to queries of QTYPE NSEC in an NSEC' zone, which is
arguably a bit of special server behaviour for NSEC to support NSEC'
functionality. An alternate approach is just to allow NSEC' records with
any hash algorithm, and specify that two mandatory hash algorithms are
SHA-1 (or whatever) and the identity mapping. Then return identity (read
unhashed) NSEC' in the case of a query for a colliding hash such as x(j).

Alex