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. <a href="http://code.google.com/p/es-lab/source/browse/trunk/src/ses/StringMap.js">http://code.google.com/p/es-lab/source/browse/trunk/src/ses/StringMap.js</a> solves this problem by simply using "$" as a suffix on a fresh object that inherits from nothing. <br>
<br><div class="gmail_quote">On Fri, Jan 6, 2012 at 1:40 AM, Erik Corry <span dir="ltr"><<a href="mailto:erik.corry@gmail.com">erik.corry@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
For hash maps with string keys, people can concatenate the string keys<br>
with a random prefix.  This fixes this attack, and also prevents the<br>
attacker from using annoying keys like __proto__, hasOwnProperty or<br>
toString.  It doesn't fix things for JSON though, if you are reading<br>
untrusted (in the DOS sense) JSON.<br>
<br>
While V8 is fixing this DOS attack, I am not entirely happy about that<br>
because it sends a signal that it is a good idea to use non-prefixed<br>
property strings on objects as hash maps.  The issues around that are<br>
often much worse than a CPU eating DOS that only really hurts when you<br>
have more than 10k keys.  See for example<br>
<a href="https://groups.google.com/a/googleproductforums.com/forum/#!category-topic/docs/documents/0hQWeOvCcHU" target="_blank">https://groups.google.com/a/googleproductforums.com/forum/#!category-topic/docs/documents/0hQWeOvCcHU</a><br>

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