User: Password:
Subscribe / Log in / New account


Denial of service via hash collisions

By Jake Edge
January 11, 2012

Man pages (or perldoc pages in this case) are not the usual places to look for security holes, but that is apparently where two researchers found a whole class of problems for web application frameworks (and the languages underlying them). The problem concerns dictionaries (aka hashes, depending on the language) and was fixed in Perl in 2003, but the need for a fix evidently wasn't clear to other high-level/scripting language developers. So, Julian Wälde and Alexander Klink were able to report efficient denial-of-service attacks against PHP, Python, Java, Ruby, and the v8 JavaScript engine via some of the web frameworks that use those languages at the recently held Chaos Communication Congress.

The "perlsec" perldoc page has a section on "Algorithmic Complexity Attacks" that explains the problem that was fixed in Perl and is (or was) present in other languages. Dictionaries are data structures offered by some languages to store key/value pairs, which are implemented using a hash table based on the key. Unlike a cryptographic hash, the hash functions that are used for hash tables are meant to be efficient in terms of CPU usage, but still offer collision resistance. But, if the same hash function is used for every installation and invocation of a given language, one can fairly easily calculate a set of dictionary keys that collide. That's where the problem starts.

A hash table needs to have some way of dealing with collisions, where two different key values hash to the same value. One common way is to have each hash "bucket" be a linked list of all the dictionary entries that hash to the bucket index. In most cases, that works just fine as the number of collisions is typically small, so the slight inefficiency of traversing the list for insertion, deletion, and searching is in the noise. But if an attacker can control the keys that are being inserted, they can arrange that all of them hash to the same bucket. So, that turns the usual case of an insertion requiring the traversal of a few collisions, at worst, to an insertion requiring traversal of all entries added so far.

If all keys hash to the same bucket, the entire linked list for the bucket must be traversed in order to insert a new key. During the traversal, each stored key must be compared with the insertion key to see if it is already present (which it wouldn't be in the attack scenario, but the hash table insertion code doesn't know that). As more and more keys get added, that traversal takes longer and longer, to a point where it can chew up some fairly significant CPU time. But how can an attacker control the key values that get stored?

That's where web frameworks come into play. Those frameworks helpfully collect up all of the POST form data that gets sent to a particular web page into a dictionary that gets handed off to the application for processing. The amount of data that the frameworks will allow is typically rather large (e.g. 1MB), so an attacker can create tens of thousands of form entries in a single HTTP request. Because they all collide, those entries can take tens of seconds to a few minutes to process on an i7 core according to the advisory [PDF] released by Wälde and Klink.

Because the languages do not randomize the hash function used in any way, the collisions that get calculated are usable for a wide variety of web applications. It is likely that collisions calculated for Python would work on most Python-based web applications for example. The presentation (slides [PDF]) mentions two different techniques to find collisions that are computationally feasible, but they are both "offline" calculations and cannot be used if the hash function changes between invocations and sites. Thus, the suggested fix for the problem is to choose a random seed that gets mixed into the hash so that collisions are not predictable. That seed would be chosen at language start-up time so that each invocation essentially had its own hash function.

There are workarounds for the problem as well. Web frameworks could (probably should) limit the amount of form data that can be processed and/or the number of form elements that are allowed in a given POST. Another potential workaround is to limit the amount of CPU time that a web application is allowed to use. If a given POST can only soak up ten seconds of a core, for example, it will take more of them (i.e. more bandwidth) to fully saturate a given server or set of servers.

While randomizing the hash function is suggested, it may not be a complete solution. Discussion on the python-dev mailing list and in Python bug 13703 indicate that more is needed to eradicate the problem. As Paul McMillan put it: "I've gotten confirmation from several other sources that the fix recommended by the presenters (just a random initialization seed) only prevents the most basic form of the attack." For long-running Python interpreters, it may be feasible for an attacker to brute force or otherwise determine the random seed that was used.

Determining the random seed will be easier to do with an "oracle function", which is some mechanism that an attacker can use to get information about the hash values of various strings. It does not require that the "raw" hash values be returned, necessarily, as other information (like JSON dictionary key ordering, for example) can be used to deduce the seed. Those are much harder attacks than the simple "POST with thousands of collisions" attack that is available today, however.

