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
Acknowledgements: Red Hat would like to thank oCERT for reporting this issue. oCERT acknowledges Julian Wälde and Alexander Klink as the original reporters.
This issue was presented on 28C3: http://events.ccc.de/congress/2011/Fahrplan/events/4680.en.html Details were posted to full-disclosure: http://seclists.org/fulldisclosure/2011/Dec/477 oCERT advisory: http://www.ocert.org/advisories/ocert-2011-003.html n.runs advisory (copy of the full-disclosure post): http://www.nruns.com/_downloads/advisory28122011.pdf 28C3 slides and recording: http://events.ccc.de/congress/2011/Fahrplan/attachments/2007_28C3_Effective_DoS_on_web_application_platforms.pdf http://www.youtube.com/28c3#p/u/22/R2Cq3CLI6H8 Another good write-up of the issue: http://cryptanalysis.eu/blog/2011/12/28/effective-dos-attacks-against-web-application-plattforms-hashdos/
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.
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.
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.
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
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
Sorry, I meant to link to the complete patchset upstream. It's here: http://codereview.chromium.org/9124004
Fixed in current Fedora/EPEL V8