Subject: Re: Avoiding collisions - desirability & possibility thereof (was Re: dictionary attack on nameservers)

From: Roy Arends <[email-masked]>
Date: Wed, 15 Sep 2004 15:06:59 +0200 (CEST)

On Wed, 15 Sep 2004, Mark Andrews wrote:

>
> > --On 15 September 2004 08:04 +1000 Mark Andrews <[email-masked]>
> > wrote:
> >
> > > 	You are incorrect.  All the current schemes have a hash of less than
> > > 	64 octets.  There will ALWAYS be a possibility of collision even
> > > 	after trying every salt as it is impossible to make the hash space
> > > 	larger than the pre-hash space.
> >
> > But the pre-hash space is sparse, and we only care about collisions of
> > ACTUAL values in the pre-hash space, not potential values. IE (assuming all
> > octet values are OK and 64 byte labels for the sake of argument) there are
> > the pre-hash space is size 256^64 and the hash space is smaller (let's say
> > we represent them as alphanumerics so 36^64) - which is presumably your
> > complaint. Note 256^64 is approximately 10^153, and there are about 10^79
> > atoms in the universe, so I predict in applications the pre-hash space will
> > be sparse as even if we could represent one RR in just one atom, we are way
> > off filling the zone :-) So this doesn't matter provided there is a
> > limitation on the number of RR's in a zone - the limitation doesn't have to
> > be impactful - If it was 10^76 (number of atoms in the universe over 1000),
> > we'd still have 10^79 possible salt values to work through, i.e. about 263
> > bits of salt. And as I pointed out earlier, as 76*2<153, the expected
> > number of iterations to find a salt that works is less than 2.
> >
> > I do not think limiting a zone file to 10^79 RRs is going to have
> > a significant deployment impact.
> >
> > Alex
>
> 	You can't write a draft assuming that there won't be collisions.
> 	There will ALWAYS be the possibility of collisions (salts only
> 	reduce the probability) and you have to take those into account.

At hash generation time, in case of collision with an existing name, alter
salt.

At name inclusion time, in case of collision with an existing hash, alter
salt.

At serving time, in case of collision, be famous:

Oh, if anyone can give an example of an actual collision of two different
inputs for say SHA-1 (full rounds please), please speak up.

> 	You have to describe what to do when you have a collision.  Don't
> 	say they won't occur because they will.

In case of an actual collision at serve time (birthday paradox does not
apply here, all pre-images were chosen for you), you treat this as a false
positive. A false positive implies that a non-existent name and type is
now proven to exist. I can't even imagine how one can abuse that fact.

Oh, if anyone can give an example of an actual abuse of false positives,
please speak up.

> 	For RRSIG the impact of collisions is that there are two (or more)
> 	RRsets that you cryptographically prove they are different.
>
> 	For name hashes you end up with different names with possible
> 	different sets of types that you some how have to merge.  If the
> 	sets are identical I don't think there is a issue but it would need
> 	to be discussed.
>
> 	You will also have occasional false matches (names that you
> 	can't prove that don't exist).  There MUST be names for which
> 	this will occur.

If _ever_ such a name can be uncovered, register it with some type.

Roy

--
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: Edward Lewis <[email-masked]>
Date: Wed, 15 Sep 2004 09:31:42 -0400

>	sets are identical I don't think there is a issue but it would need

Why not just include both records as an RRset?

I think this is why I'm thinking we should have split the problem 
into solving "name error" proofs and "no data" proofs.
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                            +1-703-227-9854
ARIN Research Engineer

"I can't go to Miami.  I'm expecting calls from telemarketers." -
Grandpa Simpson.

---

From: Mark Andrews <[email-masked]>
Date: Wed, 15 Sep 2004 23:44:53 +1000

> now proven to exist. I can't even imagine how one can abuse that fact.

	The problem is that you cannot supply a secure answer to the
	question asked.  For every hash there is a enormous set of
	qnames which all has to the same value.
 
--
Mark Andrews, ISC
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742                 INTERNET: [email-masked]

---

From: Alex Bligh <[email-masked]>
Date: Wed, 15 Sep 2004 15:28:32 +0100

> 	say they won't occur because they will.

Well we seem to be disagreeing on a point of mathematics not protocol
here. I am saying that it is always going to be possible, in time
no worse than O(n) (correct case for "O") where n is the zone size,
to find a salt such that there are no hash collisions, provided that
the size of the zone is less than the square root of the size of the
hash space.

I agree a collision MAY occur, and my description for dealing with it
is to chose subsequent salts using a cyclic function of order at least
the hash length, until a collision doesn't occur. Such a cyclic function
might be "add one modulo max hash value".

