News for hackers. Stuff that matters.
Re:Hardening Perl's Hash Function by tiagobraw on Monday November 18, 2013 @02:20PM (#6756257)
Thats why I like Lua's hash implementation that adds a random seed to the hashing algorithm to limit those pathological side effects...
Re:Hardening Perl's Hash Function by joosters on Monday November 18, 2013 @04:17PM (#6757099)
The article discusses why this alone may not be enough. (n.b. I've no experience of Lua's internals, so I can't say whether or not Lua is/isn't vulnerable)

Basically, if the attacker can view enough of an 'ordered' list of hashtable entries, they can calculate the seed and then generate appropriate keys to hit the worst case.

Re:Hardening Perl's Hash Function by Pxtl on Monday November 18, 2013 @05:09PM (#6757502)
Wait, does that mean that iterating across the members of a Lua table is not in deterministic order? I assume it just uses the naive hash ordering for iterators... this is relevant because Lua is used as a scripting-engine SpringRTS which uses a lock-step-based multiplayer approach so anything non-deterministic risks breaking sync.
Re:Hardening Perl's Hash Function by finnw on Monday November 18, 2013 @05:18PM (#6757560)
> 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.

Re:Hardening Perl's Hash Function by Pxtl on Monday November 18, 2013 @05:25PM (#6757610)
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.
Re:Hardening Perl's Hash Function by avar on Monday November 18, 2013 @06:49PM (#6758173)
Just using "sort(hash-keys())" instead of "hash-keys()" should be a trivial patch that fixes this.
Re:Hardening Perl's Hash Function by pjscott on Monday November 18, 2013 @07:18PM (#6758308)
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/