develooper Front page | perl.perl5.porters | Postings from October 2012

Re: Eliminating the "rehash" mechanism for 5.18

Thread Previous | Thread Next
Ruslan Zakirov
October 29, 2012 19:59
Re: Eliminating the "rehash" mechanism for 5.18
Message ID:

I agree with proposal to randomize the primary hash seed at the beginning.

I agree that ReHASH is sub-optimal and brings too much penalty in cases
when hash access optimized with precomputed hash value.

However, read below on security considerations.

On Tue, Oct 30, 2012 at 3:23 AM, Tony Cook <> wrote:
> On Mon, Oct 29, 2012 at 06:55:21PM +0100, demerphq wrote:
>> The attack that this is intended to defuse is that where an attacker
>> constructs a series of string which are known to collide and then
>> manages to feed them to a Perl process which uses them to construct a
>> hash. All further access to the hash then becomes a search against an
>> un-ordered linked list. This attack is more than a theoretical
>> possibility because of  the fact that Perl has by default used a
>> compile time determined constant and poorly chosen hash seed for its
>> hash algorithm. Meaning that one can use a perl on one box to attack a
>> perl on another box.
> (/me puts his paranoid hat on)
> For an attack on a long lived process, if the process ever returns the
> contents of a hash in hashed order, could this be used to determine
> the process hash seed?
> If so, it could be used to perform the attack we're trying to prevent.

I think that nobody tried to analyze perl's hash function for reversibility
by feeding data and guessing hash seed from results.

With rehash it becomes much harder because you need to find a set of
keys that produce minimal number of buckets for two different random
hash seeds.

If we think about penalty then it's possible to use different hash function
for rehashed hashes that still uses precomputed hash value. Simplest
way is just reverse bits for rehashed rather than recompute. Better solution
is to randomly extend key instead of changing hash seed, so core hash
function is the same, seed is the same, but for rehashed hashes we add
random (pregenerated) N bytes to the key when we calculate hash value.
May be it's possible to store such random sequence in the hash itself, then
I think it will be impossible to attack such rehash algorithm.

Best regards, Ruslan.

Thread Previous | Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About