I believe I've demonstrated that this process finds a salt providing
a non-colliding set (incidentally both non-colliding in the sense that
no hashed name collides with a name prior to hashing, an also that
no hashed name collides with any other hashed name), that the expected
number of iterations is less than 2, and that each iteration is o(n),
provided the requirements on maximum zone size are adhered to (as
per another email, they have no practical impact).

The foregoing is maths rather than protocol design (or at least
my attempt at maths), so it should be something objectively verifiable.
It's a fair while since I did this stuff academically, so perhaps
with more recent experience might like to chime in.

In a nutshell, I assert:

Given a set of n integers, p(i), where 0<=p(i)<K, and a hash function
H (satisfying all the normal properties) such that 0<=H(p(i),S)<J, and
K > n^2, and J<=K, it is possible to find a salt value S for the hash
such that:
  there is no (i, j) such that H(p(i),S)=p(j)
  and there is no (i, j) where i!=j such that H(p(i),S)=H(p(j),S)
by the algorithm of selecting a value S at random from the interval
O<=S<J, and, if the condition is not satisfied modifying S according
to a cyclic function of length J (such as adding 1), until the condition
is satisfied. I further assert that assuming hashing the set p(i) is
o(n), then finding a non-colliding S (i.e. an S satisfying the above
conditions) is no worse than O(n).

If that's a fair statement of the problem, we've reduced it to
a mathematical argument, yes? IE if my assertion is right, collisions
are not a problem?

> 	can't prove that don't exist).  There MUST be names for which

There must be such names for a given salt value (though such names
are computationally very hard to find). I am pretty sure one can
prove that there are not such names for ALL salt values. I am sure
one cannot prove that there ARE such names for all salt values.

Alex

---

From: Alex Bligh <[email-masked]>
Date: Wed, 15 Sep 2004 15:31:44 +0100

> At serving time, in case of collision, be famous:

I'm confused Roy - if you do the first two, how can the third ever
occur (even if you COULD find an SHA-1 collision). Or more accurately
you can avoid it by defining collision (in the first two) as either
H(i)=j OR H(i)=H(j) (i.e. regenerate the hash if you find two labels
hash to the same value - so you become potentially famous at hash
generation or name inclusion time, not at serving time)

Alex

---

From: Roy Arends <[email-masked]>
Date: Wed, 15 Sep 2004 16:40:03 +0200 (CEST)

On Wed, 15 Sep 2004, Alex Bligh wrote:

> occur (even if you COULD find an SHA-1 collision).
>
> Or more accurately

At generation/inclusion/serving time, it is virtually impossible to assert
the content of a future query. A hash over this future -yet-unknown- query
may collide with a hash over an existing name. You'll be famous at serving
time.

Roy

---

From: Ben Laurie <[email-masked]>
Date: Wed, 15 Sep 2004 16:40:01 +0100

> generation or name inclusion time, not at serving time)

The collision would be between the name requested and one of the 
existing names in the zone. And the reason you'd be famous is you'd have 
broken second preimage resistance for SHA-1.

Cheers,

Ben.

-- 
ApacheCon! 13-17 November! http://www.apachecon.com/

http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

---

From: Robert Elz <[email-masked]>
Date: Thu, 16 Sep 2004 04:53:11 +0700

Date:        Wed, 15 Sep 2004 16:40:01 +0100
    From:        Ben Laurie <[email-masked]>
    Message-ID:  <[email-masked]>

  | The collision would be between the name requested and one of the 
  | existing names in the zone. And the reason you'd be famous is you'd have 
  | broken second preimage resistance for SHA-1.

No, that's not true.

Or at least, it would be, but only if you're deliberately setting out
to find a name that hashes to a particular value - that's what's hard.

Merely getting an accidental collision with some unexpected name isn't
enough to make anyone famous.

Yet, the algorithms absolutely have to work when such things happen
(and they will happen - if rarely) - and not only the algorithms, but
the implementations as well.   Getting these "you'll never see it in
your or anyone else's lifetime" things wrong is the cause of the most
frustrating things to diagnose in any system, as the errors happen so
rarely - but they do happen.

kre

ps: all this noiose to attempt to achieve a totally worthless objective!

---

From: Roy Badami <[email-masked]>
Date: Wed, 15 Sep 2004 23:32:13 +0100

>>>>> "Robert" == Robert Elz <[email-masked]> writes:

    Robert> Or at least, it would be, but only if you're deliberately
    Robert> setting out to find a name that hashes to a particular
    Robert> value - that's what's hard.

That's one of the things that's hard.  In crypto circles it's called
preimage resistance, and it's true that it's the weakest of the three
properties that a cryptographic hash function is expected to satisfy
(ie breaking it is the hardest).

The strongest of the three properties is collision resistance, and it
means that it's computationally infeasable to find two names that hash
to the same value.

It's bad cryptographic design to rely on stronger properties of an
underlying algorithm than you need to; but if the collision resistance
of SHA-1 was broken, that would be headline news...

	   -roy