Other languages, including Perl and Ruby have fixed the simpler problem, but Python is looking at going further. One way to do that would be to use a much larger seed, and choose pieces of the seed to add into the hash based on properties of the input string, which essentially increases the search space for brute force and other means of deducing the seed.

PHP has also started to consider fixes. According to the advisory, Oracle has determined that no fix will be applied to Java itself, but that the GlassFish application server will be updated to fix or work around the problem.

The 2003 research [PDF] by Scott A. Crosby and Dan S. Wallach clearly showed the flaw, but didn't apply it to any other language beyond Perl. That led to the Perl fix, but even a heads-up message to python-dev by Crosby was not enough to cause a fix in Python at that time. Part of the problem was the inability to point to an easy way for an attacker to control the keys put into a dictionary. Evidently, the web frameworks were not considered at that time.

According to McMillan, though, the web frameworks are just the tip of the iceberg in terms of the scope of the problem. Various Python developers had suggested that the problem should be fixed in the web frameworks (as Java is evidently doing) or in a few standard libraries (like urllib, cgi, and json), but McMillan states that the problem goes much further than that:

A short and very incomplete list of vulnerable standard lib modules includes: every single parsing library (json, xml, html, plus all the third party libraries that do that), all of numpy (because it processes data which probably came from a user [yes, integers can trigger the vulnerability]), difflib, the math module, most database adaptors, anything that parses metadata (including commonly used third party libs like PIL), the tarfile lib along with other compressed format handlers, the csv module, robotparser, plistlib, argparse, pretty much everything under the heading of "18. Internet Data Handling" (email, mailbox, mimetypes, etc.), "19. Structured Markup Processing Tools", "20. Internet Protocols and Support", "21. Multimedia Services", "22. Internationalization", TKinter, and all the os calls that handle filenames. The list is impossibly large, even if we completely ignore user code. This MUST be fixed at a language level.

Work on testing and benchmarking changes for Python is ongoing, but the plan is to provide a security release for 2.6, 2.7, and 3.3, while also providing backported patches for earlier Pythons. PHP is discussing options, including placing limits on the length of hash collision chains and limiting the number of form variables that will be processed, while still planning to add randomization into the hashing function.

It is interesting to see a nearly ten-year-old flaw pop back up, though it seems likely that the flaw hasn't been exploited widely (or fixes would have come sooner). It does serve as a reminder that what may seem like theoretical vulnerabilities will, over time, often become actual vulnerabilities. It's sometimes hard to consider making changes for "theoretical" attacks, which may well be the right choice at the time, but it is worth pondering the likelihood that eventually the change will need to be made. Like most security questions—as with the rest of software development—it's always a matter of trade-offs.

Comments (75 posted)

Brief items

Security quotes of the week

Some of the password attempts are predictable (e.g. username: "root", password: "root") but others are less easy to explain. For example, there was a log-in attempt for the usernames "root" and "dark" with the password "ManualulIngineruluiMecanic", which I think is Romanian for Handbook of Mechanical Engineering. Why would someone use this password, especially for the uncommon username "dark"? Is this book common in Romania; is it likely to be by the desk of a sys-admin (or hacker) trying to choose a password? Has the hacker found the password in use on another compromised system; is it the default password for anything?
-- Steven J. Murdoch investigates SSH brute force attempts

In October 2011, ticket #4185 was filed in the Tor bug tracker by a user in China who found that their connections to US-based Tor bridge relays were being regularly cut off after a very short period of time. At the time we performed some basic experimentation and discovered that Chinese IPs (presumably at the behest of the Great Firewall of China, or GFW) would reach out to the US-based bridge and connect to it shortly after the Tor user in China connected, and, if successful, shortly thereafter the connection would be blocked by the GFW.
-- Tim Wilde on the Tor project blog

Comments (none posted)

New vulnerabilities

apache: multiple vulnerabilities

Package(s):apache CVE #(s):CVE-2011-3607 CVE-2011-4317
Created:January 10, 2012 Updated:January 11, 2012
Description: From the Mandriva advisory:

