Bug 800531 - D-Bus: hash table collisions CPU usage DoS
Summary: D-Bus: hash table collisions CPU usage DoS
Keywords:
Status: CLOSED ERRATA
Alias: None
Product: Security Response
Classification: Other
Component: vulnerability
Version: unspecified
Hardware: All
OS: Linux
low
low
Target Milestone: ---
Assignee: Red Hat Product Security
QA Contact:
URL:
Whiteboard:
Depends On:
Blocks: hashdos, oCERT-2011-003 802685
TreeView+ depends on / blocked
 
Reported: 2012-03-06 16:38 UTC by Kurt Seifried
Modified: 2021-10-19 21:51 UTC (History)
6 users (show)

Fixed In Version:
Doc Type: Bug Fix
Doc Text:
Clone Of:
Environment:
Last Closed: 2021-10-19 21:51:53 UTC
Embargoed:


Attachments (Terms of Use)

Description Kurt Seifried 2012-03-06 16:38:13 UTC
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 20:10:21 UTC
There doesn't appear to be many (any?) ways to inject data easily to trigger this vulnerability.

Comment 2 Kurt Seifried 2014-05-07 20:10:57 UTC
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.