This service will be undergoing maintenance at 03:30 UTC, 2016-05-27. It is expected to last about 2 hours
Bug 750575 - (CVE-2011-5037) CVE-2011-5037 v8: hash table collisions CPU usage DoS (oCERT-2011-003)
CVE-2011-5037 v8: hash table collisions CPU usage DoS (oCERT-2011-003)
Status: CLOSED CURRENTRELEASE
Product: Security Response
Classification: Other
Component: vulnerability (Show other bugs)
unspecified
All Linux
medium Severity medium
: ---
: ---
Assigned To: Red Hat Product Security
impact=moderate,public=20111228,repor...
: Security
Depends On:
Blocks: hashdos/oCERT-2011-003 750577
  Show dependency treegraph
 
Reported: 2011-11-01 12:02 EDT by Jan Lieskovsky
Modified: 2015-07-31 02:45 EDT (History)
4 users (show)

See Also:
Fixed In Version:
Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of:
Environment:
Last Closed: 2013-03-15 21:40:20 EDT
Type: ---
Regression: ---
Mount Type: ---
Documentation: ---
CRM:
Verified Versions:
Category: ---
oVirt Team: ---
RHEL 7.3 requirements from Atomic Host:


Attachments (Terms of Use)
v8 hash collision fix (35.77 KB, patch)
2012-01-09 08:21 EST, Tomas Hoger
no flags Details | Diff

  None (edit)
Description Jan Lieskovsky 2011-11-01 12:02:50 EDT
Julian Wälde and Alexander Klink reported that the hash function used in v8 JavaScript implementation to implement arrays using hash table is not sufficiently collision resistant.  

A specially-crafted set of keys could trigger hash function collisions, which can degrade performance of hash table operations complexity from an expected/average O(1) to the worst case O(n). Reporters were able to find colliding strings efficiently using meet in the middle attack.

v8 JS engine can also be used to implement server component, such as node.js platform.  In such use case, a remote attacker could possibly use this problem to trigger an excessive CPU use via specially-crafted request (such as HTTP POST request with many parameters that generate hash collisions).

This problem is similar to the issue that was previously reported for and fixed
in e.g. perl:
  http://www.cs.rice.edu/~scrosby/hash/CrosbyWallach_UsenixSec2003.pdf
Comment 2 Jan Lieskovsky 2011-11-01 12:06:09 EDT
Acknowledgements:

Red Hat would like to thank oCERT for reporting this issue. oCERT acknowledges Julian Wälde and Alexander Klink as the original reporters.
Comment 9 Tomas Hoger 2011-12-29 10:30:55 EST
v8 is available in Fedora.  Can it be used with node.js?

This issue is not relevant to JavaScript engine used in browsers, as browsers execute untrusted scripts, that can trigger CPU use via other ways.  Browsers also implement checks to detect CPU hogging scripts.
Comment 10 T.C. Hollingsworth 2011-12-29 12:55:00 EST
First, of all, note that Node.js is not presently included in Fedora due to bundled library issues.  The v8 in Fedora has been orphaned and likely will be removed from the distro in F17.  I submitted the last review for node and pushed the most recent update to v8 in Fedora with the help of a provenpackager.  I also maintain a third-party repository for node until we can work out the bundled library issues and get it into Fedora proper.

The current stable v0.6.x series of node requires v8 3.6.6 or higher, which is API and ABI-incompatible with the version included with Fedora.  (For this reason, I ship an updated v8 in my repository.)  The version of v8 included with F16, rawhide and EPEL6 is only compatible with the Node v0.4.x series, which is no longer maintained.  IIRC, the version included with F15 (and EPEL5 I think) is even older (it dates back to a much earlier review), and is only compatible with node v0.2.x, which is long dead.

v0.6.x has already fixed several security flaws, so anyone actually using Fedora's v8 w/node must already be subject to other security problems.  I'm not sure fixing this one helps them much.  That being said, I can take a look at backporting a fix when/if v8 upstream provides one.

As for people using modern node on Fedora and RHEL:  they're either using my repository or building from source.  I'll ship an updated v8 for the former as soon as it's fixed.  The latter are probably statically linking the copy of v8 bundled with the node tarball, and Node upstream will almost certainly provide a v0.6 patch release for them.
Comment 12 Tomas Hoger 2012-01-04 04:08:18 EST
Thank you for the detailed reply.  I'd say that if Fedora v8 packages are not really expected to be used with current (fully-patched) Node.js, fixing it for this issue should be of low priority.
Comment 13 T.C. Hollingsworth 2012-01-08 20:26:18 EST
I backported the fix for this to the v8 in F16:
Scratch build:  http://koji.fedoraproject.org/koji/taskinfo?taskID=3631765
SRPM:  http://koji.fedoraproject.org/koji/getfile?taskID=3631766&name=v8-3.3.10-5.fc16.src.rpm

HTH
Comment 14 Tomas Hoger 2012-01-09 08:21:34 EST
Created attachment 551564 [details]
v8 hash collision fix

In reply to comment #13)
> I backported the fix for this to the v8 in F16:
> Scratch build:  http://koji.fedoraproject.org/koji/taskinfo?taskID=3631765
> SRPM: 
> http://koji.fedoraproject.org/koji/getfile?taskID=3631766&name=v8-3.3.10-5.fc16.src.rpm

Attaching patch here, as scratch builds are deleted after some time.

Seems to be based on the following upstream commits:
http://code.google.com/p/v8/source/detail?r=10330
http://code.google.com/p/v8/source/detail?r=10351
Comment 15 T.C. Hollingsworth 2012-01-09 16:04:31 EST
Sorry, I meant to link to the complete patchset upstream.  It's here:
http://codereview.chromium.org/9124004
Comment 16 T.C. Hollingsworth 2013-03-15 21:40:20 EDT
Fixed in current Fedora/EPEL V8

Note You need to log in before you can comment on or make changes to this bug.