Make it possible to disable and control hash key traversal randomization

Adds support for PERL_PERTURB_KEYS environment variable, which in turn allows one to control
the level of randomization applied to keys() and friends.

When PERL_PERTURB_KEYS is 0 we will not randomize key order at all. The
chance that keys() changes due to an insert will be the same as in
previous perls, basically only when the bucket size is changed.

When PERL_PERTURB_KEYS is 1 we will randomize keys in a non repeatedable
way. The chance that keys() changes due to an insert will be very high.
This is the most secure and default mode.

When PERL_PERTURB_KEYS is 2 we will randomize keys in a repeatedable way.
Repititive runs of the same program should produce the same output every
time. The chance that keys changes due to an insert will be very high.

This patch also makes PERL_HASH_SEED imply a non-default
PERL_PERTURB_KEYS setting. Setting PERL_HASH_SEED=0 (exactly one 0) implies
PERL_PERTURB_KEYS=0 (hash key randomization disabled), settng PERL_HASH_SEED
to any other value, implies PERL_PERTURB_KEYS=2 (deterministic/repeatable
hash key randomization). Specifying PERL_PERTURB_KEYS explicitly to a
different level overrides this behavior.

Includes changes to allow one to compile out various aspects of the
patch. One can compile such that PERL_PERTURB_KEYS is not respected, or
can compile without hash key traversal randomization at all. Note that
support for these modes is incomplete, and currently a few tests will
fail.

Also includes a new subroutine in Hash::Util::hash_traversal_mask()
which can be used to ensure a given hash produces a predictable key
order (assuming the same hash seed is in effect). This sub acts as a
getter and a setter.

NOTE - this patch lacks tests, but I lack tuits to get them done quickly,
so I am pushing this with the hope that others can add them afterwards.

1 files changed, 65 insertions, 43 deletions

diff --git a/pod/perlsec.pod b/pod/perlsec.pod
index eb079a3b24..98fa513490 100644
--- a/pod/perlsec.pod
+++ b/pod/perlsec.pod
@@ -454,49 +454,71 @@ I<Denial of Service> (DoS) attacks.
 
 =item *
 
-Hash Function - the algorithm used to "order" hash elements has been
-changed several times during the development of Perl, mainly to be
-reasonably fast.  In Perl 5.8.1 also the security aspect was taken
-into account.
-
-In Perls before 5.8.1 one could rather easily generate data that as
-hash keys would cause Perl to consume large amounts of time because
-internal structure of hashes would badly degenerate.  In Perl 5.8.1
-the hash function is randomly perturbed by a pseudorandom seed which
-makes generating such naughty hash keys harder.
-See L<perlrun/PERL_HASH_SEED> for more information.
-
-In Perl 5.8.1 the random perturbation was done by default, but as of
-5.8.2 it is only used on individual hashes if the internals detect the
-insertion of pathological data. If one wants for some reason emulate the
-old behaviour (and expose oneself to DoS attacks) one can set the
-environment variable PERL_HASH_SEED to zero to disable the protection
-(or any other integer to force a known perturbation, rather than random). 
-One possible reason for wanting to emulate the old behaviour is that in the
-new behaviour consecutive runs of Perl will order hash keys differently,
-which may confuse some applications (like Data::Dumper: the outputs of two
-different runs are no longer identical).
-
-In Perl 5.18.0 the rehash mechanism has been removed, and replaced by
-true randomization similar to that used in 5.8.1. Additionally measures
-have been taken to ensure that C<keys>, C<values>, and C<each> return items
-in a per-hash randomized order. Modifying a hash by insertion is
-guaranteed to change the iteration order. Combined with a hardened
-hash function we believe that discovery attacks on the hash seed
-are very unlikely.  This traversal randomization cannot be disabled,
-and is unaffected by the value of PERL_HASH_SEED.
-
-In addition to these measures, as of Perl 5.18.0 the source code includes
-multiple hash algorithms to choose from.  While we believe that the
-default perl hash is robust to attack we have included the hash function
-Siphash as a fallback option; at the time of release of Perl 5.18.0 Siphash
-is believed to be of cryptographic strength.  This is not the default as it
-is much slower than the default hash.
-
-B<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.
+Hash Algorithm - Hash algorithms like the one used in Perl are well
+known to be vulnerable to collision attacks on their hash function.
+Such attacks involve constructing a set of keys which collide into
+the same bucket producing inefficient behavior. Such attacks often
+depend on discovering the seed of the hash function used to map the
+keys to buckets which is then used to brute force an key set which
+can be used to mount a denial of service attack. In Perl 5.8.1 changes
+were introduced to harden Perl to such attacks, and then later in
+Perl 5.18.0 these features were enhanced and additional protections
+added.
+
+As of Perl 5.18.0 the following measures are in place to mitigate attacks:
+
+=over 4
+
+=item Hash Seed Randomization
+
+In order to make it impossible to know what seed to generate an attack
+key set for this seed is randomly initialzed at process start, but this
+may be overriden by using the PERL_HASH_SEED envrionment variable, see
+L<perlrun/PERL_HASH_SEED>. This controls how items are actually stored,
+not how they are presented via C<keys>, C<values> and C<each>.
+
+=item Hash Traversal Randomization
+
+Independent of which seed has been used in the hash function, C<keys>,
+C<values>, and C<each> return items in a per-hash randomized order.
+Modifying a hash by insertion will change the iteration order of that hash.
+This behavior can be overriden by using C<hash_traversal_mask()> from
+L<Hash::Util> or by using the PERL_PERTURB_KEYS environment variable,
+see L<perlrun/PERL_PERTURB_KEYS>. Note that this feature controls the
+"visible" order of the keys, and not the actual order they are stored in.
+
+=item Bucket Order Perturbance
+
+When items collide into a given bucket the order they are stored in
+the chain is no longer predictable with the intention of making
+it harder to observe a collisions. This behavior can be overriden by using
+the PERL_PERTURB_KEYS environment variable, see L<perlrun/PERL_PERTURB_KEYS>.
+
+=item New Default Hash Function
+
+The default hash function has been modified with the intention of making
+it harder to infer the hash seed.
+
+=item Alternative Hash Functions
+
+The source code includes multiple hash algorithms to choose from.  While we
+believe that the default perl hash is robust to attack we have included the
+hash function Siphash as a fallback option; at the time of release of
+Perl 5.18.0 Siphash is believed to be of cryptographic strength.  This is
+not the default as it is much slower than the default hash.
+
+=back
+
+Without compiling a special Perl there is no way to get the exact same
+behavior of any versions prior to Perl 5.18.0. The closest one can get
+is by setting PERL_PERTURB_KEYS to 0 and setting the PERL_HASH_SEED
+to a known value.
+
+B<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 and the history of changes made
+to the hash over its lifetime.
 
 Also note that while the order of the hash elements might be
 randomised, this "pseudoordering" should B<not> be used for