Integer overflow in the ap_pregsub function in server/util.c in the Apache HTTP Server 2.0.x through 2.0.64 and 2.2.x through 2.2.21, when the mod_setenvif module is enabled, allows local users to gain privileges via a .htaccess file with a crafted SetEnvIf directive, in conjunction with a crafted HTTP request header, leading to a heap-based buffer overflow (CVE-2011-3607).

The mod_proxy module in the Apache HTTP Server 1.3.x through 1.3.42, 2.0.x through 2.0.64, and 2.2.x through 2.2.21, when the Revision 1179239 patch is in place, does not properly interact with use of (1) RewriteRule and (2) ProxyPassMatch pattern matches for configuration of a reverse proxy, which allows remote attackers to send requests to intranet servers via a malformed URI containing an \@ (at sign) character and a : (colon) character in invalid positions. NOTE: this vulnerability exists because of an incomplete fix for CVE-2011-3368 (CVE-2011-4317).

Oracle ELSA-2013-0512 httpd 2013-02-25
openSUSE openSUSE-SU-2013:0248-1 apache2 2013-02-05
openSUSE openSUSE-SU-2013:0243-1 apache2 2013-02-05
Gentoo 201206-25 apache 2012-06-24
Oracle ELSA-2012-0323 httpd 2012-03-09
Scientific Linux SL-http-20120306 httpd 2012-03-06
Fedora FEDORA-2012-1642 httpd 2012-03-06
Red Hat RHSA-2012:0323-01 httpd 2012-02-21
Fedora FEDORA-2012-1598 httpd 2012-02-21
Ubuntu USN-1368-1 apache2 2012-02-16
Scientific Linux SL-http-20120214 httpd 2012-02-14
Oracle ELSA-2012-0128 httpd 2012-02-14
CentOS CESA-2012:0128 httpd 2012-02-14
Red Hat RHSA-2012:0128-01 httpd 2012-02-13
Slackware SSA:2012-041-01 apr 2012-02-10
openSUSE openSUSE-SU-2012:0212-1 apache2 2012-02-09
openSUSE openSUSE-SU-2012:0248-1 apache2 2012-02-09
Debian DSA-2405-1 apache2 2012-02-06
Mandriva MDVSA-2012:003 apache 2012-01-10

Comments (none posted)

cacti: command execution

Package(s):cacti CVE #(s):CVE-2011-4824
Created:January 9, 2012 Updated:January 23, 2012
Description: From the CVE entry:

SQL injection vulnerability in auth_login.php in Cacti before 0.8.7h allows remote attackers to execute arbitrary SQL commands via the login_username parameter.

Debian DSA-2384-2 cacti 2012-02-04
Mandriva MDVSA-2012:010 cacti 2012-01-20
Debian DSA-2384-1 cacti 2012-01-09

Comments (none posted)

chromium: multiple vulnerabilities

Package(s):chromium CVE #(s):CVE-2011-3903 CVE-2011-3904 CVE-2011-3906 CVE-2011-3907 CVE-2011-3908 CVE-2011-3909 CVE-2011-3910 CVE-2011-3912 CVE-2011-3913 CVE-2011-3914 CVE-2011-3917 CVE-2011-3921 CVE-2011-3922
Created:January 9, 2012 Updated:January 30, 2012
Description: From the Gentoo advisory:

Multiple vulnerabilities have been discovered in Chromium and V8. A context-dependent attacker could entice a user to open a specially crafted web site or JavaScript program using Chromium or V8, possibly resulting in the execution of arbitrary code with the privileges of the process, or a Denial of Service condition.

Oracle ELSA-2012-0880 qt 2012-07-02
Fedora FEDORA-2011-17565 qt 2012-01-29
Fedora FEDORA-2012-0523 qt 2012-01-22
SUSE SUSE-SU-2012:0097-1 libqt4 2012-01-19
openSUSE openSUSE-SU-2012:0091-1 libqt4 2012-01-19
Gentoo 201201-03 chromium 2012-01-08

Comments (none posted)

glibc: heap overflow

Package(s):glibc CVE #(s):CVE-2009-5029
Created:January 5, 2012 Updated:February 13, 2012
Description: From the openSUSE advisory:

Specially crafted time zone files could cause a heap overflow in glibc.

