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

[Peter Bex]

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.

New attack vectors are discovered all the time.  It's hard to predict in
advance how someone is going to be able to abuse any given program.
Again, it's better to fix it at the root (the library) than in each
application.

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

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

Cheers,
Peter
-- 
http://sjamaan.ath.cx
--
"The process of preparing programs for a digital computer
 is especially attractive, not only because it can be economically
 and scientifically rewarding, but also because it can be an aesthetic
 experience much like composing poetry or music."
                                                        -- Donald Knuth