php.net |  support |  documentation |  report a bug |  advanced search |  search howto |  statistics |  random bug |  login
Sec Bug #60623 Hash Table Collisions
Submitted: 2011-12-29 08:45 UTC Modified: 2011-12-29 09:38 UTC
From: mateuszsokola at gmail dot com Assigned:
Status: Duplicate Package: *Encryption and hash functions
PHP Version: Irrelevant OS: ANY
Private report: No CVE-ID: None
Welcome back! If you're the original bug submitter, here's where you can edit the bug or add additional notes.
If you forgot your password, you can retrieve your password here.
Password:
Status:
Package:
Bug Type:
Summary:
From: mateuszsokola at gmail dot com
New email:
PHP Version: OS:

 

 [2011-12-29 08:45 UTC] mateuszsokola at gmail dot com
Description:
------------
PHP 5 uses the DJBX33A (Dan Bernstein's times 33, addition) hash
function and parses POST form data into the $_POST hash table. Because
of the structure of the hash function, it is vulnerable to an equivalent
substring attack.

The maximal POST request size is typically limited to 8 MB, which when
filled with a set of multi-collisions would consume about four hours of
CPU time on an i7 core. Luckily, this time can not be exhausted because
it is limited by the max_input_time (default configuration: -1,
unlimited), Ubuntu and several BSDs: 60 seconds) configuration
parameter. If the max_input_time parameter is set to -1 (theoretically:
unlimited), it is bound by the max_execution_time configuration
parameter (default value: 30).

On an i7 core, the 60 seconds take a string of multi-collisions of about
500k. 30 seconds of CPU time can be generated using a string of about
300k. This means that an attacker needs about 70-100kbit/s to keep one
i7 core constantly busy. An attacker with a Gigabit connection can keep
about 10.000 i7 cores busy.


Patches

Pull Requests

History

AllCommentsChangesGit/SVN commitsRelated reports
 [2011-12-29 09:38 UTC] pajoye@php.net
-Status: Open +Status: Duplicate
 [2012-01-02 16:50 UTC] info at ambiweb dot de
An attacker could still produce a lot of cpu-time by:

- passing post-parameters that causes collisions up to the limit
- passing get-parameters that causes collisions up to the webservers url-length-
limit (usually 4-8 KB)
- passing cookie-data that causes collisions

In addition many applications are vulnerable because of processing submitted 
data 
like:

- data passed using json that causes collisions
- data passed using xml that causes collisions
...

http://svn.php.net/viewvc?view=revision&revision=321003 is covering a problem 
instead of fixing it. With this poor fix there will be attacks against php-
applications enhanced with hash-collisions.
 
PHP Copyright © 2001-2024 The PHP Group
All rights reserved.
Last updated: Sat Nov 30 16:01:29 2024 UTC