Fwd: [friam] Fwd: Hash Collision Denial of Service

Mark S. Miller erights at google.com
Thu Jan 5 20:37:07 PST 2012


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: ConsensusSecurityVulnerability**Alert at sans.org<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.ocert.org/advisories/ocert-2011-003.html>
http://www.securityfocus.com/**bid/51236/references<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<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@**
googlegroups.com <friam%2Bunsubscribe at googlegroups.com>.
For more options, visit this group at http://groups.google.com/**
group/friam?hl=en <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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20120105/683bcedf/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 553 bytes
Desc: not available
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20120105/683bcedf/attachment-0001.bin>


More information about the es-discuss mailing list