Re: RE: HashDos protection

On 30 November 2015 at 13:58, Pascal KISSIAN <php-mailing-list@lool.fr> wrote: > >De : Nikita Popov [mailto:nikita.ppv@gmail.com] > >Envoyé : dimanche 29 novembre 2015 12:45 > >À : Pascal KISSIAN > >Cc : PHP internals > >Objet : Re: HashDos protection > > >Collisions in DJBX33A are (integer overflow notwithstanding) completely > independent of the starting value, so randomizing it wouldn't help. If > you're interested in how DJB collisions are constructed, see > > http://www.phpinternalsbook.com/hashtables/hash_algorithm.html#hash-collisionsÑn–ø÷ > <ÊûètæL× > . > > > > Very interesting reading, thanks… > > > > > > > > >Similarly, this would not have any effect either. We reduce hashes using > an equivalent of hash % table_size, which is the same as (hash + N * > table_size) % table_size for any N. If you simply add an additional number > to it, the same relation still holds: (hash + salt) % table_size == (hash + > salt + N * table_size) % table_size, so elements that collided previously > still collide. > > > > You’re absolutely right! Just adding something results in a translation > of the hash table cell… > > Perhaps another operation could do the job? Multiply still keeps the > collision for the modulo equal to 0… perhaps add + multiply …. > > > > However, my main feeling is that "An ounce of prevention is worth a pound > of cure"… > … and my preferences will go to your second option … taking care of not > degrading performance… > > > > pk > > As for what other languages do, Python, Ruby and Perl all seem to have switched to using sipHash - maybe we should consider this too