Hash collision security issue

[christian.heimes]

http://bugs.python.org/review/13703/diff/3932/12992
File Python/random.c (right):

http://bugs.python.org/review/13703/diff/3932/12992#newcode47
Python/random.c:47: return length;
length isn't defined, how about "return size;"?

[Z. Jędrzejewski-Szmek]

Some small comments.

http://bugs.python.org/review/13703/diff/3988/13266
File Include/pythonrun.h (right):

http://bugs.python.org/review/13703/diff/3988/13266#newcode250
Include/pythonrun.h:250: PyAPI_FUNC(int PyOS_URandom) (void *buffer, Py_ssize_t
size);
I think this should read:
PyAPI_FUNC(int) PyOS_URandom(void*, Py_ssize_t);

http://bugs.python.org/review/13703/diff/3988/13267
File Include/unicodeobject.h (right):

http://bugs.python.org/review/13703/diff/3988/13267#newcode384
Include/unicodeobject.h:384: details:
http://www.ocert.org/advisories/ocert-2011-003.html */
This comment talks about doing stuff (adding bytes), but this is just a data
structure. Maybe this comment should go next to the function that actually uses
this, and here "prefix" and "suffix" should be explained.

Also "adding" should be "xored at the beggining, xored at the end", or something
like that.

http://bugs.python.org/review/13703/diff/3988/13282
File Python/random.c (right):

