|  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
 [2011-12-29 08:45 UTC] mateuszsokola at gmail dot com
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.


Add a Patch

Pull Requests

Add a Pull Request


AllCommentsChangesGit/SVN commitsRelated reports
 [2011-12-29 09:38 UTC]
-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 passed using json that causes collisions
- data passed using xml that causes collisions
... 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-2021 The PHP Group
All rights reserved.
Last updated: Mon Oct 18 11:04:16 2021 UTC