4 ms·

This is what SipHash was made for: it's a cryptographic MAC that's competitive in speed with other hash functions meant for hash table use. The paper describes

• haberman 14y ago
  Interesting, though at 140 cycles to hash 16 bytes, it's much slower than state-of-the-art hash functions, which can hash 16 bytes in just over 16 cycles. If you seed your non-cryptographic hash function with a cryptographically random number, you can get the best of both worlds: fast hashing and collision resistance against an adversary.
  • kibwen 14y ago
    Can you name some of these speedy state-of-the-art hash functions?
    • haberman 14y ago
      MurmurHash3 (http://code.google.com/p/smhasher/wiki/MurmurHash3 http://code.google.com/p/smhasher/wiki/MurmurHash3), CityHash (http://code.google.com/p/cityhash/ http://code.google.com/p/cityhash/), SpookyHash (http://burtleburtle.net/bob/hash/spooky.html http://burtleburtle.net/bob/hash/spooky.html).
      • dchest 14y ago
        But you said 16 cycles. "For example, hashing 16 bytes takes 141 Bulldozer cycles with SipHash-2-4, against 82 and 126 for CityHash and SpookyHash, and 600 for MD5." https://www.131002.net/siphash/siphash.pdf https://www.131002.net/siphash/siphash.pdf (p.12)
        • haberman 14y ago
          According to CityHash's benchmarks (http://code.google.com/p/cityhash/source/browse/trunk/README http://code.google.com/p/cityhash/source/browse/trunk/README), they can hash 8 bytes in 6ns and 64 bytes in 9ns on a 2.67GHz machine (so 16-24 cycles).
  • pbsd 14y ago
    Not really. The SipHash page contains proof-of-concept code that breaks common good non-cryptographic randomized hashes, i.e., it generates collisions regardless of the chosen seed. Regarding performance, SipHash is essentially as fast as Python's randomized hash, and quite faster for long inputs (>16 bytes), cf. http://bench.cr.yp.to/results-auth.html#amd64-sandy http://bench.cr.yp.to/results-auth.html#amd64-sandy .
    • haberman 14y ago
      That code appears to rely on having direct access to the hash function; this seems very unlikely to be leaked to an attacker. More interesting would be code that gets the secret with only access to ordered iteration on the table, which is more likely to leak. I don't know anything about Python's hash function, all of those benchmarks are still an order of magnitude slower than CityHash (for example), which peaks at 0.16 cycles/byte. I would be interested to see SipHash put through SMHasher, which is the most comprehensive hash function test suite I know of: http://code.google.com/p/smhasher/ http://code.google.com/p/smhasher/
      • dchest 14y ago
        Seed recovery (which requires access to hash function) is for Python hash. For CityHash, MurmurHash (2 and 3) there are seed-independent collisions. Of course, it passes SMHasher with 10 score -- it's a cryptographic PRF.
        • haberman 14y ago
          > For CityHash, MurmurHash (2 and 3) there are seed-independent collisions. Are you referring to the "Advanced hash flooding" section of the paper, or am I missing this in another place? That analysis appears to rely on the hash function being highly linear/periodic (ie. you can always add "l" to get back the same hash value). I don't think that City, Spooky, or Murmur are nearly this linear. For example, City is based on CRC32 (ie. polynomial division). Don't get me wrong, I'm impressed that SipHash is so fast for a cryptographic hash. But modern non-cryptographic hash functions are so fast (especially when they're CPU-accelerated, like City is on Intel thanks to the CRC32 instruction) that I don't think SipHash can claim to be the obvious choice for all hash tables. I am interested to know though if the random seed + City/Spooky/Murmur approach really does have practical hash flooding attacks.
  • pjscott 14y ago
    The strategy you propose gives immunity to the more straightforward attacks on hash tables, but in practice tends to leak information about your secret key through differences in the time taken by hash table operations. If you check out pages 14--16 of the SipHash paper, it goes into a bit more detail about this. You may also find Appendix B entertaining.