I've noticed that the same hash will always be ordered the same way, each and every time, that it's used

       Hash Randomisation

       Mainly due to security reasons, the "random ordering" of
       hashes has been made even more random.  Previously while
       the order of hash elements from keys(), values(), and
       each() was essentially random, it was still repeatable.
       Now, however, the order varies between different runs of
       Perl.

       Perl has never guaranteed any ordering of the hash keys,
       and the ordering has already changed several times during
       the lifetime of Perl 5.  Also, the ordering of hash keys
       has always been, and continues to be, affected by the
       insertion order.

       The added randomness may affect applications.

       One possible scenario is when output of an application has
       included hash data.  For example, if you have used the
       Data::Dumper module to dump data into different files, and
       then compared the files to see whether the data has
       changed, now you will have false positives since the order
       in which hashes are dumped will vary.  In general the cure
       is to sort the keys (or the values); in particular for
       Data::Dumper to use the "Sortkeys" option.  If some par­
       ticular order is really important, use tied hashes: for
       example the Tie::IxHash module which by default preserves
       the order in which the hash elements were added.

       More subtle problem is reliance on the order of "global
       destruction".  That is what happens at the end of execu­
       tion: Perl destroys all data structures, including user
       data.  If your destructors (the DESTROY subroutines) have
       assumed any particular ordering to the global destruction,
       there might be problems ahead.  For example, in a destruc­
       tor of one object you cannot assume that objects of any
       other class are still available, unless you hold a refer­
       ence to them.  If the environment variable
       PERL_DESTRUCT_LEVEL is set to a non-zero value, or if Perl
       is exiting a spawned thread, it will also destruct the
       ordinary references and the symbol tables that are no
       longer in use.  You can't call a class method or an ordi­
       nary function on a class that has been collected that way.

       The hash randomisation is certain to reveal hidden assump­
       tions about some particular ordering of hash elements, and
       outright bugs: it revealed a few bugs in the Perl core and
       core modules.

       To disable the hash randomisation in runtime, set the
       environment variable PERL_HASH_SEED to 0 (zero) before
       running Perl (for more information see "PERL_HASH_SEED" in
       perlrun), or to disable the feature completely in compile
       time, compile with "-DNO_HASH_SEED" (see INSTALL).

       See "Algorithmic Complexity Attacks" in perlsec for the
       original rationale behind this change.
[download]

Abigail

However, wait until you install 5.8.1. Much less predictable.

After you have read that, a key detail that I glossed over there. A good hashing algorithm takes a lot of normal strings and should scatter them well among buckets, hence it tries to make things look pretty random. (While really being deterministic.)

What everyone else is referring to is that the hashing function that Perl uses is, as of 5.8.1, going to be different every time you start Perl. Previously it only varied from one version of Perl to the next.

Which says to me, if you want an order, establish it for yourself.

As for how Perl allocates memory, VERY WELL! And it doesn't have too many leaks either.

jdtoronto

What merlyn said is right. Perl doesn't order hash keys in order of creation, but that doesn't mean they're ordered randomly....

I have found a lack of available entropy in the system to be a major bottleneck in output of running programs at times. Obviously if randomness is being supplied by /dev/random then might not a race condition be possible in the case that you are storing random numbers in a hash while the insertion or bucket redistribution operations themselves require random numbers to operate? Is /dev/random actually used in hash mechanics now?

I am not trying to be facetious. Some operating systems really will have a problem with operations which require a lot of random numbers. I saw a visible problem with console display of random numbers. Try this (just tried on RedHat 9 in an xterm):

cat /dev/random | hexdump

After a little bit (1000 lines maybe) the output will stop and only restart when you move the mouse or hit a key. Kill it with ctrl-c and subsequent runs will only show one or two lines before waiting for input again. After a little bit it won't even output a single line until you let it sit by itself for a minute (maybe due to kernel's tcp randomization code?? anyway.) If /dev/random is not being used then the bucket order is just being hashed again, which is more obfuscation than real security I'd think. I tried to mix hash operations with reading from the above line (followed by a pipe) however it looks like it will continue to hang until I let it rest for a minute or so.

perl -e 'open (IN,"cat /dev/random|hexdump|"); while (<IN>) {$h{$_}=$_; print $c++ . " ";} close (<IN>);'

Considering I was still able to do hash operations after horribly exhausting my system's entropy I would say the security gained is fragile as it is based on a hash function and not an entropy source, therefore the order is not random at all, but calculable based on the hash to be reordered.

So is the "increased randomness" of hash order in newer perls mainly just meant as a reminder not to depend on the order of the hash, or is it something real which could be made to draw from an authentic entropy source if you really wanted to? Another use for /dev/cdrom ..

Exhausting entropy like that is a serious problem for some applications. However, I doubt it's a big deal for Perl.

The problem the increased hash randomness was trying to solve was that certain well-crafted inputs would expand the internal data structures, thus consuming a lot more resources and becoming a potential DoS attack (the attack can be generalized to be used on many languages and algorithms, not just Perl's hashes). By putting a little randomization in the hash, it becomes much harder for an attacker to predict how the datastructure will expand.

The random number generator used need not be from an extremely high quality source. Just enough that an attacker won't be able to predict the hash seeds. It would be pretty easy to foil a remote attacker this way, but a bit harder for a local attacker, depending on their system priviliges.

----
I wanted to explore how Perl's closures can be manipulated, and ended up creating an object system by accident.
-- Schemer

: () { :|:& };:

Note: All code is untested, unless otherwise stated

Thank you very much for your illumination! I had no entropy problems just now creating 100,000 small hashes so I guess the seed is being chosen without using /dev/random at all. Thanks again. --Matt

As many other posters pointed out, as of perl 5.8.1, the hash order will no longer be the same between runs. Before that, you could assume that the order would be the same on the same version of perl and get away with it.

So if you're depending on keys %hash to have consistant output, you better have a sort in front of it.

----
I wanted to explore how Perl's closures can be manipulated, and ended up creating an object system by accident.
-- Schemer

: () { :|:& };:

Note: All code is untested, unless otherwise stated

my %hashA;
$hashA{123456} = 1;
$hashA{'Roger and Albert'} = 1;
$hashA{'Roger'} = 1;
$hashA{'456789'} = 1;

print "HASH A\n------\n";
print "$_\n" for keys %hashA;

my %hashB;
$hashB{'Roger'} = 1;
$hashB{123456} = 1;
$hashB{'Roger and Albert'} = 1;
$hashB{456789} = 1;

print "\nHASH B\n------\n";
print "$_\n" for keys %hashB;
[download]

HASH A
------
456789
123456
Roger and Albert
Roger

HASH B
------
456789
123456
Roger and Albert
Roger
[download]

The random seed for the hash function is to avoid DoS attacks based on "well-crafted" data. Reducing the bias of the hash function (if there was any) or improving the performance would require a different hash algorithm.

Carelessly chosen alogorithms might be less secure against DoS attacks, be more biased, or degrade performance.

-QM
--
Quantum Mechanics: The dreams stuff is made of