News for hackers. Stuff that matters.
Re:Open-sourcing F14 for memory-efficient hash tables by bjourne on Friday April 26, 2019 @05:38PM (#19761990)
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-improvem...
Re:Open-sourcing F14 for memory-efficient hash tables by ngbronson on Friday April 26, 2019 @06:43PM (#19762393)
F14 supports stateful hashers, so in situations that need to be resilient to hash poisoning we can use a hasher designed for that purpose.
Re:Open-sourcing F14 for memory-efficient hash tables by bjourne on Friday April 26, 2019 @07:08PM (#19762549)
I 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.
Re:Open-sourcing F14 for memory-efficient hash tables by ngbronson on Friday April 26, 2019 @07:23PM (#19762634)
I 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/r...

Re:Open-sourcing F14 for memory-efficient hash tables by bjourne on Friday April 26, 2019 @08:44PM (#19763005)
Afaik, 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... It appears that SipHash would be enough (for now) to prevent hash poisoning. Most open addressing hash implementations doesn't yet use SipHash though.
Re:Open-sourcing F14 for memory-efficient hash tables by rurban on Friday April 26, 2019 @05:44PM (#19762033)
They 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.