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* <[email protected]> Date: Thu, Jan 5, 2012 at 11:51 AM To: Design <[email protected]> From: @RISK: The Consensus Security Vulnerability Alert Week 1 2012 ====== Forwarded Message ====== Date: 1/5/12 19:37 From: ConsensusSecurityVulnerability**[email protected]<[email protected]>(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 [email protected]. To unsubscribe from this group, send email to friam+unsubscribe@** googlegroups.com <friam%[email protected]>. 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* <[email protected]> Date: Thu, Jan 5, 2012 at 12:09 PM To: [email protected] 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* <[email protected]> Date: Thu, Jan 5, 2012 at 2:03 PM To: [email protected] 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
signature.asc
Description: PGP signature
_______________________________________________ es-discuss mailing list [email protected] https://mail.mozilla.org/listinfo/es-discuss
