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

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

# Mark S. Miller (13 years ago)

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 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: www.ocert.org/**advisories/ocert-2011-003.htmlwww.ocert.org/advisories/ocert-2011-003.html

www.securityfocus.com/**bid/51236/referenceswww.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: www.securityfocus.com/**bid/51239/referenceswww.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

# Erik Corry (13 years ago)

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 groups.google.com/a/googleproductforums.com/forum/#!category-topic/docs/documents/0hQWeOvCcHU

2012/1/6 Mark S. Miller <erights at google.com>:

# Mark S. Miller (13 years ago)

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