4 ms·
Moral of the story: Always always consult Knuth.
by carapace 8y ago
Moral of the story: Always always consult Knuth.
- rurban 8y agoUnless Knuth is outdated. With hash tables Knuth is seriously outdated. With hash functions you can consult his test functions, but he is also outdated. E.g. the CRC scheme is the fastest by far (one even exists in HW), but too easily attackable. Trivial really, any 10 year old can do that, due to some unfortunate CRC properties.
- carapace 8y agoStart with Knuth, don't end with him. ;-)
- acqq 8y ago> too easily attackable. Trivial really, any 10 year old can do that In another comment you write: > You can easily brute-force even the worst of all siphash in under 4min. Can you please write what you mean by those statements? Is it about the "hash-flooding DoS" attacks or something else? Can you share a little more of your insights?
- rurban 8y agoSee the relevant smhasher discussions.
- acqq 8y ago"smhasher discussions" where? This is not an answer. Especially regarding "4 min" re siphash, about which kind of attack do you talk about at all, under which conditions? The writings of those who try to protect from flooding attacks are more specific, e.g.: https://github.com/google/highwayhash https://github.com/google/highwayhash "The author of SipHash has published C++ programs to generate" "'universal (key-independent) multicollisions' for CityHash and Murmur. Similar 'differential' attacks are likely possible for any hash function consisting only of reversible operations" "attackers are only looking for multiple m mapping to the same bin rather than identical hash values." "a strong hash function is not, by itself, sufficient to protect a chained hash table from flooding attacks. However, strong hash functions are important parts of two schemes for preventing denial of service. Using weak hash functions can slightly accelerate the best-case and average-case performance of a service, but at the risk of greatly reduced attack costs and worst-case performance." Also, please also be specific about the "regressions" you mention in another post. Your statements, in the form they are, aren't of much use.
- nhaehnle 8y ago> any 10 year old can do that Is this kind of hyperbole really necessary?
- rurban 8y agoYes, because almost nobody knows. But when you see it it's super trivial. Knuth would be ashamed.