Regarding Michal's comment of using BST (binary search tree)-based dictionaries, Clojure does already have sorted-maps and sorted-sets that do this, for comparable keys/elements.
A nice hybrid of the nearly-O(1) typical case of hash maps/sets, and simultaneously protecting against the cases where there are many hash collisions, is to have the 'leaves' of the current hash maps/sets be binary search trees, rather than linked lists. That requires the keys/element to be comparable, but today's clojure.core/compare cannot compare all pairs of things, and perhaps there is no practical way to try to include "everything" in a more general compare function so that everything hashable (i.e. every Java object) is also comparable. Would it be easier to create a 'universal compare' function for all Clojure values, assuming they only contained Clojure values inside of them? Andy On Thu, Mar 20, 2014 at 9:56 AM, Michał Marczyk <michal.marc...@gmail.com>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... > > 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. > -- 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.
