For hash maps with string keys, people can concatenate the string keys with a random prefix. This fixes this attack, and also prevents the attacker from using annoying keys like __proto__, hasOwnProperty or toString. It doesn't fix things for JSON though, if you are reading untrusted (in the DOS sense) JSON.
While V8 is fixing this DOS attack, I am not entirely happy about that because it sends a signal that it is a good idea to use non-prefixed property strings on objects as hash maps. The issues around that are often much worse than a CPU eating DOS that only really hurts when you have more than 10k keys. See for example https://groups.google.com/a/googleproductforums.com/forum/#!category-topic/docs/documents/0hQWeOvCcHU 2012/1/6 Mark S. Miller <[email protected]>: > There is currently an informal (partial?) consensus to try to add high > entropy identity hashes to ES6 (but no proposal page yet), so that users can > build hashtables for themselves. Were they to do so, they immediately find > they'd want to include non-objects as keys as well (like Map does), and so > we might be tempted to expose a stable data hashing function to support such > uses. The following surprised me, even though it was apparently well known > (not by me ;)) since 2003. > > from <https://groups.google.com/forum/#!topic/friam/jKRZrb5bQEA>: > > Forwarded conversation > Subject: [friam] Fwd: Hash Collision Denial of Service > ------------------------ > > From: Bill Frantz <[email protected]> > Date: Thu, Jan 5, 2012 at 11:51 AM > To: Design <[email protected]> > > > From: @RISK: The Consensus Security Vulnerability Alert Week 1 2012 > > ====== Forwarded Message ====== > Date: 1/5/12 19:37 > From: [email protected] (The SANS Institute) > > 12.2.5 CVE: Not Available > Platform: Cross Platform > Title: Java Hash Collision Denial of Service > Description: Java is a programming language. The application is > exposed to a denial of service issue due to an > error during hashing form posts and updating a hash table. Specially > crafted forms in HTTP POST requests can trigger hash collisions > resulting in high CPU consumption. Java 7 and prior are affected. > Ref: http://www.ocert.org/advisories/ocert-2011-003.html > http://www.securityfocus.com/bid/51236/references > ______________________________________________________________________ > > 12.2.6 CVE: Not Available > Platform: Cross Platform > Title: Python Hash Collision Denial of Service > Description: Python is a programming language available for multiple > platforms. The application is exposed to a denial of service issue > due to an error during hashing form posts and updating a hash table. > Specially crafted forms in HTTP POST requests > can trigger hash collisions resulting in high CPU consumption. > All versions of Python are affected. > Ref: http://www.securityfocus.com/bid/51239/references > ______________________________________________________________________ > ====== End Forwarded Message ====== > > It seems to me, short of using secure hashes, any use of hashtables is > subject to this attack if the attacker can control the data being hashed. > > Cheers - Bill > > --------------------------------------------------------------------------- > Bill Frantz |"We used to quip that "password" is the most common > 408-356-8506 | password. Now it's 'password1.' Who said users haven't > www.periwinkle.com | learned anything about security?" -- Bruce Schneier > > -- > You received this message because you are subscribed to the Google Groups > "friam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/friam?hl=en. > > > ---------- > From: Brian Warner <[email protected]> > Date: Thu, Jan 5, 2012 at 12:09 PM > To: [email protected] > > > Given the limited number of output buckets, I don't think a secure hash > would win you much (i.e. there are no secure 10-bit hashes). Instead, I > think you want to mix things up a bit, by including a per-runtime random > secret in the hash calculation (generated each time the program starts, > maybe for each dictionary you allocate). And then hope that you don't > expose enough information to the attacker (perhaps by enumerating > dictionaries in "implementation-defined" order without sorting the keys) > to let them deduce the secret, and thus be able to force a lot of > collisions. > > I was re-reading djb/agl's articles on "crit-bit trees" (aka PATRICIA > trees, or tries, for those in the router world), and making the argument > that programming languages should use a crit-bit tree as their > fundamental data structure rather than a hash-table -based dictionary > (because you get some additional operations for cheap, like sorted > enumeration). I'm not sure if this would be any less vulnerable to > attack.. seems like a series of [1,11,111,1111,11111,..] keys would > cause similar problems. > > http://cr.yp.to/critbit.html > https://github.com/agl/critbit > > > cheers, > -Brian > > ---------- > From: David-Sarah Hopwood <[email protected]> > Date: Thu, Jan 5, 2012 at 2:03 PM > To: [email protected] > > > Huh. This is a class of attacks that I remember getting a lot of attention > in around 2003 [CW2003]. There were mitigations proposed then that sounded > reasonable (using universal hashing was one). Oh, but Java specifies a > stable > hash, so it's not fixable that way. That presumably explains why it's not > fixed. > > [CW2003] Scott A. Crosby, Dan S. Wallach, > "Denial of Service via Algorithmic Complexity Attacks," > Usenix Security Conference, 2003. > <https://db.usenix.org/event/sec03/tech/full_papers/crosby/crosby_html/> > <https://db.usenix.org/event/sec03/tech/full_papers/crosby/crosby.pdf> > > -- > David-Sarah Hopwood ⚥ http://davidsarah.livejournal.com > > > > > > -- > Cheers, > --MarkM > > _______________________________________________ > es-discuss mailing list > [email protected] > https://mail.mozilla.org/listinfo/es-discuss > _______________________________________________ es-discuss mailing list [email protected] https://mail.mozilla.org/listinfo/es-discuss
