[PHP-DEV] Randomize hash-function in php

Re: [PHP-DEV] Randomize hash-function in php

Ángel González — Sun, 18 Mar 2012 17:10:01 +0100

On 18/03/12 06:56, Tjerk Anne Meesters wrote:
> On Sun, Mar 18, 2012 at 8:12 AM, Stas Malyshev wrote:
>> Obvious solution would be to use a salt for the hash, which prevents blind
>> pre-computing of hash collisions. However, due to the fact that PHP hash
>> values can be reused in different processes by bytecode caches, implementing
>> it properly is not trivial.
> What if php uses salts for specific hashes only, such as GPC (or all
> hashes whose lifetime is limited to the current reuqest), and use a
> zero-value salt for all others?
We'll need to have at least two kind of hashes, at that point, I think
it makes sense
to place the salt as a member of the HashTable struct. Bytecode caches
would just
store the salt with the hash. We can also mt_rand() the salt of each
hash, for further
randomization.

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php

Re: [PHP-DEV] Randomize hash-function in php

Xinchen Hui — Sun, 18 Mar 2012 08:20:01 +0100

Sent from my iPhone

在 2012-3-18，15:05，Tjerk Meesters 写道：

> On 18 Mar, 2012, at 2:32 PM, Xinchen Hui wrote:
>
>>> What if php uses salts for specific hashes only, such as GPC (or all
>>> hashes whose lifetime is limited to the current reuqest), and use a
>>> zero-value salt for all others?
>> definitely no，thinking of pre-calculated hash.
>
> Pre-calculated hash of what? You mean binary serialisation?
>
>> Or Ajax which use
>> json_decode parse input json.
>
> That would be considered a request lifetime hash and therefore could be salted.
>
>>
>> IMO, this Make no sense but mess things up.
>
> We all have opinions. If a clear distinction between vulnerable and non vulnerable data can be reliably made, in my limited knowledge of the whole ecosystem I genuinely think this has a shot :)
>
Ha, sorry for my rude words, I am not meaning you， but the point self;)

And it's also why I am not usually saying words at internal@ , my poor
English :)

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php

Re: [PHP-DEV] Randomize hash-function in php

Tjerk Meesters — Sun, 18 Mar 2012 08:10:02 +0100

On 18 Mar, 2012, at 2:32 PM, Xinchen Hui wrote:

>> What if php uses salts for specific hashes only, such as GPC (or all
>> hashes whose lifetime is limited to the current reuqest), and use a
>> zero-value salt for all others?
> definitely no，thinking of pre-calculated hash.

Pre-calculated hash of what? You mean binary serialisation?

> Or Ajax which use
> json_decode parse input json.

That would be considered a request lifetime hash and therefore could be salted.

>
> IMO, this Make no sense but mess things up.

We all have opinions. If a clear distinction between vulnerable and non vulnerable data can be reliably made, in my limited knowledge of the whole ecosystem I genuinely think this has a shot :)

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php

Re: [PHP-DEV] Randomize hash-function in php

Xinchen Hui — Sun, 18 Mar 2012 07:40:02 +0100

Sent from my iPhone

在 2012-3-18，13:57，Tjerk Anne Meesters 写道：

> On Sun, Mar 18, 2012 at 8:12 AM, Stas Malyshev wrote:
>> Obvious solution would be to use a salt for the hash, which prevents blind
>> pre-computing of hash collisions. However, due to the fact that PHP hash
>> values can be reused in different processes by bytecode caches, implementing
>> it properly is not trivial.
>
> What if php uses salts for specific hashes only, such as GPC (or all
> hashes whose lifetime is limited to the current reuqest), and use a
> zero-value salt for all others?
definitely no，thinking of pre-calculated hash. Or Ajax which use
json_decode parse input json.

IMO, this Make no sense but mess things up.

Thanks
>
> --
> PHP Internals - PHP Runtime Development Mailing List
> To unsubscribe, visit: http://www.php.net/unsub.php
>

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php

Re: [PHP-DEV] Randomize hash-function in php

Tjerk Anne Meesters — Sun, 18 Mar 2012 07:00:01 +0100

On Sun, Mar 18, 2012 at 8:12 AM, Stas Malyshev wrote:
> Obvious solution would be to use a salt for the hash, which prevents blind
> pre-computing of hash collisions. However, due to the fact that PHP hash
> values can be reused in different processes by bytecode caches, implementing
> it properly is not trivial.

What if php uses salts for specific hashes only, such as GPC (or all
hashes whose lifetime is limited to the current reuqest), and use a
zero-value salt for all others?

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php

Re: [PHP-DEV] Randomize hash-function in php

Stas Malyshev — Sun, 18 Mar 2012 01:20:01 +0100

Hi!

> Anyway I was looking at the hash function in PHP the other week, and was
> playing around with some different implementations. DJBX33A is fast,
> which I guess is why PHP uses it as it is hit so many times in the
> execution.

Some time ago we've checked various implementations of hash functions
and the result was none produces better results consistently than one we
already have. Note that you have to account not only for the function
itself but for the usage patterns - e.g., distribution of key sizes for
variables, functions, classes, etc.
However bigger question is - wouldn't another hash function be as
vulnerable? Unless we have a perfect hash we'll still have collisions,
and that means it still can be attacked if collisions are easy to generate.
Obvious solution would be to use a salt for the hash, which prevents
blind pre-computing of hash collisions. However, due to the fact that
PHP hash values can be reused in different processes by bytecode caches,
implementing it properly is not trivial.
--
Stanislav Malyshev, Software Architect
SugarCRM: http://www.sugarcrm.com/
(408)454-6900 ext. 227

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php