Gentoo 201312-01 glibc 2013-12-02
Ubuntu USN-1396-1 eglibc, glibc 2012-03-09
Scientific Linux SL-glib-20120214 glibc 2012-02-14
Scientific Linux SL-glib-20120214 glibc 2012-02-14
Oracle ELSA-2012-0126 glibc 2012-02-14
Oracle ELSA-2012-0125 glibc 2012-02-14
CentOS CESA-2012:0126 glibc 2012-02-14
CentOS CESA-2012:0125 glibc 2012-02-14
Red Hat RHSA-2012:0125-01 glibc 2012-02-13
Red Hat RHSA-2012:0126-01 glibc 2012-02-13
Slackware SSA:2012-041-05 vsftpd 2012-02-10
Slackware SSA:2012-041-03 glibc 2012-02-10
CentOS CESA-2012:0058 glibc 2012-01-30
Scientific Linux SL-glib-20120125 glibc 2012-01-25
Red Hat RHSA-2012:0058-01 glibc 2012-01-24
Oracle ELSA-2012-0058 glibc 2012-01-25
Fedora FEDORA-2012-0018 glibc 2012-01-02
SUSE SUSE-SU-403 openSSL 2012-01-05
SUSE SUSE-SU-2012:0033-1 glibc 2012-01-05
SUSE SUSE-SU-2012:0023-1 glibc 2012-01-05
openSUSE openSUSE-SU-2012:0064-1 glibc 2012-01-05

Comments (none posted)

kernel: denial of service

Package(s):kernel CVE #(s):CVE-2011-4622
Created:January 9, 2012 Updated:March 6, 2012
Description: From the Red Hat bugzilla:

User space may create the PIT and forget about setting up the irqchips. In that case, firing PIT IRQs will crash the host.

openSUSE openSUSE-SU-2013:0925-1 kernel 2013-06-10
SUSE SUSE-SU-2013:0786-1 Linux kernel 2013-05-14
openSUSE openSUSE-SU-2013:0927-1 kernel 2013-06-10
SUSE SUSE-SU-2012:0616-1 Linux kernel 2012-05-14
Oracle ELSA-2012-0350 kernel 2012-03-12
Oracle ELSA-2012-2003 kernel-uek 2012-03-12
Oracle ELSA-2012-2003 kernel-uek 2012-03-12
Scientific Linux SL-kern-20120308 kernel 2012-03-08
Oracle ELSA-2012-0149 kvm 2012-03-07
CentOS CESA-2012:0350 kernel 2012-03-07
Ubuntu USN-1389-1 linux 2012-03-06
Red Hat RHSA-2012:0350-01 kernel 2012-03-06
Ubuntu USN-1388-1 linux-ec2 2012-03-06
Ubuntu USN-1387-1 linux-lts-backport-maverick 2012-03-06
Ubuntu USN-1386-1 linux-lts-backport-natty 2012-03-06
Ubuntu USN-1384-1 linux-lts-backport-oneiric 2012-03-06
Ubuntu USN-1363-1 linux 2012-02-13
Ubuntu USN-1362-1 linux 2012-02-13
Ubuntu USN-1361-1 linux 2012-02-13
CentOS CESA-2012:0051 kvm 2012-01-24
Scientific Linux SL-kvm-20120124 kvm 2012-01-24
Oracle ELSA-2012-0051 kvm 2012-01-23
Red Hat RHSA-2012:0051-01 kvm 2012-01-23
Fedora FEDORA-2012-0492 kernel 2012-01-14
Fedora FEDORA-2012-0363 kernel 2012-01-11
Debian DSA-2389-1 linux-2.6 2012-01-15
Fedora FEDORA-2012-0145 kernel 2012-01-05

Comments (none posted)

kernel: denial of service

Package(s):kernel CVE #(s):CVE-2011-3637 CVE-2011-4324 CVE-2011-4325 CVE-2011-4348
Created:January 11, 2012 Updated:January 11, 2012
Description: The kernel suffers from four independent denial of service vulnerabilities in the SELinux subsystem (CVE-2011-4348), module subsystem (CVE-2011-3637), and NFS subsystem (CVE-2011-4324 CVE-2011-4325).
Oracle ELSA-2013-1645 kernel 2013-11-26
SUSE SUSE-SU-2012:0736-1 Linux kernel 2012-06-14
Oracle ELSA-2012-0150 kernel 2012-03-07
Ubuntu USN-1390-1 linux 2012-03-06
Red Hat RHSA-2012:0116-01 kernel 2012-02-15
Oracle ELSA-2012-0007 kernel 2012-01-12
Scientific Linux SL-kern-20120112 kernel 2012-01-12
CentOS CESA-2012:0007 kernel 2012-01-11
Red Hat RHSA-2012:0010-01 kernel-rt 2012-01-10
Red Hat RHSA-2012:0007-01 kernel 2012-01-10

