Most hash functions and benchmarks are not tuned for small inputs. This is why SipHash is disfavored in Rust these days, because while its performance is excellent on large keys it suffers quite a bit on small ones.
Most hash functions and benchmarks are not tuned for small inputs. This is why SipHash is disfavored in Rust these days, because while its performance is excellent on large keys it suffers quite a bit on small ones.
> The main focus is about short keys of random lengths, with a distribution of length roughly in the 20-30 bytes area, featuring occasional outliers, both tiny and large.
I have been playing around trying to write interpreters and compilers for a hobby, and though I haven't taken stats, but I suspect that in source code, identifiers half that length are more than twice as common.
It make me wonder if compilers are better of using old-school byte-by-byte hashes rather than new ones optmised for parallelism. (Then again, the hash function probably makes no real difference to speed once in a real-world compiler that does optimisation).
> > The main focus is about short keys of random lengths, with a distribution of length roughly in the 20-30 bytes area, featuring occasional outliers, both tiny and large.
Based on the graphs, XXH3 still seems to beat everything at key sizes > 6 (presumably bytes?)
Probably not.
Good hashes optimized for small sizes would probably still use wider loads and operations, perhaps overlapping them: e.g., for a 7 byte hash you might do two 4-byte hashes on the first and second half meaning one byte would get done twice, which isn't a problem. High speed small memory copies follow the same approach.
One problem with byte-at-a-time hashes are that byte operations aren't really any faster than wider operations (at least up to 64-bits), so you'll do 7 byte mixing operations in the example above rather than 2.
The other problem is that wider chunks tend to "quantize" the number of loops in the algorithm, which is very helpful for branch prediction. A byte-at-a-time hash that uses a loop or some kind of jump into inline code will necessarily mispredict unless the exact length is predictable: but if it varies by even 1 byte, the branching is different. Hashes with larger chunks may take the same path for a range of lengths, so may have fewer mispredictions even if the size varies. For example, a hash that uses two possibly overlapping 4-byte reads may handle sizes from 5-8 (or even 4-8) bytes with the same path, so random variation within that range doesn't cause a mispredict.
I think the era of the byte-at-a-time hash is really over, except perhaps if gets some special hardware support.
I wasn't aware of this!
What do people use instead?
(I remember reading that part of the motivation for making SipHash the default Hasher was that its randomness guards against hash flooding attacks. Is that something people care about in practice?)
That's controversial the way climate change is controversial.
His arguments are a little inconsistent and ambiguous, which suggests either a misunderstanding, perhaps a touch of mania, or both. But they're all wrong--whether at face value or when assuming the best possible version--at least regarding the security and the ease of generating collisions.
As for the argument that SipHash is too slow, that's a qualitative judgment that many people have made. But they don't usually need to first convince themselves, erroneously, that SipHash is insecure.
1) If he's arguing that SipHash (or any keyed) hash function is insufficient because one can presume that the key can be acquired, then that would render all encryption schemes insecure. The security of any keyed cipher or hash is always predicated on maintaining the secrecy of the key, period. If you throw that presumption out the door than they're all "broken".
2) If he's arguing that he can generate collisions by timing when an injected key collides, he never shows how that information can be used to reliably generate new collisions. At best he only _alludes_ to this. He says something about having code to do it, but then refuses to provide the code.
If a hash table only has two buckets, it's trivial to create collisions. For a uniformly random hashing function you have a 50% chance. But so what? Unless the hash table is a fixed size, when you try to inject more keys (usually 50%-80% of the hash table size) the table will be resized. This will happen regardless of the collision rate, and indeed you want to avoid predicating resize on actual collision rate because otherwise an attacker can force you to use up all memory. All you need for this is a simple counter for the table. (And of course your hash should evenly distribute keys, as SipHash does.)
If you use a fixed-sized table, then not only will a secure hash not help you, but neither will anything else. If an attacker can reliably generate biased collisions, then he can always cause worse-case performance, including triggering whatever fancy reshuffle logic the hash table uses after a collision, violating the presumption of amortized O(1) work.
Note that the paper cited in the Github thread (Wool 2009) presumes a small key space:
We have demonstrated that a remote algorithmic complexity
attack, against randomized hash tables, is possible if the
secret value is chosen from a small enough space. More
secret bits cause more effort, time and space to be consumed
in the information gathering stage. Thus, it seems that a
random value of 32 bits would render this attack impractical
with today's technology. Note though that in this paper the
attacker iterates over all possible random values in a
brute-force manner, searching for bucket collisions.
However, the search space may be limited to a smaller subset
of random numbers by taking advantage of the vulnerabilities
in the Linux Random Number Generator as suggested in
(Gutterman et al., 2006). This might lead to a feasible
attack against a server with a longer secret value.
SipHash takes a 128-bit key. The Wool attack isn't even remotely feasible. Even if the hash table is small and you're reducing the 64-bit SipHash-generated key to only, say, 10 bits, you still can't recover the key and you can't generate biased collisions. As for targeting Linux's PRNG, that same argument applies to all cryptographic software schemes.EDIT: Previously said the Wool paper relied on fixed-sized hash tables. But it actually relies on a small key space permitting a brute force, oracle attack.