Re: [Chicken-hackers] On Hash Collisions (28C3)

[Jörg F . Wittenberger]

On Jan 1 2012, Peter Bex wrote:

> On Sun, Jan 01, 2012 at 10:29:18AM -0500, John Cowan wrote:
> > Peter Bex scripsit:
> >
> > > Yes, and doing it in *every* *freaking* program.  Including
> > > third-party libraries written long ago or by people assuming a sane
> > > srfi-69 implementation (or more likely, not having thought about it).
> >
> > Not at all.  Only fixing programs that are exposed to potentially
> > malicious data, like HTTP request parameters.

Me, too, believes that the hash table implementation should be fixed
instead of waiting for some application being hit and fix only that
one later.

How would one define "potential malicious data"?  I'd say: any input.

If the cost was too high, why not have an option to switch back
to vulnerable code.

> > > There is almost no cost; just one call to get a random number when
> > > creating the hash table and one extra xor when hashing a value.
> >
> > Well, that would certainly be reassuring, except for this:
> >
> > 1) If the number is only pseudo-random a la SRFI 27, you have only
> > increased the resistance but not eliminated the problem.  The algorithm
> > is still published and predictable, just more complex.
>
> Increased resistance is better than none at all.

As far as I read the paper, the exploit was rather narrow.  As soon
as one breaks the symmetry in the hash function pretty much gone,
isn't it?

> > 2) If the number is truly random (from /dev/random or what not) it is
> > definitely not cheap.  A program that allocates lots of hash tables will
> > find itself running very slow indeed.
>
> That's why the randomization factor is exposed as a keyword argument.
> If a given program turns out to be too slow, the author can decide what
> security/performance tradeoff is best for that particular program.

Thanks Peter for the quick patch.

I'll try next.

/Jörg