[friam] Fwd: Hash Collision Denial of Service

Erik Corry erik.corry at gmail.com
Fri Jan 6 01:40:41 PST 2012


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 <erights at 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 <frantz at pwpconsult.com>
> Date: Thu, Jan 5, 2012 at 11:51 AM
> To: Design <friam at googlegroups.com>
>
>
> From: @RISK: The Consensus Security Vulnerability Alert Week 1 2012
>
> ====== Forwarded Message ======
> Date: 1/5/12 19:37
> From: ConsensusSecurityVulnerabilityAlert at 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 friam at googlegroups.com.
> To unsubscribe from this group, send email to
> friam+unsubscribe at googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/friam?hl=en.
>
>
> ----------
> From: Brian Warner <warner at lothar.com>
> Date: Thu, Jan 5, 2012 at 12:09 PM
> To: friam at 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.hopwood at googlemail.com>
> Date: Thu, Jan 5, 2012 at 2:03 PM
> To: friam at 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 at mozilla.org
> https://mail.mozilla.org/listinfo/es-discuss
>


More information about the es-discuss mailing list