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

Re: Eliminating the "rehash" mechanism for 5.18

Thread Previous | Thread Next
October 31, 2012 03:05
Re: Eliminating the "rehash" mechanism for 5.18
Message ID:
On 31 October 2012 10:24, Ed Avis <> wrote:
> A 64-bit random seed has 2^64 possible values.  There are about 3*(2**64) ways
> to shuffle 21 elements.  So as a rough estimate, if you can insert 21 elements
> into a freshly created hash and observe the order of the hash keys, you should
> be able to determine the random seed most of the time.  This would not be noticed
> as a denial-of-service attack.
> However, once you have your 21 elements in order, you still have to grind through
> all possible random seeds to find which one gives that ordering.  That would take
> about five million years on a typical desktop CPU.  Somebody clever might find
> an analytic solution to determine the random seed from the hash ordering, but
> such minds are probably all busy working for the NSA on more important problems.

This still feels optimistic. The ordering of the 21 elements wont be
based on the full hash value but rather the right 5 bits of the hash
value. So for any given bucket assignment there will be 2**27 possible
hash values that could have resulted in that bucket. Which means IMO
that there will be a lot of seeds that generate the order you see.

So once you have that list of seeds you would then repeatedly add a
new string, filter out the seeds that would produce a different order,
and i guess eventually you would be down to one seed.

It would be faster to use as large a list as possible and double the
size of the list each time, as that way you get to "see" more bits of
the hash values your strings generate.


perl -Mre=debug -e "/just|another|perl|hacker/"

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