Hi:
the origin thread is too long, so I open a new thread for this.
I have made another patch try to fix this issue.
the key point is, randomizing the table size(tableMask).
instead of double the the table size in zend_hash_do_resize, I
increase the table size with a random delta ( the value now is just a
try, we can change it to a more appropriate value),
that is: new_table_size = old_table_size * 2 + random_num.
then, the collision can not be predicatible, which fix the
problem, and also fixed the issue in json/soap/serialize etc.
here is the patch(draft now):
https://bugs.php.net/patch-display.php?bug_id=60655&patch=rand_hash_resize.patch&revision=latest
after this fix , may slow down the php, but compared to the
security threat I thinks the cost could be ignored.
for the test script list in
http://nikic.github.com/2011/12/28/Supercolliding-a-PHP-array.html:
*before patched:
Inserting 65536 evil elements took 162.65940284729 seconds
Inserting 65536 good elements took 0.075557947158813 seconds
*after patched:
Inserting 65536 evil elements took 0.074128866195679 seconds
Inserting 65536 good elements took 0.091044902801514 seconds
what do you think ?
thanks
--
Laruence Xinchen Hui
http://www.laruence.com/
Hi:
run bench.php:
*before patched:
$ sapi/cli/php Zend/bench.php
simple 0.374
simplecall 0.720
simpleucall 0.600
simpleudcall 0.633
mandel 1.161
mandel2 1.632
ackermann(7) 0.810
ary(50000) 0.108
ary2(50000) 0.098
ary3(2000) 0.699
fibo(30) 2.180
hash1(50000) 0.168
hash2(500) 0.171
heapsort(20000) 0.395
matrix(20) 0.354
nestedloop(12) 0.656
sieve(30) 0.441
strcat(200000) 0.073
Total 11.276
*after patched:
sapi/cli/php Zend/bench.php
simple 0.520
simplecall 0.723
simpleucall 0.622
simpleudcall 0.639
mandel 1.168
mandel2 1.711
ackermann(7) 0.784
ary(50000) 0.116
ary2(50000) 0.100
ary3(2000) 0.749
fibo(30) 2.188
hash1(50000) 0.177
hash2(500) 0.184
heapsort(20000) 0.421
matrix(20) 0.420
nestedloop(12) 0.836
sieve(30) 0.458
strcat(200000) 0.073
Total 11.888
thanks
Hi:
the origin thread is too long, so I open a new thread for this.I have made another patch try to fix this issue.
the key point is, randomizing the table size(tableMask).
instead of double the the table size in zend_hash_do_resize, I
increase the table size with a random delta ( the value now is just a
try, we can change it to a more appropriate value),
that is: new_table_size = old_table_size * 2 + random_num.then, the collision can not be predicatible, which fix the
problem, and also fixed the issue in json/soap/serialize etc.here is the patch(draft now):
https://bugs.php.net/patch-display.php?bug_id=60655&patch=rand_hash_resize.patch&revision=latestafter this fix , may slow down the php, but compared to the
security threat I thinks the cost could be ignored.for the test script list in
http://nikic.github.com/2011/12/28/Supercolliding-a-PHP-array.html:*before patched:
Inserting 65536 evil elements took 162.65940284729 seconds
Inserting 65536 good elements took 0.075557947158813 seconds*after patched:
Inserting 65536 evil elements took 0.074128866195679 seconds
Inserting 65536 good elements took 0.091044902801514 secondswhat do you think ?
thanks
--
Laruence Xinchen Hui
http://www.laruence.com/
--
Laruence Xinchen Hui
http://www.laruence.com/
Hi:
the origin thread is too long, so I open a new thread for this.I have made another patch try to fix this issue.
the key point is, randomizing the table size(tableMask).
instead of double the the table size in zend_hash_do_resize, I
increase the table size with a random delta ( the value now is just a
try, we can change it to a more appropriate value),
that is: new_table_size = old_table_size * 2 + random_num.then, the collision can not be predicatible, which fix the
problem, and also fixed the issue in json/soap/serialize etc.here is the patch(draft now):
https://bugs.php.net/patch-display.php?bug_id=60655&patch=rand_hash_resize.patch&revision=latestafter this fix , may slow down the php, but compared to the
security threat I thinks the cost could be ignored.for the test script list in
http://nikic.github.com/2011/12/28/Supercolliding-a-PHP-array.html:*before patched:
Inserting 65536 evil elements took 162.65940284729 seconds
Inserting 65536 good elements took 0.075557947158813 seconds*after patched:
Inserting 65536 evil elements took 0.074128866195679 seconds
Inserting 65536 good elements took 0.091044902801514 secondswhat do you think ?
At least one problem with your patch is that it uses crypto safe
random numbers. The problem with that is that the very frequent random
number fetches could deplete the entropy pool and thus make
/dev/urandom (and probably the Windows RNG too) block. So you would
again have a DOS vulnerability (just create many small arrays with 16
elements so they get resized a few times). Additionally this could
also impose a security threat to other application that rely on the
entropy source.
Nikita
Hi,
Hi:
the origin thread is too long, so I open a new thread for this.I have made another patch try to fix this issue.
the key point is, randomizing the table size(tableMask).
instead of double the the table size in zend_hash_do_resize, I
increase the table size with a random delta ( the value now is just a
try, we can change it to a more appropriate value),
that is: new_table_size = old_table_size * 2 + random_num.then, the collision can not be predicatible, which fix the
problem, and also fixed the issue in json/soap/serialize etc.here is the patch(draft now):
https://bugs.php.net/patch-display.php?bug_id=60655&patch=rand_hash_resize.patch&revision=latestafter this fix , may slow down the php, but compared to the
security threat I thinks the cost could be ignored.for the test script list in
http://nikic.github.com/2011/12/28/Supercolliding-a-PHP-array.html:*before patched:
Inserting 65536 evil elements took 162.65940284729 seconds
Inserting 65536 good elements took 0.075557947158813 seconds*after patched:
Inserting 65536 evil elements took 0.074128866195679 seconds
Inserting 65536 good elements took 0.091044902801514 secondswhat do you think ?
At least one problem with your patch is that it uses crypto safe
random numbers. The problem with that is that the very frequent random
number fetches could deplete the entropy pool and thus make
/dev/urandom (and probably the Windows RNG too) block. So you would
again have a DOS vulnerability (just create many small arrays with 16
elements so they get resized a few times). Additionally this could
also impose a security threat to other application that rely on the
entropy source.
In essence there should only be the need for one random number per
request, so it should be fine in that regard.
Nikita
--
--
Etienne Kneuss
http://www.colder.ch
Hi,
thanks to sesser, he point out that this won't work for string keys,
so, I guess, we should change the hash logic in the mean time.. I
will keep trying.
thanks
Hi,
Hi:
the origin thread is too long, so I open a new thread for this.I have made another patch try to fix this issue.
the key point is, randomizing the table size(tableMask).
instead of double the the table size in zend_hash_do_resize, I
increase the table size with a random delta ( the value now is just a
try, we can change it to a more appropriate value),
that is: new_table_size = old_table_size * 2 + random_num.then, the collision can not be predicatible, which fix the
problem, and also fixed the issue in json/soap/serialize etc.here is the patch(draft now):
https://bugs.php.net/patch-display.php?bug_id=60655&patch=rand_hash_resize.patch&revision=latestafter this fix , may slow down the php, but compared to the
security threat I thinks the cost could be ignored.for the test script list in
http://nikic.github.com/2011/12/28/Supercolliding-a-PHP-array.html:*before patched:
Inserting 65536 evil elements took 162.65940284729 seconds
Inserting 65536 good elements took 0.075557947158813 seconds*after patched:
Inserting 65536 evil elements took 0.074128866195679 seconds
Inserting 65536 good elements took 0.091044902801514 secondswhat do you think ?
At least one problem with your patch is that it uses crypto safe
random numbers. The problem with that is that the very frequent random
number fetches could deplete the entropy pool and thus make
/dev/urandom (and probably the Windows RNG too) block. So you would
again have a DOS vulnerability (just create many small arrays with 16
elements so they get resized a few times). Additionally this could
also impose a security threat to other application that rely on the
entropy source.In essence there should only be the need for one random number per
request, so it should be fine in that regard.Nikita
--
--
Etienne Kneuss
http://www.colder.ch
--
Laruence Xinchen Hui
http://www.laruence.com/
Hi:
so here is the problem, the number index collision can be fixed by
this idea (increase table size with a random delta).
now we need add the random number into DJB hash, and I am not good at math,
so Calling for help, and the random number will be stored in a
process global variable like: PHPAPI int zend_hash_random_number.
and the reason for use a process global variable are:
1. this would break the zend hash cache
2. no abi backward break ( zend_hash_func)
3. simplify ZTS protection..
any help will be appreciated.
thanks
Hi,
thanks to sesser, he point out that this won't work for string keys,so, I guess, we should change the hash logic in the mean time.. I
will keep trying.thanks
Hi,
Hi:
the origin thread is too long, so I open a new thread for this.I have made another patch try to fix this issue.
the key point is, randomizing the table size(tableMask).
instead of double the the table size in zend_hash_do_resize, I
increase the table size with a random delta ( the value now is just a
try, we can change it to a more appropriate value),
that is: new_table_size = old_table_size * 2 + random_num.then, the collision can not be predicatible, which fix the
problem, and also fixed the issue in json/soap/serialize etc.here is the patch(draft now):
https://bugs.php.net/patch-display.php?bug_id=60655&patch=rand_hash_resize.patch&revision=latestafter this fix , may slow down the php, but compared to the
security threat I thinks the cost could be ignored.for the test script list in
http://nikic.github.com/2011/12/28/Supercolliding-a-PHP-array.html:*before patched:
Inserting 65536 evil elements took 162.65940284729 seconds
Inserting 65536 good elements took 0.075557947158813 seconds*after patched:
Inserting 65536 evil elements took 0.074128866195679 seconds
Inserting 65536 good elements took 0.091044902801514 secondswhat do you think ?
At least one problem with your patch is that it uses crypto safe
random numbers. The problem with that is that the very frequent random
number fetches could deplete the entropy pool and thus make
/dev/urandom (and probably the Windows RNG too) block. So you would
again have a DOS vulnerability (just create many small arrays with 16
elements so they get resized a few times). Additionally this could
also impose a security threat to other application that rely on the
entropy source.In essence there should only be the need for one random number per
request, so it should be fine in that regard.Nikita
--
--
Etienne Kneuss
http://www.colder.ch--
Laruence Xinchen Hui
http://www.laruence.com/
--
Laruence Xinchen Hui
http://www.laruence.com/
Hi:
so here is the problem, the number index collision can be fixed by
this idea (increase table size with a random delta).now we need add the random number into DJB hash, and I am not good at math,
so Calling for help, and the random number will be stored in a
process global variable like: PHPAPI int zend_hash_random_number.and the reason for use a process global variable are:
1. this would break the zend hash cache
2. no abi backward break ( zend_hash_func)
3. simplify ZTS protection..
A problem with a process global variable arises when the PHP process
is kept alive between requests (e.g. fcgi). In that case the random
value will stay the same between all requests and could be
brute-forced. Not sure whether this is an issue in reality (e.g. what
is the range of the random number?)
Nikita