Hardening Perl's Hash Function • Hacker News Board

Re: Hardening Perl's Hash Function

#11

Post by andreasvc » Mon, Nov 18, 2013, 10:26 PM UTC

ggchappell wrote: post #3

TheLoneWolfling wrote: post #2

> An attacker could precalculate one or more suffixes such that H(x) == H( concat(x, suffix) ) which would then allow an attacker to trivially construct an infinite set of keys which would always collide into the same bucket. We hardened the hash by mixing in the length of the key into the seed. This prevents making an infinite set of keys that collide, yes, but does not fix the problem completely. It only increases…

> But if I was looking for guarantees for worst-case performance, I'd (pretty much) never use a HashMap. I wonder why none[1] of the major dynamic languages offer the option of running with the built-in associative-data structures implemented using a Red-Black Tree. Seems like an obvious thing to do. There are interface issues, of course. In particular, for a new type to be usable as a key, it would need to provide a…

I reckon because pointer-based trees are very slow compared to array-based data structures; these are constant factors due to memory accesses so they have nothing to do with the average and worst case performance you mention. For databases b-trees are appropriate, but for most uses of associative data structures hash tables are just very hard to beat.

Re: Hardening Perl's Hash Function

#12

Post by avar » Mon, Nov 18, 2013, 11:49 PM UTC

Pxtl wrote: post #10

finnw wrote: post #9

Earlier quoted context omitted.

> Wait, does that mean that iterating across the members of a Lua table is not in deterministic order? Yes. And it is documented as such. Any dependency on repeatable iteration order is a bug.

Huh. I'm not involved directly in SpringRTS, but I'm going to take a look at the code... I assume there's a compilation flag for Lua to disable that, or they've hacked it up and are using a custom interpreter, because protecting sync is paramount.

Just using "sort(hash-keys())" instead of "hash-keys()" should be a trivial patch that fixes this.

Re: Hardening Perl's Hash Function

#13

Post by pjscott » Tue, Nov 19, 2013, 12:18 AM UTC

tiagobraw wrote: post #5

Thats why I like Lua's hash implementation that adds a random seed to the hashing algorithm to limit those pathological side effects...

That's often insufficient. For MurmurHash{2,3}, for example, you can generate arbitrarily many keys that collide regardless of the random seed. Code is on the SipHash page:

https://131002.net/siphash/

Re: Hardening Perl's Hash Function

#14

Post by ggchappell » Tue, Nov 19, 2013, 3:09 AM UTC

_delirium wrote: post #6

ggchappell wrote: post #3

Earlier quoted context omitted.

> But if I was looking for guarantees for worst-case performance, I'd (pretty much) never use a HashMap. I wonder why none[1] of the major dynamic languages offer the option of running with the built-in associative-data structures implemented using a Red-Black Tree. Seems like an obvious thing to do. There are interface issues, of course. In particular, for a new type to be usable as a key, it would need to provide a…

> I wonder why none[1] of the major dynamic languages offer the option of running with the built-in associative-data structures implemented using a Red-Black Tree. Seems like an obvious thing to do. It's not a command-line option, but Perl lets you "tie" a hash to a different backing implementation, and there are some tree-based ones: use Tree::RB; tie my %hash, 'Tree::RB';

Wow, I had no idea. That's a nice feature.