On Thursday, March 20, 2014 11:56:46 AM UTC-5, Michał Marczyk wrote: > > We're vulnerable to this problem anyway as long as hashing is > deterministic, which is why I think it would be cool to use some > universal-hashing-like scheme... >
Agreed - whether it's the old algorithm or new, it's still a deterministic function from input to hash and an attacker could create inputs that generate the same hash regardless. > I think Murmur3 actually uses a seed that could be randomized? Not > really "safe" in the cryptographic sense of the word, but would make > this sort of attack more challenging. > It does and we currently set that seed to 0. It would be completely feasible to randomize that seed on a per-VM basis thus hashing differently on different JVM instances. Java 7 includes an implementation of this (after u7) for Strings. In Java 8, interestingly they removed all of that and just fixed the hash collection implementation to use balanced trees for collisions instead of lists. Seems like something similar could potentially be done in the HashCollisionNode impl in PHM. > > The way to avoid the problem completely is to use BST-based > dictionaries -- slower, but free from pathological edge cases. > > Murmuring a short initial fragment could still be cool, just because > we'd probably get a better hash. That's an interesting conjecture, but I wouldn't judge it until I saw data on the hash quality and performance impact. I do not expect that any of these changes would be in 1.6.0 - a workaround for any of these problems would be to create a deftype that wrapped a String, implemented IHashEq, and hashed with a VM-specific seed. > > Cheers, > Michał > > > On 20 March 2014 17:40, Tim McCormack > <group-...@brainonfire.net<javascript:>> > wrote: > > On Wednesday, March 19, 2014 4:14:38 PM UTC-4, Alex Miller wrote: > >> Rich just pushed a change to the String hashing to address this. We're > >> going to grab the string hashcode (which is cached after first call) > and > >> murmur the result of that. This gives us constant time hashcode after > first > >> call with better distribution for combinations in nested collections. > Will > >> be in presumed RC2. > > > > (Discussion continued from IRC and Github.) > > > > This does make PHM vulnerable to "hashDoS" attacks again -- ["AaAa" > "BBBB" > > "AaBB" "BBAa"] will all hash to the same value, so an attacker can pass > a > > ton of these colliding strings to a webapp as a querystring or POST body > and > > really bog down the machine. Best article I could find on this attack: > > > http://cryptanalysis.eu/blog/2011/12/28/effective-dos-attacks-against-web-application-plattforms-hashdos/ > > > > > Is there some compromise we can make between caching and good hashing? > > > > My naïve thought would be to combine the native String hashCode with a > > Murmur hash of a fixed chunk of the string, then possibly run that > > combination through Murmur. This avoids hashing unbounded data more than > > once, and would be effective against basic hashDoS. (Intelligently > picking > > the fixed chunk of the string would be essential for protecting against > an > > adaptive hashDoS attack.) > > > > - Tim McCormack > > > > -- > > You received this message because you are subscribed to the Google > > Groups "Clojure" group. > > To post to this group, send email to clo...@googlegroups.com<javascript:> > > Note that posts from new members are moderated - please be patient with > your > > first post. > > To unsubscribe from this group, send email to > > clojure+u...@googlegroups.com <javascript:> > > For more options, visit this group at > > http://groups.google.com/group/clojure?hl=en > > --- > > You received this message because you are subscribed to the Google > Groups > > "Clojure" group. > > To unsubscribe from this group and stop receiving emails from it, send > an > > email to clojure+u...@googlegroups.com <javascript:>. > > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en --- You received this message because you are subscribed to the Google Groups "Clojure" group. To unsubscribe from this group and stop receiving emails from it, send an email to clojure+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.