4 ms·

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

• joosters 13y ago
  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.
• Pxtl 13y ago
  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.
  • finnw 13y ago
    > 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.
    • Pxtl 13y ago
      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.
      • avar 13y ago
        Just using "sort(hash-keys())" instead of "hash-keys()" should be a trivial patch that fixes this.
• pjscott 13y ago
  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/ https://131002.net/siphash/