Bug 800531 - D-Bus: hash table collisions CPU usage DoS
D-Bus: hash table collisions CPU usage DoS
Status: NEW
Product: Security Response
Classification: Other
Component: vulnerability (Show other bugs)
unspecified
All Linux
low Severity low
: ---
: ---
Assigned To: Red Hat Product Security
impact=low,public=20140507,reported=2...
: Security
Depends On:
Blocks: hashdos/oCERT-2011-003 802685
  Show dependency treegraph
 
Reported: 2012-03-06 11:38 EST by Kurt Seifried
Modified: 2015-07-31 02:48 EDT (History)
6 users (show)

See Also:
Fixed In Version:
Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of:
Environment:
Last Closed: 2012-03-06 11:42:31 EST
Type: ---
Regression: ---
Mount Type: ---
Documentation: ---
CRM:
Verified Versions:
Category: ---
oVirt Team: ---
RHEL 7.3 requirements from Atomic Host:


Attachments (Terms of Use)

  None (edit)
Description Kurt Seifried 2012-03-06 11:38:13 EST
Similar to the denial of service flaw present in various programming languages'
hash function usage, a potential flaw was found in the dbus implementation (specifically in the DBusHashTable() function):

A specially-crafted set of keys could trigger hash function collisions, which
degrade dictionary performance by changing hash table operations complexity
from an expected/average O(1) to the worst case O(n). 

Please note that this level of access requires both local access to the system and the ability to send specific types of dbus messages (e.g. service activiation names) in order to trigger this vulnerability and cause high CPU utilization resulting in a possible DoS.

DBus uses the following code to permute data in dbus-hash.c:

/*
 * Takes a preliminary integer hash value and produces an index into a
 * hash tables bucket list.  The idea is to make it so that
 * preliminary values that are arbitrarily similar will end up in
 * different buckets.  The hash function was taken from a
 * random-number generator. (This is used to hash integers.)
 *
 * The down_shift drops off the high bits of the hash index, and
 * decreases as we increase the number of hash buckets (to keep more
 * range in the hash index). The mask also strips high bits and strips
 * fewer high bits as the number of hash buckets increases.
 * I don't understand two things: why is the initial downshift 28
 * to keep 4 bits when the initial mask is 011 to keep 2 bits,
 * and why do we have both a mask and a downshift?
 */
#define RANDOM_INDEX(table, i) \
    (((((long) (i))*1103515245) >> (table)->down_shift) & (table)->mask)

The Red Hat Security Response Team has rated this issue as having low security 
impact. A future update may address this issue. For additional information, refer 
to the Issue Severity Classification: https://access.redhat.com/security/updates/classification/.
Comment 1 Kurt Seifried 2014-05-07 16:10:21 EDT
There doesn't appear to be many (any?) ways to inject data easily to trigger this vulnerability.
Comment 2 Kurt Seifried 2014-05-07 16:10:57 EDT
Statement:

The Red Hat Security Response Team has rated this issue as having Low to no 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.