Comments (none posted)

libvirt: firewalled port exposure

Package(s):libvirt CVE #(s):CVE-2011-4600
Created:January 6, 2012 Updated:January 11, 2012

From the Fedora advisory:

This release of libvirt fixes a minor security problem with extraneous iptables rules being added when an externally managed network (new feature in 0.9.4) exists.

More information can be found in the Red Hat bugzilla entry.

Fedora FEDORA-2011-17267 libvirt 2011-12-22
Ubuntu USN-2867-1 libvirt 2016-01-12

Comments (2 posted)

nova: access control bypass

Package(s):nova CVE #(s):CVE-2012-0030
Created:January 11, 2012 Updated:January 20, 2012
Description: From the Ubuntu advisory: Nachi Ueno, Rohit Karajgi, and Venkatesan Ravikumar discovered that when Nova is configured to use the OpenStack API, it would not correctly enforce access controls on certain incoming requests. A remote authenticated attacker could exploit this to change resources of arbitrary tenants.
Ubuntu USN-1326-1 nova 2012-01-11

Comments (none posted)

openssl: multiple vulnerabilities

Package(s):openssl CVE #(s):CVE-2011-4108 CVE-2011-4576 CVE-2011-4577 CVE-2011-4619 CVE-2011-4109 CVE-2012-0027
Created:January 11, 2012 Updated:February 7, 2012
Description: Openssl prior to versions 1.0.0f and 0.9.8s suffers from a number of information disclosure and denial of service vulnerabilities; see this advisory for details.
SUSE SUSE-SU-2014:0320-1 gnutls 2014-03-04
openSUSE openSUSE-SU-2013:0336-1 openssl 2013-02-25
SUSE SUSE-SU-2012:0674-1 openssl 2012-05-30
Debian DSA-2454-1 openssl 2012-04-19
Oracle ELSA-2012-0426 openssl 2012-03-28
Oracle ELSA-2012-0426 openssl 2012-03-28
Scientific Linux SL-open-20120328 openssl 2012-03-28
CentOS CESA-2012:0426 openssl 2012-03-28
CentOS CESA-2012:0426 openssl 2012-03-28
Red Hat RHSA-2012:0426-01 openssl 2012-03-27
Gentoo 201203-12 openssl 2012-03-05
Ubuntu USN-1357-1 openssl 2012-02-09
CentOS CESA-2012:0060 openssl 2012-02-07
Scientific Linux SL-open-20120201 openssl 2012-02-01
Oracle ELSA-2012-0086 openssl 2012-02-01
CentOS CESA-2012:0086 openssl 2012-02-01
Red Hat RHSA-2012:0086-01 openssl 2012-02-01
CentOS CESA-2012:0059 openssl 2012-01-30
Scientific Linux SL-open-20120125 openssl 2012-01-25
Scientific Linux SL-open-20120125 openssl 2012-01-25
Red Hat RHSA-2012:0059-01 openssl 2012-01-24
Red Hat RHSA-2012:0060-01 openssl 2012-01-24
Oracle ELSA-2012-0059 openssl 2012-01-25
Oracle ELSA-2012-0060 openssl 2012-01-25
CentOS CESA-2012:0060 openssl 2012-01-25
Mandriva MDVSA-2012:007 openssl 2012-01-16
Mandriva MDVSA-2012:006 openssl 2012-01-16
SUSE SUSE-SU-2012:0084-1 OpenSSL 2012-01-16
openSUSE openSUSE-SU-2012:0083-1 openssl 2012-01-16
Fedora FEDORA-2012-0250 openssl 2012-01-07
Debian DSA-2390-1 openssl 2012-01-15
Fedora FEDORA-2012-0232 openssl 2012-01-07

Comments (none posted)

