Bug 787888 - (CVE-2012-0839) CVE-2012-0839 ocaml: hash table collisions CPU usage DoS (oCERT-2011-003)
CVE-2012-0839 ocaml: hash table collisions CPU usage DoS (oCERT-2011-003)
Status: CLOSED NEXTRELEASE
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: 842636 842637 842638 842639
Blocks: hashdos/oCERT-2011-003 787889
  Show dependency treegraph
 
Reported: 2012-02-06 20:18 EST by Kurt Seifried
Modified: 2014-06-12 14:37 EDT (History)
3 users (show)

See Also:
Fixed In Version:
Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of:
Environment:
Last Closed: 2014-06-12 14:37:07 EDT
Type: ---
Regression: ---
Mount Type: ---
Documentation: ---
CRM:
Verified Versions:
Category: ---
oVirt Team: ---
RHEL 7.3 requirements from Atomic Host:
Cloudforms Team: ---


Attachments (Terms of Use)

  None (edit)
Description Kurt Seifried 2012-02-06 20:18:04 EST
Julian Wälde and Alexander Klink reported a flaw in the hash function used in
the implementation of various hash based arrays. 

http://caml.inria.fr/pub/docs/manual-ocaml/libref/Hashtbl.html

A specially-crafted set of keys could trigger hash function collisions, which
degrade hash table performance by changing 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 equivalent substrings or meet in the
middle techniques.

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

Discussion of a fix for ocaml is taking place in this email thread:

http://www.mail-archive.com/caml-list@inria.fr/msg01477.html
Comment 1 Richard W.M. Jones 2012-02-07 03:18:29 EST
Are we proposing to fix this for RHEL too?  There are
no OCaml applications in RHEL which are vulnerable to this.
Comment 2 Kurt Seifried 2012-03-09 19:30:32 EST
We ship the ocaml language so ideally we need to fix it for our customers that do use it. Emailed ocaml to confirm if they're done fixing it.
Comment 3 Richard W.M. Jones 2012-03-10 02:29:04 EST
(In reply to comment #2)
> We ship the ocaml language so ideally we need to fix it for our customers that
> do use it. Emailed ocaml to confirm if they're done fixing it.

Where is this email?

Anyway, upstream haven't started fixing it.  There is
opposition from people who want Hashtbl to work
reproducibly (naturally without them having to make any
changes to their code nor to their workflow).
Comment 4 Kurt Seifried 2012-04-03 00:21:35 EDT
I misspoke, they are still discussing fixing it in this thread: 

http://www.mail-archive.com/caml-list@inria.fr/msg02104.html

"OCaml 3.13 will provide options for Hashtbl allowing it pass a seed, but
only in a case by case way. What will not be included in OCaml 3.13 is
access to RNGs with entropy injection (i.e. it is left to the programmer
to solve this difficulty)."
Comment 5 Kurt Seifried 2012-04-03 12:47:04 EDT
According to Xavier Leroy Xavier.Leroy@inria.fr:

We decided to skip the 3.13 release entirely and go straight to 4.00.
The 4.00 release is scheduled for June 2012.

http://caml.inria.fr/mantis/view.php?id=5572
Comment 6 Stefan Cornelius 2012-07-24 06:03:24 EDT
Fixed in SVN:
http://caml.inria.fr/cgi-bin/viewvc.cgi?view=revision&revision=11056
http://caml.inria.fr/cgi-bin/viewvc.cgi?view=revision&revision=12383 (4.0 branch)
http://caml.inria.fr/cgi-bin/viewvc.cgi?view=revision&revision=12384 (trunk)

I've also noticed the following fix in ocamlnet 3.5.1:
https://godirepo.camlcity.org/wwwsvn?rev=1683&root=lib-ocamlnet2&view=rev

We don't seem to ship this in RHEL, but Fedora 16 and 17 include versions earlier then 3.5.1. Rawhide contains 3.5.1 already.
Comment 7 Stefan Cornelius 2012-07-24 06:07:56 EDT
Created ocaml-ocamlnet tracking bugs for this issue

Affects: fedora-all [bug 842637]
Comment 8 Stefan Cornelius 2012-07-24 06:07:59 EDT
Created ocaml tracking bugs for this issue

Affects: fedora-all [bug 842636]
Affects: epel-4 [bug 842638]
Affects: epel-5 [bug 842639]
Comment 10 Tomas Hoger 2014-06-12 14:37:07 EDT
This issue does not affect any OCaml applications shipped in Red Hat Enterprise Linux 6.  OCaml is only shipped via unsupported Optional repository as a build dependency.  Therefore, this issue is not planned to be addressed in future Red Hat Enterprise Linux 6 updates.  The fix is included in OCaml packages shipped as part of Red Hat Enterprise Linux 7.

Statement:

The Red Hat Security Response Team has rated this issue as having Moderate security impact. This issue is not currently planned to be addressed in future updates. For additional information, refer to the Issue Severity Classification: https://access.redhat.com/security/updates/classification/.

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