http://bugs.python.org/review/13703/diff/3988/13282#newcode84
Python/random.c:84: Py_FatalError("Fail to initialized the randomized hash "
grammar: Failed to initialize...

http://bugs.python.org/review/13703/diff/3988/13282#newcode110
Python/random.c:110: Py_FatalError("Fail to open /dev/urandom");
grammar: Failed...

http://bugs.python.org/review/13703/diff/3988/13282#newcode126
Python/random.c:126: "Fail to read %zi bytes from /dev/urandom",
grammar: Failed...
(and everywhere else)

[gregory.p.smith]

I think what you've done in issue 13704 is better than this change.

[gregory.p.smith]

I still like what you've done in http://bugs.python.org/review/13704/show better
than what you have done in this change.

The XOR of the random "suffix" value to the hash is unnecessary.  It doesn't
change anything as it does not cause the final hash value to change in a
non-deterministic manner.  Changing the seed with the "prefix" as you call it
here (and which is all you do in 13704) is fine.

http://bugs.python.org/review/13703/diff/4016/13392
File Objects/unicodeobject.c (right):

http://bugs.python.org/review/13703/diff/4016/13392#newcode11214
Objects/unicodeobject.c:11214: /* Issue #13703: add 2 x sizeof(Py_hash_t) random
bytes (prefix and suffix)
Why are you only doing this for Unicode?  bytes needs protecting as well.

[loewis]

http://bugs.python.org/review/13703/diff/4069/13656
File Makefile.pre.in (right):

http://bugs.python.org/review/13703/diff/4069/13656#newcode715
Makefile.pre.in:715: test:		all platform
There should be a test target enabling the randomized hash. It might be useful
to enable it by default for test and buildbottest.

http://bugs.python.org/review/13703/diff/4069/13659
File Modules/posixmodule.c (left):

http://bugs.python.org/review/13703/diff/4069/13659#oldcode7058
Modules/posixmodule.c:7058: #ifdef __VMS
It seems that the __VMS case is lost in the transformation to the new code. For
compatibility, it should be preserved.

[Benjamin Peterson]

All doc problems I think.

http://bugs.python.org/review/13703/diff/4129/14145
File Doc/using/cmdline.rst (right):

http://bugs.python.org/review/13703/diff/4129/14145#newcode220
Doc/using/cmdline.rst:220: Turn on "hash randomization, so that the
:meth:`__hash__` values of str,
Stray quote.

http://bugs.python.org/review/13703/diff/4129/14145#newcode221
Doc/using/cmdline.rst:221: bytes and datetime objects are "salted" with an
unpredictable random value.
Comma after bytes.

http://bugs.python.org/review/13703/diff/4129/14145#newcode233
Doc/using/cmdline.rst:233: Changing hash values affects the order in which keys
are retrieved from
"retrieved"? Explaning iteration order is probably better.

http://bugs.python.org/review/13703/diff/4129/14145#newcode474
Doc/using/cmdline.rst:474: Its purpose is for use in selftests for the
interpreter.
Or anyone who wants repeatable hashing?

http://bugs.python.org/review/13703/diff/4129/14145#newcode477
Doc/using/cmdline.rst:477: the value 0 overrides the other setting, disabling
the hash random salt.
Explicitly say what the other setting is.

http://bugs.python.org/review/13703/diff/4129/14157
File Misc/python.man (right):

http://bugs.python.org/review/13703/diff/4129/14157#newcode421
Misc/python.man:421: .IP PYTHONHASHRANDOMIZATION
What about the other envvar?

http://bugs.python.org/review/13703/diff/4129/14159
File Modules/main.c (right):

http://bugs.python.org/review/13703/diff/4129/14159#newcode106
Modules/main.c:106: PYTHONHASHRANDOMIZATION : make hash() values of various
types be unpredictable\n\
And the other envvar?

[gregory.p.smith]

http://bugs.python.org/review/13703/diff/4172/14373
File Doc/library/sys.rst (right):

http://bugs.python.org/review/13703/diff/4172/14373#newcode223
Doc/library/sys.rst:223: :const:`hash_randomization`   :option:`-R`
mention the 3.1.X version this was added in.

http://bugs.python.org/review/13703/diff/4172/14375
File Doc/using/cmdline.rst (right):

http://bugs.python.org/review/13703/diff/4172/14375#newcode237
Doc/using/cmdline.rst:237: the randomization is disabled by default.
add a versionadded: 3.1.X annotation.

Also mention that the default may change in 3.3.

http://bugs.python.org/review/13703/diff/4172/14375#newcode462
Doc/using/cmdline.rst:462: .. envvar:: PYTHONHASHRANDOMIZATION
similarly, add versionadded annotatations for the env vars.

http://bugs.python.org/review/13703/diff/4172/14389
File Modules/main.c (right):

http://bugs.python.org/review/13703/diff/4172/14389#newcode113
Modules/main.c:113: If PYTHONHASHSEED is set, it is used as a fixed seed for\n\
no need to re-state the environment variable name here.

http://bugs.python.org/review/13703/diff/4172/14389#newcode114
Modules/main.c:114: generating the hash() of the types covered by the hash
randomization\n\
line length.  this help text even wraps.  but in general you have some source
code lines longer than 80 here above and below as well in this text.

use a narrower wrap margin so that it all fits even in the code.

http://bugs.python.org/review/13703/diff/4172/14389#newcode120
Modules/main.c:120: It should be a decimal number in the range [0;
4294967295].\n\
replace should with must

http://bugs.python.org/review/13703/diff/4172/14390
File Modules/posixmodule.c (right):

http://bugs.python.org/review/13703/diff/4172/14390#newcode6984
Modules/posixmodule.c:6984: Return n pseudo-random bytes.");
Why does this docstring change.  isn't this still "suitable for cryptographic
use"?

http://bugs.python.org/review/13703/diff/4172/14391
File Objects/bytesobject.c (right):

http://bugs.python.org/review/13703/diff/4172/14391#newcode902
Objects/bytesobject.c:902: if (len == 0) {
why is it important for '' to hash to 0?  if it actually is, add a comment
stating why.  otherwise don't add this special case.

http://bugs.python.org/review/13703/diff/4172/14393
File Objects/unicodeobject.c (right):

http://bugs.python.org/review/13703/diff/4172/14393#newcode7347
Objects/unicodeobject.c:7347: if (len == 0) {
same comment as in bytesobject.c

[gregory.p.smith]

http://bugs.python.org/review/13703/diff/4172/14396
File Python/random.c (right):

http://bugs.python.org/review/13703/diff/4172/14396#newcode277
Python/random.c:277: "in range [0; 4294967295]");
nit picking here, i think this is fine as is but I do notice a discrepancy:

We are artificially limiting the user-supplied seed to 32 bits here.  Yet when
we choose one ourselves using urandom it is either 64-bits (on platforms where
sizeof(long) == 4) or 128-bits (platforms where sizeof(long) == 8).

Shouldn't we allow the environment variable to supply an equivalent amount of
randomness or at least allow them to supply up to 64-bits?

[gregory.p.smith]

looking good.  I do agree with Marc-Andre Lemburg's comment in the bug based on
previous discussion:  Lets use a single environment variable.  No need for two
variables.

PYTHONHASHSEED=random   is used to enable the new behavior.
PYTHONHASHSEED=0  explicitly enables the old behavior.
PYTHONHASHSEED=n  sets the seed to int(n).

http://bugs.python.org/review/13703/diff/4192/14582
File Modules/main.c (right):

http://bugs.python.org/review/13703/diff/4192/14582#newcode117
Modules/main.c:117: It should be a decimal number in the range [0; 4294967295].
Specifying\n\
nit pick, use "must" instead of should.  use a , in the range instead of a ;. 
(honestly this doesn't matter much, it is clear either way)

[gregory.p.smith]

http://bugs.python.org/review/13703/diff/4191/14547
File Lib/test/test_cmd_line.py (right):

http://bugs.python.org/review/13703/diff/4191/14547#newcode107
Lib/test/test_cmd_line.py:107: # Verify that -R enables hash randomization:
To be sure it is testing the intended behavior, this test should be sure to
explicitly unset the hash randomization related environment variable(s) when
spawning the python subprocesses.

Otherwise if a test suite is run with the randomization enabled via the
environment variable this isn't actually guaranteed to test that -R did
anything.

[AntoinePitrou]

http://bugs.python.org/review/13703/diff/4192/14568
File Doc/using/cmdline.rst (right):

http://bugs.python.org/review/13703/diff/4192/14568#newcode227
Doc/using/cmdline.rst:227: of a dict lookup, O(n^2) complexity.  See:
The worst case performance of a dict lookup is O(n). O(n^2) is the worst case
performance of dict construction.

http://bugs.python.org/review/13703/diff/4192/14575
File Lib/test/test_hash.py (right):

http://bugs.python.org/review/13703/diff/4192/14575#newcode14
Lib/test/test_hash.py:14: IS_64BIT = (struct.calcsize('l') == 8)
That's a bit misleading. This will get you the size of a C long, not whether the
machine is 64-bit. Under Windows for Python 3.1 it still does the right thing
(because hash() returns a C long). However, starting from 3.2, hash() returns a
Py_hash_t, which is 64-bit under 64-bit Windows: you'll have to use sys.maxsize.

http://bugs.python.org/review/13703/diff/4192/14575#newcode138
Lib/test/test_hash.py:138: env['PYTHONHASHRANDOMIZATION'] = str(randomization)
If it's None, you should remove it from the environment, no?

http://bugs.python.org/review/13703/diff/4192/14589
File Python/random.c (right):

http://bugs.python.org/review/13703/diff/4192/14589#newcode236
Python/random.c:236: return dev_urandom_python((char*)buffer, size);
No VMS here?

http://bugs.python.org/review/13703/diff/4192/14590
File Python/sysmodule.c (right):

http://bugs.python.org/review/13703/diff/4192/14590#newcode1138
Python/sysmodule.c:1138: 13
If you change this value, it threatens to break compatibility (think someone
using tuple-unpacking on sys.flags). I think we should only change it in 3.3.