pdns: denial of service

Package(s):pdns CVE #(s):CVE-2012-0206
Created:January 10, 2012 Updated:February 23, 2012
Description: From the Debian advisory:

Ray Morris discovered that the PowerDNS authoritative sever responds to response packets. An attacker who can spoof the source address of IP packets can cause an endless packet loop between a PowerDNS authoritative server and another DNS server, leading to a denial of service.

Gentoo 201202-04 pdns 2012-02-22
Fedora FEDORA-2012-1207 pdns 2012-02-10
openSUSE openSUSE-SU-2012:0200-1 powerdns 2012-02-09
Fedora FEDORA-2012-0263 pdns 2012-01-19
Debian DSA-2385-1 pdns 2012-01-10

Comments (none posted)

python-virtualenv: symlink attack

Package(s):python-virtualenv CVE #(s):CVE-2011-4617
Created:January 6, 2012 Updated:June 25, 2012
Description: From the CVE entry: in virtualenv before 1.5 allows local users to overwrite arbitrary files via a symlink attack on a certain file in /tmp/.

Gentoo 201206-17 virtualenv 2012-06-22
Fedora FEDORA-2011-17341 python-virtualenv 2011-12-22
Fedora FEDORA-2011-17289 python-virtualenv 2011-12-22

Comments (none posted)

ruby: denial of service

Package(s):ruby CVE #(s):CVE-2011-4815
Created:January 11, 2012 Updated:February 28, 2012
Description: Ruby, like many scripting languages, enables the predictable creation of hash collisions. This "feature" can be exploited for a denial of service attack.
Debian-LTS DLA-263-1 ruby1.9.1 2015-07-01
Gentoo 201412-27 ruby 2014-12-13
Mandriva MDVSA-2012:024 ruby 2012-02-28
Ubuntu USN-1377-1 ruby1.8 2012-02-27
openSUSE openSUSE-SU-2012:0228-1 Ruby 2012-02-09
Scientific Linux SL-ruby-20120131 ruby 2012-01-31
Scientific Linux SL-ruby-20120130 ruby 2012-01-30
Oracle ELSA-2012-0070 ruby 2012-01-31
Oracle ELSA-2012-0070 ruby 2012-01-31
Oracle ELSA-2012-0069 ruby 2012-01-31
CentOS CESA-2012:0070 ruby 2012-01-30
CentOS CESA-2012:0070 ruby 2012-01-30
CentOS CESA-2012:0069 ruby 2012-01-30
Red Hat RHSA-2012:0070-01 ruby 2012-01-30
Red Hat RHSA-2012:0069-01 ruby 2012-01-30
Fedora FEDORA-2011-17551 ruby 2012-01-10
Fedora FEDORA-2011-17542 ruby 2012-01-10

Comments (none posted)

super: buffer overflow

Package(s):super CVE #(s):CVE-2011-2776
Created:January 9, 2012 Updated:January 11, 2012
Description: From the Debian advisory:

Robert Luberda discovered a buffer overflow in the syslog logging code of Super, a tool to execute scripts (or other commands) as if they were root. The default Debian configuration is not affected.

Debian DSA-2383-1 super 2012-01-08

Comments (none posted)

zabbix: multiple cross-site scripting vulnerabilities

Package(s):zabbix CVE #(s):CVE-2011-4615 CVE-2011-5027
Created:January 9, 2012 Updated:January 11, 2012
Description: From the CVE entries:

Multiple cross-site scripting (XSS) vulnerabilities in Zabbix before 1.8.10 allow remote attackers to inject arbitrary web script or HTML via the gname parameter (aka host groups name) to (1) hostgroups.php and (2) usergrps.php, the update action to (3) hosts.php and (4) scripts.php, and (5) maintenance.php. (CVE-2011-4615)

Cross-site scripting (XSS) vulnerability in ZABBIX before 1.8.10 allows remote attackers to inject arbitrary web script or HTML via unspecified vectors related to the profiler. (CVE-2011-5027)

Fedora FEDORA-2011-17559 zabbix 2011-12-30
Fedora FEDORA-2011-17560 zabbix 2011-12-30

Comments (none posted)

Page editor: Jake Edge
Next page: Kernel development>>

Copyright © 2012, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds