3 ms·

As long as your usecase isn't worried about hash-flooding [0]. Unfortunately too few people know this is even an attack, so it may be reasonable for languages t

by Gankro 11y ago

As long as your usecase isn't worried about hash-flooding [0]. Unfortunately too few people know this is even an attack, so it may be reasonable for languages to default to a stronger hash algorithm for safety, but this isn't the common case... language design is hard. [0]: https://www.youtube.com/watch?v=wGYj8fhhUVA https://www.youtube.com/watch?v=wGYj8fhhUVA

jbapple 11y ago
Fortunately, there are very fast universal hash functions like Vhash that are resistant to hash-flooding.
- Gankro 11y ago
  I've literally never heard of Vhash, and I see no references to it outside of the 2007 paper. As far as I know, the state of the art for "fast and secure" is still SipHash 2-4 or 2-3. While SipHash perf is generally quite good, it's still not as fast as Fnv on small inputs or XxHash on large inputs. As in, 4x slower [0]. FarmHash has great perf if you can invoke it in the way it wants, but doesn't do well in a streaming context. [0]: http://cglab.ca/~abeinges/blah/hash-rs/ http://cglab.ca/~abeinges/blah/hash-rs/
  - jbapple 11y ago
    > I've literally never heard of Vhash, and I see no references to it outside of the 2007 paper. It is intimately tied up with VMAC. The title of the 2006 paper that introduced them is "Message authentication on 64-bit architectures". Google scholar says it has been cited 32 times, while "SipHash: a fast short-input PRF" has been cited 43 times. > As far as I know, the state of the art for "fast and secure" is still SipHash 2-4 or 2-3. SipHash seems to me like a good choice. SipHash has some security properties that Vhash does not, although Vhash-based-VMAC has similar security properties to SipHash, I believe. However, for hash flooding attacks, if the hash values themselves are not directly exposed to the attackers and there is enough noise in the response latency that timing attacks are difficult, I do not know what benefits SipHash has. "Faster 64-bit universal hashing using carry-less multiplications" has some benchmarks that show Vhash as faster than SipHash, substantially so on long input. Speed-wise, an iterated string hash using Dietzfelbinger-style multiply-shift hashing is also substantially faster (3-10x) than SipHash on both large and small inputs in my testing, and it needs about 20 lines of code to implement. I haven't written any Rust in a while, but I'll try and send you a patch to the repo you linked. The benchmarks from the "Faster 64-bit ..." paper are available at https://github.com/lemire/StronglyUniversalStringHashing https://github.com/lemire/StronglyUniversalStringHashing. The iterated string hash I referenced is https://github.com/lemire/StronglyUniversalStringHashing/blob/3215c53a34699c8b573a4a6e57e7df248c0a82fc/include/bigendianuniversal.h#L43 https://github.com/lemire/StronglyUniversalStringHashing/blo....
    - Gankro 11y ago
      Awesome, cool! The repo's a bit of a commented-out mess (I was trying to get a bunch of broken impls working before I had to get back to real work), so let me know if you have any trouble. Always happy to help people learn the language. :) I'm Gankro on github and the #rust IRC channel.
KMag 11y ago
There isn't much complexity and performance cost of optimistically using a faster hash, and dynamically falling back to siphash (or another secure keyed hash function). Using associative arrays implemented via chaining, one could have a bit in the associative array header that indicates if the associative array uses the fast keyed hash or siphash (or another secure hash). When inserting an item, if one finds that the chain length exceeds a certain limit without the load exceeding the resize threshold (indicating poor hash distribution), one could rehash all of the keys using siphash. An associative array using open addressing could do something similar, switching hash functions if the probe sequence got too long (analogous to a chain being too long). Alternatively, if using open addressing, one could use something like cuckoo hashing. A very fast keyed hash could be computed, and upon a collision, siphash could be used, with a probe sequence similar to used by Python dicts. Though, if your use case has lots of missed lookups, then performance will be better just using siphash. Of course, one could use counters to detect this condition, set a bit in the associative array header to indicate all future lookups should just use siphash, and rehash all of the existing keys.
- Gankro 11y ago
  Rust's solution is to provide the hash function as a generic parameter so you can just Fnv/Xx/Sip based on your workload, with Sip as the default if you don't pick. Unfortunately this is mostly incompatible with the adaptive scheme you suggest, because you definitely don't want the adaptive logic if you've already picked Xx/Fnv. Making it possible to disable all that if you pick something other than Sip would make things quite complicated. But yeah, data structuring is ultimately really work-load specific. Any solution a language provides will always be suboptimal for tons of use cases. The solution you describe sounds good for a "never think about it" solution that works for 85% of cases. Rust's solution kinda necessitates more thinking more often, but I think it makes it more applicable for more usecases if you're willing to do that little bit of thinking.

