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...
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. 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. Cheers, Michał On 20 March 2014 17:40, Tim McCormack <group-cloj...@brainonfire.net> 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 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. -- 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.
