[prev in list] [next in list] [prev in thread] [next in thread]
List: perl5-changes
Subject: [perl.git] branch yves/hv_h_split, created. v5.17.9-201-g92310de
From: "Yves Orton" <demerphq () gmail ! com>
Date: 2013-03-18 22:52:53
Message-ID: E1UHivF-0001z6-4s () camel ! ams6 ! corp ! booking ! com
[Download RAW message or body]
In perl.git, the branch yves/hv_h_split has been created
<http://perl5.git.perl.org/perl.git/commitdiff/92310deb223031d0e2c8768fae2bec1d1c32c5dd?hp=0000000000000000000000000000000000000000>
at 92310deb223031d0e2c8768fae2bec1d1c32c5dd (commit)
- Log -----------------------------------------------------------------
commit 92310deb223031d0e2c8768fae2bec1d1c32c5dd
Author: Yves Orton <demerphq@gmail.com>
Date: Mon Mar 18 00:28:03 2013 +0100
detect each() after insert and produce warnings when we do
Inserting into a hash that is being traversed with each()
has always produced undefined behavior. With hash traversal
randomization this is more pronounced, and at the same
time relatively easy to spot. At the cost of an extra U32
in the xpvhv_aux structure we can detect that the xhv_rand
has changed and then produce a warning if it has.
It was suggested on IRC that this should produce a fatal
error, but I couldn't see a clean way to manage that with
"strict", it was much easier to create a "severe" (internal)
warning, which is enabled by default but suppressible with
C<no warnings "internal";> if people /really/ wanted.
M hv.c
M hv.h
M pod/perldiag.pod
M t/op/each.t
commit cc354e08443a203c79795f63077b27bbb3090e41
Author: Yves Orton <demerphq@gmail.com>
Date: Sun Mar 17 20:48:45 2013 +0100
ensure that inserting into a hash causes its hash iteration order to change
This serves two functions, it makes it harder for an attacker
to learn useful information by viewing the output of keys(),
and it makes "insert during traversal" errors much easier to
spot, as they will almost always produce degenerate behavior.
M hv.c
commit 465192b9d6eedd9fd4874982498b68e9cad251e2
Author: Yves Orton <demerphq@gmail.com>
Date: Sun Mar 17 20:33:19 2013 +0100
perturb insertion order and update xhv_rand during insertion and S_hsplit()
When inserting into a hash results in a collision the order of the items
in the bucket chain is predictable (FILO), and can be used to determine
that a collision has occured.
When a hash is too small for the number of items it holds we double
its size and remap the items as required. During this process the
keys in a bucket will reverse order, and exposes information to an
attacker that a collision has occured.
We therefore use the PL_hash_rand_bits() and the S_ptr_hash()
infrastructure to randomly "perturb" the order that colliding
items are inserted into the bucket chain. During insertion and
mapping instead of doing a simple "insert to top" we check the low
bit of PL_hash_rand_bits() and depending if it is set or not we
insert at the top of the chain, otherwise second from the top.
The end result being that the order in a bucket is less predictable,
which should make it harder for an attacker to spot a collision.
Every insert (via hv_common), and bucket doubling (via hsplit())
results in us updating PL_hash_rand_bits() using "randomish" data
like the hashed bucket address, the hash of the inserted item, and
the address of the inserted item.
This also updates the xhv_rand() of the hash, if there is one, during
S_hsplit() so that the iteration order changes when S_hsplit() is
called. This also is intended to make it harder for an attacker to
aquire information about collisions.
M hv.c
commit 8785c0241c6765557a64686a77b3b4d8dc96d6a4
Author: Yves Orton <demerphq@gmail.com>
Date: Sun Mar 17 20:19:09 2013 +0100
Harden hashes against hash seed discovery by randomizing hash iteration
Adds:
S_ptr_hash() - A new static function in hv.c which can be used to
hash a pointer or integer.
PL_hash_rand_bits - A new interpreter variable used as a cheap
provider of "semi-random" state for use by the hash infrastructure.
xpvhv_aux.xhv_rand - Used as a mask which is xored against the
xpvhv_aux.riter during iteration to randomize the order the actual
buckets are visited.
PL_hash_rand_bits is initialized as interpreter start from the random
hash seed, and then modified by "mixing in" the result of ptr_hash()
on the bucket array pointer in the hv (HvARRAY(hv)) every time
hv_auxinit() allocates a new iterator structure.
The net result is that every hash has its own iteration order, which
should make it much more difficult to determine what the current hash
seed is.
This required some test to be restructured, as they tested for something
that was not necessarily true, we never guaranteed that two hashes with
the same keys would produce the same key order, we merely promised that
using keys(), values(), or each() on the same hash, without any
insertions in between, would produce the same order of visiting the
key/values.
M embed.fnc
M embed.h
M embedvar.h
M hv.c
M hv.h
M intrpvar.h
M proto.h
M t/op/smartkve.t
M util.c
commit 1657f27294882e819c374d8a1206d468996a2a6a
Author: Yves Orton <demerphq@gmail.com>
Date: Sun Mar 17 15:20:20 2013 +0100
rework ROTL definitions (and add ROTL_UV)
M hv_func.h
commit de7c0235118cca6e3ebc4480b00c30ccc99fd5cf
Author: Yves Orton <demerphq@gmail.com>
Date: Tue Feb 12 05:06:48 2013 +0100
default to PERL_FUNC_ONE_AT_A_TIME_HARD for all builds
For testing, but maybe for ever
M hv_func.h
commit 252f9733cc38e93e8cb3dff7a42b08dd6a0408ae
Author: Yves Orton <demerphq@gmail.com>
Date: Tue Dec 11 08:50:58 2012 +0100
silence signed mistmatch in comparison warning in Murmurhash
as far as I can tell 'i' can only be positive here.
M hv_func.h
commit 987459b53d9bf03a0c6e1a0be3d3b8361af718a5
Author: Yves Orton <demerphq@gmail.com>
Date: Mon Dec 10 08:36:43 2012 +0100
add a hardened one-at-a-time hash variant
Mix in additional randomness into the final value.
M hv_func.h
commit 8c5f6c1ab88fce02a47ae1fc5aee8b1166db2ba0
Author: Yves Orton <demerphq@gmail.com>
Date: Sat Dec 8 16:24:06 2012 +0100
Split out hash functions into new file and turn into inline static functions
This includes various tweaks related to building SipHash and other
cleanup.
M Cross/Makefile-cross-SH
M MANIFEST
M Makefile.SH
M Makefile.micro
M NetWare/Makefile
M configpm
M hv.h
A hv_func.h
M win32/Makefile
M win32/Makefile.ce
commit 33afd9f40a946dfe3e53941750c31ba02a7c3acc
Author: Yves Orton <demerphq@gmail.com>
Date: Tue Dec 11 23:46:37 2012 +0100
add a "hash quality score" to Hash::Util::bucket_stats()
M ext/Hash-Util/lib/Hash/Util.pm
commit c5ca3eb869902fda05647fc610e3a6fd5001326a
Author: Yves Orton <demerphq@gmail.com>
Date: Mon Dec 10 09:43:59 2012 +0100
update ExtUtils-MakeMaker to github v6.65_01
Perl core specific highlights:
* Fix hash related issues for 5.18.
* Do not hard code the list of perl header files - discover them from disk \
instead
* Don't need completely different include file collector on VMS.
M MANIFEST
M cpan/ExtUtils-MakeMaker/Changes
M cpan/ExtUtils-MakeMaker/MANIFEST
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/Command/MM.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/Liblist.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/Liblist/Kid.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_AIX.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_Any.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_BeOS.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_Cygwin.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_DOS.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_Darwin.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_MacOS.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_NW5.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_OS2.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_QNX.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_UWIN.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_Unix.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_VMS.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_VOS.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_Win32.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MM_Win95.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MY.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MakeMaker.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MakeMaker/Config.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MakeMaker/FAQ.pod
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/MakeMaker/Tutorial.pod
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/Mkbootstrap.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/Mksymlists.pm
M cpan/ExtUtils-MakeMaker/lib/ExtUtils/testlib.pm
A cpan/ExtUtils-MakeMaker/t/Liblist_Kid.t
M cpan/ExtUtils-MakeMaker/t/basic.t
M cpan/ExtUtils-MakeMaker/t/pod2man.t
-----------------------------------------------------------------------
--
Perl5 Master Repository
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic