Subject: RE: Collisions irrelevant

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

Thats 32 bytes of course.

> -----Original Message-----
> From: Hallam-Baker, Phillip [mailto:[email-masked]]
> Sent: Saturday, September 18, 2004 11:12 AM
> To: 'Robert Elz'; Ben Laurie
> Cc: Alex Bligh; [email-masked]
> Subject: Collisions irrelevant
> 
> 
> 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/>
> 

--
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: "Hallam-Baker, Phillip" <[email-masked]>
Date: Mon, 20 Sep 2004 09:00:41 -0700

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

Yes, the collisions between members of the same set are irrelevant. It is
when you have a collision between A and A' that you have the issue.

> 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, :-)

The chance of this ever happening is somewhat less than the chance that a
giant meteor will collide the planet causing everyone to turn into oil.

If this really is a concern then what we could do is to have a system
whereby in the case of a collision the server returns the value that results
in the collision.

---

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Mon, 20 Sep 2004 14:02:01 -0700

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

OK now I get it, yes this works for me. I can make the 
probability of having to release a record to be considerably 
less than the probability of being hit by a giant asteroid.

I can certainly make the probability way less than the 
probability of a machine error in the signing unit.

Security is risk control, not risk elimination.