Re: [Chicken-hackers] SRFI-69 compatibility problem and hash table segfaults

[Peter Bex]

On Sun, Jan 08, 2012 at 04:13:49PM +0100, Jörg F. Wittenberger wrote:
> On Jan 7 2012, Peter Bex wrote:
> 
> >The thought just popped into my head that my hash table patch breaks
> >SRFI-69 compatibility.  When the user passes a custom hash procedure,
> 
> That would be bad bad.  In the end.

Yes.

> >2) Get rid of randomization-per-hashtable and have one global
> >   randomization value instead, like low-level hash tables.
> >   Symbol tables could still have per-table randomization.
> >   Users must take care of randomization themselves.
> 
> Haven't had time to read things up.  A question: is randomization
> the only option to fix the issue?  To my understanding (read
> guesswork) additional randomisation would fix any vulnerable
> hash function.  But aren't there any good hash functions to begin
> with?

The problem is actually that the hash function must map any given
string to a restricted set of integers.  If you have a hash table
with 10 buckets, and you have 100 strings, you're always going
to end up with collisions.

> If we could have non-vulnerable hash functions for the defaults
> and those hash-* functions as exported, then I'd feel much easier
> with the next topic

Our initial hash function was extremely weak and very vulnerable
because any string with a matching 8-character suffix would result
in the same hash value, which makes it very easy to exploit.

I've replaced this function by a better one.  Like in the paper/talk
at CCC, they could either predict the hash function's output (bad)
or perform a meet-in-the-middle attack.  The latter is the best
you can get.  Randomizing it means that the meet-in-the-middle attack
won't work because if something happens to hash to the same value with
your random value means it won't hash to that value with my random value.

> >3 means that in some cases the
> >user might want to use the chicken-supplied ones but needs to
> >remember to use the randomization factor.  3 is of course the easiest
> >since it basically just punts on the issue and lets the user sort it
> >out (but only when passing a custom procedure!).
> 
> I'd assume that whoever passes a custom procedure either re-uses
> the default hash-* functions on some value selector or really, really
> knows what to do.  For the latter a footnote in the manual to remind
> them on the issue would do even better then a well meant solution
> which doesn't fit their needs perfectly.

Maybe you can provide a patch for the manual?

> >make use of the hash table's randomization value, this becomes
> >difficult because then when you use hash-table-copy the first hash
> >table stays around in the closure and never gets GCed.
> 
> Such a memory leak will soon show up and spoil the fun.

Yes, that's why I decided to fix it the way I did.

> Sorry for the late reply.

That's okay.

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