2 ms·
Since the hashes uses open addressing wouldn't they be susceptible to hash poisoning attacks? Java plugged that hole in HashMap in Java 8 by reallocating lists
by bjourne 8y ago
Since the hashes uses open addressing wouldn't they be susceptible to hash poisoning attacks? Java plugged that hole in HashMap in Java 8 by reallocating lists over a certain length as balanced trees. But that strategy isn't possible with open addressing. https://www.nagarro.com/en/blog/post/24/performance-improvement-for-hashmap-in-java-8 https://www.nagarro.com/en/blog/post/24/performance-improvem...
- rurban 8y agoThey use a byte for collision counting, and a byte is enough to reliably detect and punish DOS attackers on 32bit tables (max 4G keys). On 64bit tables I didn't do the math yet.
- ngbronson 8y agoF14 supports stateful hashers, so in situations that need to be resilient to hash poisoning we can use a hasher designed for that purpose.
- bjourne 8y agoI recall that that was what was suggested for Java's HashMap too, but they found it to be insufficient. By careful analysis, an attacker could still figure out how to cause hash collisions.
- ngbronson 8y agoI haven't seen those discussions, but is it possible that they were trying to rehash the results of Object.hashCode rather than pass all of the bytes of the original value through a new hash algorithm? If you haven't seen it before you will appreciate https://accidentallyquadratic.tumblr.com/post/153545455987/rust-hash-iteration-reinsertion https://accidentallyquadratic.tumblr.com/post/153545455987/r...
- bjourne 8y agoAfaik, they augmented the hash function with a random seed, which didn't work out. See: http://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/ http://emboss.github.io/blog/2012/12/14/breaking-murmur-hash... It appears that SipHash would be enough (for now) to prevent hash poisoning. Most open addressing hash implementations doesn't yet use SipHash though.