3 ms·

I think the claim isn't "SipHash is not a secure keyed hash function (PRF)" but rather "secure keyed hash functions are insufficient mitigation for hash DoS".

I think the claim isn't "SipHash is not a secure keyed hash function (PRF)" but rather "secure keyed hash functions are insufficient mitigation for hash DoS". For long lived hash-tables even per-table keys don't prevent finding bucket-collisions via side-channels. So you either have to either rekey when a large number of bucket-collisions are detected. Or you fall back to a balanced tree based data structure for those buckets. If you prefer the latter mitigation, there is little reason to pay the performance hit of SipHash. So the OP has a point, but is terrible at communicating it.

jchw 8y ago
Well, I am not a cryptographer, so I can't really make much attestations myself, but here's what I read: - OP claims that the security claims of SipHash are incorrect or misleading. - SipHash paper author defends claims made in SipHash paper. - OP responds, claims that the security properties are misleading because most people would just assume it meant it was a "secure hash" and not a secure PRF. To prove this, he alludes to a Rust bug that as far as I can tell would work exactly the same with any hash function. So I'm curious. Can you recover the seed in SipHash with side channel attacks? The response can be summed up as "PoC||GTFO," and I tend to agree; it seems to contradict at least some of the security claims they are making, after all. All in all, if they have a point, it's missed in the flurry of unrelated points that were brought up there, and I definitely am not sure what to take away from it.
GoblinSlayer 8y ago
He means the worst case scenario when the attacker knows the key. In which case it's trivial indeed.
- rurban 8y ago
  As I explained there, getting the hash seed of a running process in a dynamic language is trivial. Every language has enough ropes to hang yourself and print the value from some known offset. And if not, there's still enough information from a typical bad hash table (95% of hash tables are bad) to get at the seed via ordering and timing. From there you just brute force an attack even with an extremely slow hash like siphash. A seed is no secure protection against an determined attacker, only for newbies. A newbie would just DOS the system with simplier means. The point is, don't believe the theatre, use proper protection against the attack (no linear list on collisions), and keep the hash table fast. Collision counting or fallback to tree really is trivial.
  - minitech 8y ago
    > And if not, there's still enough information from a typical bad hash table (95% of hash tables are bad) to get at the seed via ordering and timing. Really? How’s that? The SipHash seed isn’t supposed to be recoverable from hashes – that would be a pretty significant break – and I don’t see what other route the hash table would have to the seed. > Every language has enough ropes to hang yourself and print the value from some known offset. You mean explicitly reading the seed out for an attacker? If we’re modifying the program to help, I figure while (true) {} is probably a simpler DoS.

jchw 8y ago

Well, I am not a cryptographer, so I can't really make much attestations myself, but here's what I read: - OP claims that the security claims of SipHash are incorrect or misleading. - SipHash paper author defends claims made in SipHash paper. - OP responds, claims that the security properties are misleading because most people would just assume it meant it was a "secure hash" and not a secure PRF. To prove this, he alludes to a Rust bug that as far as I can tell would work exactly the same with any hash function. So I'm curious. Can you recover the seed in SipHash with side channel attacks? The response can be summed up as "PoC||GTFO," and I tend to agree; it seems to contradict at least some of the security claims they are making, after all. All in all, if they have a point, it's missed in the flurry of unrelated points that were brought up there, and I definitely am not sure what to take away from it.

GoblinSlayer 8y ago

He means the worst case scenario when the attacker knows the key. In which case it's trivial indeed.

rurban 8y ago
As I explained there, getting the hash seed of a running process in a dynamic language is trivial. Every language has enough ropes to hang yourself and print the value from some known offset. And if not, there's still enough information from a typical bad hash table (95% of hash tables are bad) to get at the seed via ordering and timing. From there you just brute force an attack even with an extremely slow hash like siphash. A seed is no secure protection against an determined attacker, only for newbies. A newbie would just DOS the system with simplier means. The point is, don't believe the theatre, use proper protection against the attack (no linear list on collisions), and keep the hash table fast. Collision counting or fallback to tree really is trivial.
- minitech 8y ago
  > And if not, there's still enough information from a typical bad hash table (95% of hash tables are bad) to get at the seed via ordering and timing. Really? How’s that? The SipHash seed isn’t supposed to be recoverable from hashes – that would be a pretty significant break – and I don’t see what other route the hash table would have to the seed. > Every language has enough ropes to hang yourself and print the value from some known offset. You mean explicitly reading the seed out for an attacker? If we’re modifying the program to help, I figure while (true) {} is probably a simpler DoS.