by Gankro 11y ago

jbapple 11y ago

Fortunately, there are very fast universal hash functions like Vhash that are resistant to hash-flooding.

Gankro 11y ago
I've literally never heard of Vhash, and I see no references to it outside of the 2007 paper. As far as I know, the state of the art for "fast and secure" is still SipHash 2-4 or 2-3. While SipHash perf is generally quite good, it's still not as fast as Fnv on small inputs or XxHash on large inputs. As in, 4x slower [0]. FarmHash has great perf if you can invoke it in the way it wants, but doesn't do well in a streaming context. [0]: http://cglab.ca/~abeinges/blah/hash-rs/ http://cglab.ca/~abeinges/blah/hash-rs/
- jbapple 11y ago
  > I've literally never heard of Vhash, and I see no references to it outside of the 2007 paper. It is intimately tied up with VMAC. The title of the 2006 paper that introduced them is "Message authentication on 64-bit architectures". Google scholar says it has been cited 32 times, while "SipHash: a fast short-input PRF" has been cited 43 times. > As far as I know, the state of the art for "fast and secure" is still SipHash 2-4 or 2-3. SipHash seems to me like a good choice. SipHash has some security properties that Vhash does not, although Vhash-based-VMAC has similar security properties to SipHash, I believe. However, for hash flooding attacks, if the hash values themselves are not directly exposed to the attackers and there is enough noise in the response latency that timing attacks are difficult, I do not know what benefits SipHash has. "Faster 64-bit universal hashing using carry-less multiplications" has some benchmarks that show Vhash as faster than SipHash, substantially so on long input. Speed-wise, an iterated string hash using Dietzfelbinger-style multiply-shift hashing is also substantially faster (3-10x) than SipHash on both large and small inputs in my testing, and it needs about 20 lines of code to implement. I haven't written any Rust in a while, but I'll try and send you a patch to the repo you linked. The benchmarks from the "Faster 64-bit ..." paper are available at https://github.com/lemire/StronglyUniversalStringHashing https://github.com/lemire/StronglyUniversalStringHashing. The iterated string hash I referenced is https://github.com/lemire/StronglyUniversalStringHashing/blob/3215c53a34699c8b573a4a6e57e7df248c0a82fc/include/bigendianuniversal.h#L43 https://github.com/lemire/StronglyUniversalStringHashing/blo....
  - Gankro 11y ago
    Awesome, cool! The repo's a bit of a commented-out mess (I was trying to get a bunch of broken impls working before I had to get back to real work), so let me know if you have any trouble. Always happy to help people learn the language. :) I'm Gankro on github and the #rust IRC channel.

KMag 11y ago

There isn't much complexity and performance cost of optimistically using a faster hash, and dynamically falling back to siphash (or another secure keyed hash function). Using associative arrays implemented via chaining, one could have a bit in the associative array header that indicates if the associative array uses the fast keyed hash or siphash (or another secure hash). When inserting an item, if one finds that the chain length exceeds a certain limit without the load exceeding the resize threshold (indicating poor hash distribution), one could rehash all of the keys using siphash. An associative array using open addressing could do something similar, switching hash functions if the probe sequence got too long (analogous to a chain being too long). Alternatively, if using open addressing, one could use something like cuckoo hashing. A very fast keyed hash could be computed, and upon a collision, siphash could be used, with a probe sequence similar to used by Python dicts. Though, if your use case has lots of missed lookups, then performance will be better just using siphash. Of course, one could use counters to detect this condition, set a bit in the associative array header to indicate all future lookups should just use siphash, and rehash all of the existing keys.

Gankro 11y ago
Rust's solution is to provide the hash function as a generic parameter so you can just Fnv/Xx/Sip based on your workload, with Sip as the default if you don't pick. Unfortunately this is mostly incompatible with the adaptive scheme you suggest, because you definitely don't want the adaptive logic if you've already picked Xx/Fnv. Making it possible to disable all that if you pick something other than Sip would make things quite complicated. But yeah, data structuring is ultimately really work-load specific. Any solution a language provides will always be suboptimal for tons of use cases. The solution you describe sounds good for a "never think about it" solution that works for 85% of cases. Rust's solution kinda necessitates more thinking more often, but I think it makes it more applicable for more usecases if you're willing to do that little bit of thinking.