Yes, that example is indeed much worse than this dos attack. But the fix does not need random prefixes, and indeed random prefixes are way overkill. http://code.google.com/p/es-lab/source/browse/trunk/src/ses/StringMap.jssolves this problem by simply using "$" as a suffix on a fresh object that inherits from nothing.
On Fri, Jan 6, 2012 at 1:40 AM, Erik Corry <erik.co...@gmail.com> wrote: > 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 <erig...@google.com>: > > 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 <fra...@pwpconsult.com> > > Date: Thu, Jan 5, 2012 at 11:51 AM > > To: Design <fr...@googlegroups.com> > > > > > > From: @RISK: The Consensus Security Vulnerability Alert Week 1 2012 > > > > ====== Forwarded Message ====== > > Date: 1/5/12 19:37 > > From: consensussecurityvulnerabilityal...@sans.org (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 fr...@googlegroups.com. > > To unsubscribe from this group, send email to > > friam+unsubscr...@googlegroups.com. > > For more options, visit this group at > > http://groups.google.com/group/friam?hl=en. > > > > > > ---------- > > From: Brian Warner <war...@lothar.com> > > Date: Thu, Jan 5, 2012 at 12:09 PM > > To: fr...@googlegroups.com > > > > > > 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 <davidsarah.hopw...@googlemail.com> > > Date: Thu, Jan 5, 2012 at 2:03 PM > > To: fr...@googlegroups.com > > > > > > 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 > > es-discuss@mozilla.org > > https://mail.mozilla.org/listinfo/es-discuss > > > -- Cheers, --MarkM
_______________________________________________ es-discuss mailing list es-discuss@mozilla.org https://mail.mozilla.org/listinfo/es-discuss
