[friam] Fwd: Hash Collision Denial of Service

Mark S. Miller erights at google.com
Fri Jan 6 08:13:27 PST 2012


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.corry at 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 <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
> >
>



-- 
    Cheers,
    --MarkM
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20120106/402d02de/attachment.html>


More information about the es-discuss mailing list