Newsgroups: php.internals
Path: news.php.net
Xref: news.php.net php.internals:57311
Mailing-List: contact internals-help@lists.php.net; run by ezmlm
Received-SPF: pass (pb1.pair.com: domain priacta.com designates 64.95.72.244 as permitted sender)
To: Nikita Popov <nikita.ppv@googlemail.com>, Xinchen Hui <laruence@gmail.com>
CC: Pierre Joye <pierre.php@gmail.com>, PHP internals
	<internals@lists.php.net>, =?iso-8859-1?Q?Johannes_Schl=FCter?=
	<johannes@schlueters.de>, Laruence <laruence@php.net>
Date: Mon, 9 Jan 2012 14:00:16 -0500
Thread-Topic: [PHP-DEV] Re: 5.3.9, Hash DoS, release
Thread-Index: AczO73xE1C0cVEnzRD2i5rklHa90sAADQ+Uw
Message-ID: <A633CF2D7C7BED41B41F1E64F25507B8068EF3421C@MAILR001.mail.lan>
References: <CAEZPtU44aag3z-oGAx+mF1dvr9qF0ZLpdW3pHFWEe0uwbchMBQ@mail.gmail.com>
	<6268389813742875794@unknownmsgid>
 <CAF+90c9noBgpbPBB0UEygFwr4G=Sw=0VXJxeDsKCmVxzNESRWQ@mail.gmail.com>
In-Reply-To: <CAF+90c9noBgpbPBB0UEygFwr4G=Sw=0VXJxeDsKCmVxzNESRWQ@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
acceptlanguage: en-US
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Subject: RE: [PHP-DEV] Re: 5.3.9, Hash DoS, release
From: johncrenshaw@priacta.com (John Crenshaw)

> -----Original Message-----
> From: Nikita Popov [mailto:nikita.ppv@googlemail.com]=20
> Sent: Monday, January 09, 2012 11:54 AM
> To: Xinchen Hui
> Cc: Pierre Joye; PHP internals; Johannes Schl=FCter; Laruence
> Subject: Re: [PHP-DEV] Re: 5.3.9, Hash DoS, release
>
> On Mon, Jan 9, 2012 at 5:36 PM, Xinchen Hui <laruence@gmail.com> wrote:
> > Hi:
> > =A0 I have a new idea, which is simple and also works for Jason/seriali=
zed etc.
> >
> > =A0That is Restricting a max length of a buckets list in a hash table.
> >
> > =A0 If a bucket's length exceed 1024, any insertion into this bucket=20
> > will return failure and a warning will be generated.
> >
> > =A0 What do you think?
>
> That seems like a very good approach (until we have randomization). It wo=
uld
> fix the issue in a generic way so not all functions need to be patched on=
e by
> one. It also will not hurt legit uses of many POST variables (or large
> serialized arrays).
>
> --
> PHP Internals - PHP Runtime Development Mailing List To unsubscribe, visi=
t: http://www.php.net/unsub.php

Yuck. Bad idea. Collisions happen, and for most hash algorithms there are p=
lenty of perfectly likely key sequences that will collide badly.

There are two problems here:
1. Large data sets have the potential to behave poorly if things collide ba=
dly
2. An attacker may initiate a DoS attack by supplying a large set of data t=
hat is known to collide badly

To mitigate the impact of collisions, how about using a dynamic bucket beha=
vior? Use a flat list for small/medium buckets, switch to a second level of=
 hashing if the bucket grows beyond a certain size. Something like md5 coul=
d be used as part of the hash key calculation at deeper levels to ensure th=
at the buckets don't infinitely collide. This covers the basic performance =
implications.

To prevent DoS, it has to be impossible for a malicious user to compute a p=
roblematic sequence of data. If the bucket level key computation includes a=
n additional cryptographic transformation of any sort using a secret value =
unique to the machine (or unique to the process) that is handling the reque=
st, it would be impossible for an attacker to compute a problematic sequenc=
e of keys, which should close the door on DoS.

John Crenshaw
Priacta, Inc.