Re: [PHP-DEV] Randomize hash-function in php

Sam — Sun, 18 Mar 2012 01:10:02 +0100

On 17/03/12 23:17, Simon Schick wrote:
> Hi, All
>
> I just came around that talk a couple of days ago ..
> http://www.youtube.com/watch?v=R2Cq3CLI6H8
>
> I don't know much about hash-maps and internal php-stuff at all, but
> they say that the fix provided in 5.3.9 (and 5.4.0) is more a
> work-around than a fix ...
> Would it be an option to provide a real fix in PHP 6.0? They got the
> feedback that this will take some time and is not trivial, but we have
> a good time before PHP6 and can also break backwards compatibility for
> php-plugins if really necessary.
>
> As they said in the movie, PHP seems to have the algorithm DJBX33A
> implemented as Ruby. So as they're so proud of the fix provided by the
> Ruby-Team, may we can use that for PHP as well :)
> https://bugzilla.redhat.com/show_bug.cgi?id=CVE-2011-4815
>
> This is not much because some attacker can do something, but what if
> you have a real-world-application that (for some reason) build up an
> array that just will blow up because of that? I haven't experienced
> that until now, but it's possible ...
>
> Bye
> Simon
>

Hi,

Fairly new to this list so go easy :P..

Anyway I was looking at the hash function in PHP the other week, and was
playing around with some different implementations. DJBX33A is fast,
which I guess is why PHP uses it as it is hit so many times in the
execution.

However I tried and benchmarked a few different algorithms, I didn't try
the patch you mentioned, however the only algorithm that came anywhere
close to matching the DJBX33A method is Paul Hseih's Super Fast Hash
algorithm: http://www.azillionmonkeys.com/qed/hash.html

I benchmarked the DJBX33A against Hseih's algorithm and compared the
results using an Intel x86 architecture and an AMD 64 machine and both
algorithms performed similarly. The benchmarks weren't robust as they
were only quick, 'let's hack and see' tests. Would be interesting if
anyone else has had a go.

If I can find it I'll post a patch so you could?

Cheers

Sam

Re: [PHP-DEV] Randomize hash-function in php

Stas Malyshev — Sun, 18 Mar 2012 00:50:01 +0100

Hi!

> I don't know much about hash-maps and internal php-stuff at all, but
> they say that the fix provided in 5.3.9 (and 5.4.0) is more a
> work-around than a fix ...

This is true, it is a workaround in a meaning that the hash stays the
same, but the fix prevents one from using excessive amounts of data that
makes the hash unusable.

> Would it be an option to provide a real fix in PHP 6.0? They got the

Definitely. However doing this has some challenges. We're working on it.
--
Stanislav Malyshev, Software Architect
SugarCRM: http://www.sugarcrm.com/
(408)454-6900 ext. 227

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php

[PHP-DEV] Randomize hash-function in php

Simon Schick — Sun, 18 Mar 2012 00:20:01 +0100

Hi, All

I just came around that talk a couple of days ago ..
http://www.youtube.com/watch?v=R2Cq3CLI6H8

I don't know much about hash-maps and internal php-stuff at all, but
they say that the fix provided in 5.3.9 (and 5.4.0) is more a
work-around than a fix ...
Would it be an option to provide a real fix in PHP 6.0? They got the
feedback that this will take some time and is not trivial, but we have
a good time before PHP6 and can also break backwards compatibility for
php-plugins if really necessary.

As they said in the movie, PHP seems to have the algorithm DJBX33A
implemented as Ruby. So as they're so proud of the fix provided by the
Ruby-Team, may we can use that for PHP as well :)
https://bugzilla.redhat.com/show_bug.cgi?id=CVE-2011-4815

This is not much because some attacker can do something, but what if
you have a real-world-application that (for some reason) build up an
array that just will blow up because of that? I haven't experienced
that until now, but it's possible ...

Bye
Simon

--
PHP Internals - PHP Runtime Development Mailing List
To unsubscribe, visit: http://www.php.net/unsub.php

[PHP-DEV] Randomize hash-function in php

Simon Schick — Wed, 14 Mar 2012 21:30:02 +0100

Hi, All

I just came around that talk a couple of days ago ..
http://www.youtube.com/watch?v=R2Cq3CLI6H8

I don't know much about hash-maps and internal php-stuff at all, but they
say that the fix provided in 5.3.9 (and 5.4.0) is more a work-around than a
fix ...
Would it be an option to provide a real fix in PHP 6.0? They got the
feedback that this will take some time and is not trivial, but we have a
good time before PHP6 and can also break backwards compatibility for
php-plugins if really necessary.

As they said in the movie, PHP seems to have the algorithm DJBX33A
implemented as Ruby. So as they're so proud of the fix provided by the
Ruby-Team, may we can use that for PHP as well :)
https://bugzilla.redhat.com/show_bug.cgi?id=CVE-2011-4815

This is not much because some attacker can do something, but what if you
have a real-world-application that (for some reason) build up an array that
just will blow up because of that? I haven't experienced that until now,
but it's possible ...

Bye
Simon