On Thu, Jan 5, 2012 at 4:11 PM, Laruence <larue...@php.net> wrote: > On Thu, Jan 5, 2012 at 4:04 PM, Laruence <larue...@php.net> wrote: >> On Thu, Jan 5, 2012 at 3:57 PM, Rasmus Lerdorf <ras...@lerdorf.com> wrote: >>> On 01/04/2012 11:49 PM, Laruence wrote: >>>> Hi: >>>> there is one way maybe is a good try. >>>> >>>> when resize hashtable, we don't just dobule the size, instead, we >>>> increase the hashtable size with a random delta >>>> >>>> what do you think? >>> >>> Sorry, you lost me. How does that help? The problem is when we collide >>> on a single hash key the resulting linked list traversion gets longer >>> and longer as more colliding keys are added to that hashtable. Whether >>> you double the size or grow it by some other factor doesn't change this. >> No, No, >> >> if we increase the table size with a random delta(the nTableMask will >> also be random), then the collision will not be predictable. > > I have made a patch, plz try this mechanism, > https://bugs.php.net/patch-display.php?bug_id=60655&patch=rand_hash_resize.patch&revision=latest > > I have tested , that works. > > and the patch is still a rough draft, so maybe some compile warnings.. the key point is, increase the table size in a random delta (2 * size + (random_num & size_mask));
in the same time use mod(%) instead of and(&) while doing the index mapping. then the attacker will be not able to predicate the collision ;) thanks. > > thanks >> >> thanks >> >>> >>> -Rasmus >>> >> >> >> >> -- >> Laruence Xinchen Hui >> http://www.laruence.com/ > > > > -- > Laruence Xinchen Hui > http://www.laruence.com/ -- Laruence Xinchen Hui http://www.laruence.com/ -- PHP Internals - PHP Runtime Development Mailing List To unsubscribe, visit: http://www.php.net/unsub.php
