[issue13703] Hash collision security issue

Dave Malcolm report at bugs.python.org
Sun Jan 29 00:14:28 CET 2012


Dave Malcolm <dmalcolm at redhat.com> added the comment:

On Sat, 2012-01-28 at 20:05 +0000, Benjamin Peterson wrote:
> Benjamin Peterson <benjamin at python.org> added the comment:
> 
> I think we don't need to mess with tests in 2.6/3.1, but everything should pass under 2.7 and 3.2.

New version of the patch for 3.1
  optin-hash-randomization-for-3.1-dmalcolm-2012-01-28-001.patch

This version adds a command-line flag to enable hash-randomization: -R
(given that the -E flag disables env vars and thus disabled
PYTHONHASHRANDOMIZATION). See [1] below

[Is there a convenient way to check the length of the usage messages in
Modules/main.c?  I see this comment:
   /* Long usage message, split into parts < 512 bytes */ ]

I reworded the documentation somewhat based on input from Barry and
Antoine.

Also adds a NEWS item.

Passes "make test" on this x86_64 Fedora 15 box, --with-pydebug, though
that's without randomization enabled (it just does it within individual
test cases that explicitly enable it).

No performance testing done yet (though hopefully similar to that of
Victor's patch; see msg151078)

No idea of the impact on Windows users (I don't have a windows dev box).
It still has the stuff from Victor's patch described in msg151158.

How is this looking?
Dave

[1] IRC transcript concerning "-R" follows:
<__ap__> dmalcolm: IMO it would be simpler if there was only one env var
(preferably not too clumsy to type)
<__ap__> also, despite being neither barry nor gutworth, I think the
test suite *should* pass with randomized hashes
<__ap__> :)
<dmalcolm> :)
<__ap__> also the failure you're having is a bit worrying, since
apparently it's not about dict ordering
<dmalcolm> PYTHONHASHSEED exists mostly for selftesting (also for
compat, if you absolutely need to reproduce a specific random dict
ordering)
<__ap__> ok
<__ap__> if -E suppresses hash randomization, I think we should also add
a command-line flag
<__ap__> -R seems untaken
<__ap__> also it'll make things easier for Windows users, I think

----------
Added file: http://bugs.python.org/file24353/optin-hash-randomization-for-3.1-dmalcolm-2012-01-28-001.patch

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue13703>
_______________________________________
-------------- next part --------------
diff -r 73dad4940b88 Doc/reference/datamodel.rst
--- a/Doc/reference/datamodel.rst	Fri Jan 20 11:23:02 2012 +0000
+++ b/Doc/reference/datamodel.rst	Sat Jan 28 18:05:49 2012 -0500
@@ -1265,6 +1265,8 @@
    inheritance of :meth:`__hash__` will be blocked, just as if :attr:`__hash__`
    had been explicitly set to :const:`None`.
 
+   See also the :option:`-R` command-line option.
+
 
 .. method:: object.__bool__(self)
 
diff -r 73dad4940b88 Doc/using/cmdline.rst
--- a/Doc/using/cmdline.rst	Fri Jan 20 11:23:02 2012 +0000
+++ b/Doc/using/cmdline.rst	Sat Jan 28 18:05:49 2012 -0500
@@ -21,7 +21,7 @@
 
 When invoking Python, you may specify any of these options::
 
-    python [-bBdEhiOsSuvVWx?] [-c command | -m module-name | script | - ] [args]
+    python [-bBdEhiORsSuvVWx?] [-c command | -m module-name | script | - ] [args]
 
 The most common use case is, of course, a simple invocation of a script::
 
@@ -215,6 +215,30 @@
    Discard docstrings in addition to the :option:`-O` optimizations.
 
 
+.. cmdoption:: -R
+
+   Turn on "hash randomization, so that the :meth:`__hash__` values of str,
+   bytes and datetime objects are "salted" with an unpredictable random value.
+   Although they remain constant within an individual Python process, they
+   are not predictable between repeated invocations of Python.
+
+   This is intended to provide protection against a denial-of-service
+   caused by carefully-chosen inputs that exploit the worst case performance
+   of a dict lookup, O(n^2) complexity.  See:
+
+       http://www.ocert.org/advisories/ocert-2011-003.html
+
+   for details.
+
+   Changing hash values affects the order in which keys are retrieved from
+   a dict.  Although Python has never made guarantees about this ordering
+   (and it typically varies between 32-bit and 64-bit builds), enough
+   real-world code implicitly relies on this non-guaranteed behavior that
+   the randomization is disabled by default.
+
+   See also :envvar:`PYTHONHASHRANDOMIZATION`.
+
+
 .. cmdoption:: -s
 
    Don't add user site directory to sys.path
@@ -435,6 +459,25 @@
    import of source modules.
 
 
+.. envvar:: PYTHONHASHRANDOMIZATION
+
+   If this is set to a non-empty string it is equivalent to specifying the
+   :option:`-R` option.
+
+
+.. envvar:: PYTHONHASHSEED
+
+   If this is set, it is used as a fixed seed for generating the hash() of
+   the types covered by the :option:`-R` option (or its equivalent,
+   :envvar:`PYTHONHASHRANDOMIZATION`.
+
+   It is primarily intended for use in selftests for the interpreter, but
+   may perhaps be of use for reproducing a specific dict ordering.
+
+   It should be a decimal number in the range [0; 4294967295].  Specifying
+   the value 0 overrides the other setting, disabling the hash random salt.
+
+
 .. envvar:: PYTHONIOENCODING
 
    Overrides the encoding used for stdin/stdout/stderr, in the syntax
diff -r 73dad4940b88 Include/object.h
--- a/Include/object.h	Fri Jan 20 11:23:02 2012 +0000
+++ b/Include/object.h	Sat Jan 28 18:05:49 2012 -0500
@@ -473,6 +473,12 @@
 PyAPI_FUNC(long) _Py_HashDouble(double);
 PyAPI_FUNC(long) _Py_HashPointer(void*);
 
+typedef struct {
+    long prefix;
+    long suffix;
+} _Py_HashSecret_t;
+PyAPI_DATA(_Py_HashSecret_t) _Py_HashSecret;
+
 /* Helper for passing objects to printf and the like */
 #define PyObject_REPR(obj) _PyUnicode_AsString(PyObject_Repr(obj))
 
diff -r 73dad4940b88 Include/pydebug.h
--- a/Include/pydebug.h	Fri Jan 20 11:23:02 2012 +0000
+++ b/Include/pydebug.h	Sat Jan 28 18:05:49 2012 -0500
@@ -19,6 +19,7 @@
 PyAPI_DATA(int) Py_DontWriteBytecodeFlag;
 PyAPI_DATA(int) Py_NoUserSiteDirectory;
 PyAPI_DATA(int) Py_UnbufferedStdioFlag;
+PyAPI_DATA(int) Py_HashRandomizationFlag;
 
 /* this is a wrapper around getenv() that pays attention to
    Py_IgnoreEnvironmentFlag.  It should be used for getting variables like
diff -r 73dad4940b88 Include/pythonrun.h
--- a/Include/pythonrun.h	Fri Jan 20 11:23:02 2012 +0000
+++ b/Include/pythonrun.h	Sat Jan 28 18:05:49 2012 -0500
@@ -174,6 +174,8 @@
 PyAPI_FUNC(PyOS_sighandler_t) PyOS_getsig(int);
 PyAPI_FUNC(PyOS_sighandler_t) PyOS_setsig(int, PyOS_sighandler_t);
 
+/* Random */
+PyAPI_FUNC(int) _PyOS_URandom (void *buffer, Py_ssize_t size);
 
 #ifdef __cplusplus
 }
diff -r 73dad4940b88 Lib/os.py
--- a/Lib/os.py	Fri Jan 20 11:23:02 2012 +0000
+++ b/Lib/os.py	Sat Jan 28 18:05:49 2012 -0500
@@ -611,23 +611,6 @@
 except NameError: # statvfs_result may not exist
     pass
 
-if not _exists("urandom"):
-    def urandom(n):
-        """urandom(n) -> str
-
-        Return a string of n random bytes suitable for cryptographic use.
-
-        """
-        try:
-            _urandomfd = open("/dev/urandom", O_RDONLY)
-        except (OSError, IOError):
-            raise NotImplementedError("/dev/urandom (or equivalent) not found")
-        bs = b""
-        while len(bs) < n:
-            bs += read(_urandomfd, n - len(bs))
-        close(_urandomfd)
-        return bs
-
 # Supply os.popen()
 def popen(cmd, mode="r", buffering=-1):
     if not isinstance(cmd, str):
diff -r 73dad4940b88 Lib/test/regrtest.py
--- a/Lib/test/regrtest.py	Fri Jan 20 11:23:02 2012 +0000
+++ b/Lib/test/regrtest.py	Sat Jan 28 18:05:49 2012 -0500
@@ -428,6 +428,11 @@
         except ValueError:
             print("Couldn't find starting test (%s), using all tests" % start)
     if randomize:
+        hashseed = os.getenv('PYTHONHASHSEED')
+        if not hashseed:
+            os.environ['PYTHONHASHSEED'] = str(random_seed)
+            os.execv(sys.executable, [sys.executable] + sys.argv)
+            return
         random.seed(random_seed)
         print("Using random seed", random_seed)
         random.shuffle(tests)
diff -r 73dad4940b88 Lib/test/test_cmd_line.py
--- a/Lib/test/test_cmd_line.py	Fri Jan 20 11:23:02 2012 +0000
+++ b/Lib/test/test_cmd_line.py	Sat Jan 28 18:05:49 2012 -0500
@@ -190,6 +190,16 @@
             self.assertTrue(path1.encode('ascii') in stdout)
             self.assertTrue(path2.encode('ascii') in stdout)
 
+    def test_hash_randomization(self):
+        # Verify that -R enables hash randomization:
+        self.verify_valid_flag('-R')
+        hashes = []
+        for i in range(2):
+            code = 'print(hash("spam"))'
+            data, rc = self.start_python_and_exit_code('-R', '-c', code)
+            self.assertEqual(rc, 0)
+            hashes.append(data)
+        self.assertNotEqual(hashes[0], hashes[1])
 
 def test_main():
     test.support.run_unittest(CmdLineTest)
diff -r 73dad4940b88 Lib/test/test_hash.py
--- a/Lib/test/test_hash.py	Fri Jan 20 11:23:02 2012 +0000
+++ b/Lib/test/test_hash.py	Sat Jan 28 18:05:49 2012 -0500
@@ -3,10 +3,14 @@
 #
 # Also test that hash implementations are inherited as expected
 
+import struct
 import unittest
 from test import support
+from test.script_helper import assert_python_ok
 from collections import Hashable
 
+IS_64BIT = (struct.calcsize('l') == 8)
+
 
 class HashEqualityTestCase(unittest.TestCase):
 
@@ -118,10 +122,65 @@
         for obj in self.hashes_to_check:
             self.assertEqual(hash(obj), _default_hash(obj))
 
+class RandomizationTestCase(unittest.TestCase):
+
+    # Examples of the various types having randomized hash:
+    test_reprs = [repr('abc'), repr(b'abc')]
+
+    def get_hash(self, repr_, randomization=None, seed=None):
+        env = {}
+        if randomization is not None:
+            env['PYTHONHASHRANDOMIZATION'] = str(randomization)
+        if seed is not None:
+            env['PYTHONHASHSEED'] = str(seed)
+        out = assert_python_ok(
+            '-c', 'print(hash(%s))' % repr_,
+            **env)
+        stdout = out[1].strip()
+        return int(stdout)
+
+    def test_empty_string(self):
+        self.assertEqual(hash(""), 0)
+        self.assertEqual(hash(b""), 0)
+
+    def test_null_hash(self):
+        # PYTHONHASHSEED=0 disables the randomized hash
+        if IS_64BIT:
+            known_hash_of_obj = 1453079729188098211
+        else:
+            known_hash_of_obj = -1600925533
+        for repr_ in self.test_reprs:
+            # Randomization is disabled by default:
+            self.assertEqual(self.get_hash(repr_), known_hash_of_obj)
+
+            # If enabled, it can still be disabled by setting the seed to 0:
+            self.assertEqual(self.get_hash(repr_, randomization=1, seed=0),
+                             known_hash_of_obj)
+
+    def test_fixed_hash(self):
+        # test a fixed seed for the randomized hash
+        # Note that all types share the same values:
+        if IS_64BIT:
+            h = -4410911502303878509
+        else:
+            h = -206076799
+        for repr_ in self.test_reprs:
+            self.assertEqual(self.get_hash(repr_, randomization=1, seed=42),
+                             h)
+
+    def test_randomized_hash(self):
+        # two runs should return different hashes
+        for repr_ in self.test_reprs:
+            run1 = self.get_hash(repr_, randomization=1)
+            run2 = self.get_hash(repr_, randomization=1)
+            self.assertNotEqual(run1, run2)
+
+
 def test_main():
     support.run_unittest(HashEqualityTestCase,
                               HashInheritanceTestCase,
-                              HashBuiltinsTestCase)
+                              HashBuiltinsTestCase,
+                         RandomizationTestCase)
 
 
 if __name__ == "__main__":
diff -r 73dad4940b88 Lib/test/test_os.py
--- a/Lib/test/test_os.py	Fri Jan 20 11:23:02 2012 +0000
+++ b/Lib/test/test_os.py	Sat Jan 28 18:05:49 2012 -0500
@@ -9,6 +9,7 @@
 import sys
 import shutil
 from test import support
+from test.script_helper import assert_python_ok
 
 # Detect whether we're on a Linux system that uses the (now outdated
 # and unmaintained) linuxthreads threading library.  There's an issue
@@ -574,14 +575,33 @@
         f.close()
 
 class URandomTests(unittest.TestCase):
-    def test_urandom(self):
-        try:
-            self.assertEqual(len(os.urandom(1)), 1)
-            self.assertEqual(len(os.urandom(10)), 10)
-            self.assertEqual(len(os.urandom(100)), 100)
-            self.assertEqual(len(os.urandom(1000)), 1000)
-        except NotImplementedError:
-            pass
+    def test_urandom_length(self):
+        self.assertEqual(len(os.urandom(0)), 0)
+        self.assertEqual(len(os.urandom(1)), 1)
+        self.assertEqual(len(os.urandom(10)), 10)
+        self.assertEqual(len(os.urandom(100)), 100)
+        self.assertEqual(len(os.urandom(1000)), 1000)
+
+    def test_urandom_value(self):
+        data1 = os.urandom(16)
+        data2 = os.urandom(16)
+        self.assertNotEqual(data1, data2)
+
+    def get_urandom_subprocess(self, count):
+        code = '\n'.join((
+            'import os, sys',
+            'data = os.urandom(%s)' % count,
+            'sys.stdout.buffer.write(data)',
+            'sys.stdout.buffer.flush()'))
+        out = assert_python_ok('-c', code)
+        stdout = out[1]
+        self.assertEqual(len(stdout), 16)
+        return stdout
+
+    def test_urandom_subprocess(self):
+        data1 = self.get_urandom_subprocess(16)
+        data2 = self.get_urandom_subprocess(16)
+        self.assertNotEqual(data1, data2)
 
 class ExecTests(unittest.TestCase):
     @unittest.skipIf(USING_LINUXTHREADS,
diff -r 73dad4940b88 Lib/test/test_set.py
--- a/Lib/test/test_set.py	Fri Jan 20 11:23:02 2012 +0000
+++ b/Lib/test/test_set.py	Sat Jan 28 18:05:49 2012 -0500
@@ -734,6 +734,17 @@
         if self.repr is not None:
             self.assertEqual(repr(self.set), self.repr)
 
+    def check_repr_against_values(self):
+        text = repr(self.set)
+        self.assertTrue(text.startswith('{'))
+        self.assertTrue(text.endswith('}'))
+
+        result = text[1:-1].split(', ')
+        result.sort()
+        sorted_repr_values = [repr(value) for value in self.values]
+        sorted_repr_values.sort()
+        self.assertEqual(result, sorted_repr_values)
+
     def test_print(self):
         try:
             fo = open(support.TESTFN, "w")
@@ -892,7 +903,9 @@
         self.set    = set(self.values)
         self.dup    = set(self.values)
         self.length = 3
-        self.repr   = "{'a', 'c', 'b'}"
+
+    def test_repr(self):
+        self.check_repr_against_values()
 
 #------------------------------------------------------------------------------
 
@@ -903,7 +916,9 @@
         self.set    = set(self.values)
         self.dup    = set(self.values)
         self.length = 3
-        self.repr   = "{b'a', b'c', b'b'}"
+
+    def test_repr(self):
+        self.check_repr_against_values()
 
 #------------------------------------------------------------------------------
 
@@ -916,11 +931,13 @@
         self.set    = set(self.values)
         self.dup    = set(self.values)
         self.length = 4
-        self.repr   = "{'a', b'a', 'b', b'b'}"
 
     def tearDown(self):
         warnings.filters = self.warning_filters
 
+    def test_repr(self):
+        self.check_repr_against_values()
+
 #==============================================================================
 
 def baditer():
diff -r 73dad4940b88 Makefile.pre.in
--- a/Makefile.pre.in	Fri Jan 20 11:23:02 2012 +0000
+++ b/Makefile.pre.in	Sat Jan 28 18:05:49 2012 -0500
@@ -305,6 +305,7 @@
 		Python/pymath.o \
 		Python/pystate.o \
 		Python/pythonrun.o \
+		Python/random.o \
 		Python/structmember.o \
 		Python/symtable.o \
 		Python/sysmodule.o \
diff -r 73dad4940b88 Misc/NEWS
--- a/Misc/NEWS	Fri Jan 20 11:23:02 2012 +0000
+++ b/Misc/NEWS	Sat Jan 28 18:05:49 2012 -0500
@@ -10,6 +10,12 @@
 Core and Builtins
 -----------------
 
+- Issue #13703: add -R command-line option and PYTHONHASHRANDOMIZATION (and
+  PYTHONHASHSEED) environment variables, to provide an opt-in way to protect
+  against denial of service attacks due to hash collisions within the dict
+  and set types. See http://www.ocert.org/advisories/ocert-2011-003.html
+  Patch by David Malcolm, based on work by Victor Stinner.
+
 Library
 -------
 
diff -r 73dad4940b88 Misc/python.man
--- a/Misc/python.man	Fri Jan 20 11:23:02 2012 +0000
+++ b/Misc/python.man	Sat Jan 28 18:05:49 2012 -0500
@@ -34,6 +34,9 @@
 .B \-OO
 ]
 [
+.B \-R
+]
+[
 .B -Q
 .I argument
 ]
@@ -145,6 +148,18 @@
 .B \-OO
 Discard docstrings in addition to the \fB-O\fP optimizations.
 .TP
+.B \-R
+Turn on "hash randomization", so that the hash() values of str, bytes and
+datetime objects are "salted" with an unpredictable pseudo-random value.
+Although they remain constant within an individual Python process, they are
+not predictable between repeated invocations of Python.
+.IP
+This is intended to provide protection against a denial of service
+caused by carefully-chosen inputs that exploit the worst case performance
+of a dict lookup, O(n^2) complexity.  See
+http://www.ocert.org/advisories/ocert-2011-003.html
+for details.
+.TP
 .BI "\-Q " argument
 Division control; see PEP 238.  The argument must be one of "old" (the
 default, int/int and long/long return an int or long), "new" (new
@@ -403,6 +418,17 @@
 If this is set to a non-empty string it is equivalent to specifying
 the \fB\-v\fP option. If set to an integer, it is equivalent to
 specifying \fB\-v\fP multiple times. 
+.IP PYTHONHASHRANDOMIZATION
+If this is set to a non-empty string it is equivalent to specifying the
+\fB\-R\fP option.
+.IP PYTHONHASHSEED
+If this is set, it is used as a fixed seed for generating the hash() of
+the types covered by the \fB\-R\fP  (or its equivalent environment variable,
+\fB\PYTHONHASHRANDOMIZATION\fP).
+It is primarily intended for use in selftests for the interpreter, but
+may perhaps be of use for reproducing a specific dict ordering.
+It should be a decimal number in the range [0; 4294967295].  Specifying
+the value 0 overrides the other setting, disabling the hash random salt.
 .SH AUTHOR
 The Python Software Foundation: http://www.python.org/psf
 .SH INTERNET RESOURCES
diff -r 73dad4940b88 Modules/datetimemodule.c
--- a/Modules/datetimemodule.c	Fri Jan 20 11:23:02 2012 +0000
+++ b/Modules/datetimemodule.c	Sat Jan 28 18:05:49 2012 -0500
@@ -2566,10 +2566,12 @@
     register long x;
 
     p = (unsigned char *) data;
-    x = *p << 7;
+    x = _Py_HashSecret.prefix;
+    x ^= *p << 7;
     while (--len >= 0)
         x = (1000003*x) ^ *p++;
     x ^= len;
+    x ^= _Py_HashSecret.suffix;
     if (x == -1)
         x = -2;
 
diff -r 73dad4940b88 Modules/main.c
--- a/Modules/main.c	Fri Jan 20 11:23:02 2012 +0000
+++ b/Modules/main.c	Sat Jan 28 18:05:49 2012 -0500
@@ -47,7 +47,7 @@
 static int  orig_argc;
 
 /* command line options */
-#define BASE_OPTS L"bBc:dEhiJm:OsStuvVW:xX?"
+#define BASE_OPTS L"bBc:dEhiJm:ORsStuvVW:xX?"
 
 #define PROGRAM_OPTS BASE_OPTS
 
@@ -72,6 +72,9 @@
 -m mod : run library module as a script (terminates option list)\n\
 -O     : optimize generated bytecode slightly; also PYTHONOPTIMIZE=x\n\
 -OO    : remove doc-strings in addition to the -O optimizations\n\
+-R     : use a pseudo-random salt to make hash() values of various types be\n\
+         unpredictable between separate invocations of the interpreter, as\n\
+         a defence against denial-of-service attacks\n\
 -s     : don't add user site directory to sys.path; also PYTHONNOUSERSITE\n\
 -S     : don't imply 'import site' on initialization\n\
 ";
@@ -99,6 +102,11 @@
 PYTHONCASEOK : ignore case in 'import' statements (Windows).\n\
 PYTHONIOENCODING: Encoding[:errors] used for stdin/stdout/stderr.\n\
 ";
+static char *usage_6 = "\
+PYTHONHASHRANDOMIZATION : make hash() values of various types be unpredictable\n\
+                          between separate invocations of the interpreter, as\n\
+                          a defence against denial-of-service attacks\n\
+";
 
 #ifndef MS_WINDOWS
 static FILE*
@@ -136,6 +144,7 @@
         fputs(usage_3, f);
         fprintf(f, usage_4, DELIM);
         fprintf(f, usage_5, DELIM, PYTHONHOMEHELP);
+        fputs(usage_6, f);
     }
 #if defined(__VMS)
     if (exitcode == 0) {
@@ -373,6 +382,10 @@
             PySys_AddWarnOption(_PyOS_optarg);
             break;
 
+        case 'R':
+            Py_HashRandomizationFlag++;
+            break;
+
         /* This space reserved for other options */
 
         default:
diff -r 73dad4940b88 Modules/posixmodule.c
--- a/Modules/posixmodule.c	Fri Jan 20 11:23:02 2012 +0000
+++ b/Modules/posixmodule.c	Sat Jan 28 18:05:49 2012 -0500
@@ -6942,82 +6942,6 @@
 }
 #endif
 
-#ifdef MS_WINDOWS
-
-PyDoc_STRVAR(win32_urandom__doc__,
-"urandom(n) -> str\n\n\
-Return n random bytes suitable for cryptographic use.");
-
-typedef BOOL (WINAPI *CRYPTACQUIRECONTEXTA)(HCRYPTPROV *phProv,\
-              LPCSTR pszContainer, LPCSTR pszProvider, DWORD dwProvType,\
-              DWORD dwFlags );
-typedef BOOL (WINAPI *CRYPTGENRANDOM)(HCRYPTPROV hProv, DWORD dwLen,\
-              BYTE *pbBuffer );
-
-static CRYPTGENRANDOM pCryptGenRandom = NULL;
-/* This handle is never explicitly released. Instead, the operating
-   system will release it when the process terminates. */
-static HCRYPTPROV hCryptProv = 0;
-
-static PyObject*
-win32_urandom(PyObject *self, PyObject *args)
-{
-    int howMany;
-    PyObject* result;
-
-    /* Read arguments */
-    if (! PyArg_ParseTuple(args, "i:urandom", &howMany))
-        return NULL;
-    if (howMany < 0)
-        return PyErr_Format(PyExc_ValueError,
-                            "negative argument not allowed");
-
-    if (hCryptProv == 0) {
-        HINSTANCE hAdvAPI32 = NULL;
-        CRYPTACQUIRECONTEXTA pCryptAcquireContext = NULL;
-
-        /* Obtain handle to the DLL containing CryptoAPI
-           This should not fail         */
-        hAdvAPI32 = GetModuleHandle("advapi32.dll");
-        if(hAdvAPI32 == NULL)
-            return win32_error("GetModuleHandle", NULL);
-
-        /* Obtain pointers to the CryptoAPI functions
-           This will fail on some early versions of Win95 */
-        pCryptAcquireContext = (CRYPTACQUIRECONTEXTA)GetProcAddress(
-                                        hAdvAPI32,
-                                        "CryptAcquireContextA");
-        if (pCryptAcquireContext == NULL)
-            return PyErr_Format(PyExc_NotImplementedError,
-                                "CryptAcquireContextA not found");
-
-        pCryptGenRandom = (CRYPTGENRANDOM)GetProcAddress(
-                                        hAdvAPI32, "CryptGenRandom");
-        if (pCryptGenRandom == NULL)
-            return PyErr_Format(PyExc_NotImplementedError,
-                                "CryptGenRandom not found");
-
-        /* Acquire context */
-        if (! pCryptAcquireContext(&hCryptProv, NULL, NULL,
-                                   PROV_RSA_FULL, CRYPT_VERIFYCONTEXT))
-            return win32_error("CryptAcquireContext", NULL);
-    }
-
-    /* Allocate bytes */
-    result = PyBytes_FromStringAndSize(NULL, howMany);
-    if (result != NULL) {
-        /* Get random data */
-        memset(PyBytes_AS_STRING(result), 0, howMany); /* zero seed */
-        if (! pCryptGenRandom(hCryptProv, howMany, (unsigned char*)
-                              PyBytes_AS_STRING(result))) {
-            Py_DECREF(result);
-            return win32_error("CryptGenRandom", NULL);
-        }
-    }
-    return result;
-}
-#endif
-
 PyDoc_STRVAR(device_encoding__doc__,
 "device_encoding(fd) -> str\n\n\
 Return a string describing the encoding of the device\n\
@@ -7055,41 +6979,35 @@
     return Py_None;
 }
 
-#ifdef __VMS
-/* Use openssl random routine */
-#include <openssl/rand.h>
-PyDoc_STRVAR(vms_urandom__doc__,
+PyDoc_STRVAR(posix_urandom__doc__,
 "urandom(n) -> str\n\n\
-Return n random bytes suitable for cryptographic use.");
-
-static PyObject*
-vms_urandom(PyObject *self, PyObject *args)
-{
-    int howMany;
-    PyObject* result;
-
-    /* Read arguments */
-    if (! PyArg_ParseTuple(args, "i:urandom", &howMany))
-        return NULL;
-    if (howMany < 0)
+Return n pseudo-random bytes.");
+
+static PyObject *
+posix_urandom(PyObject *self, PyObject *args)
+{
+    Py_ssize_t size;
+    PyObject *result;
+    int ret;
+ 
+     /* Read arguments */
+    if (!PyArg_ParseTuple(args, "n:urandom", &size))
+        return NULL;
+    if (size < 0)
         return PyErr_Format(PyExc_ValueError,
                             "negative argument not allowed");
-
-    /* Allocate bytes */
-    result = PyBytes_FromStringAndSize(NULL, howMany);
-    if (result != NULL) {
-        /* Get random data */
-        if (RAND_pseudo_bytes((unsigned char*)
-                              PyBytes_AS_STRING(result),
-                              howMany) < 0) {
-            Py_DECREF(result);
-            return PyErr_Format(PyExc_ValueError,
-                                "RAND_pseudo_bytes");
-        }
+    result = PyBytes_FromStringAndSize(NULL, size);
+    if (result == NULL)
+        return NULL;
+
+    ret = _PyOS_URandom(PyBytes_AS_STRING(result),
+                        PyBytes_GET_SIZE(result));
+    if (ret == -1) {
+        Py_DECREF(result);
+        return NULL;
     }
     return result;
 }
-#endif
 
 static PyMethodDef posix_methods[] = {
     {"access",          posix_access, METH_VARARGS, posix_access__doc__},
@@ -7374,12 +7292,7 @@
 #ifdef HAVE_GETLOADAVG
     {"getloadavg",      posix_getloadavg, METH_NOARGS, posix_getloadavg__doc__},
 #endif
- #ifdef MS_WINDOWS
-    {"urandom", win32_urandom, METH_VARARGS, win32_urandom__doc__},
- #endif
- #ifdef __VMS
-    {"urandom", vms_urandom, METH_VARARGS, vms_urandom__doc__},
- #endif
+    {"urandom",         posix_urandom,   METH_VARARGS, posix_urandom__doc__},
     {NULL,              NULL}            /* Sentinel */
 };
 
diff -r 73dad4940b88 Objects/bytesobject.c
--- a/Objects/bytesobject.c	Fri Jan 20 11:23:02 2012 +0000
+++ b/Objects/bytesobject.c	Sat Jan 28 18:05:49 2012 -0500
@@ -899,11 +899,17 @@
     if (a->ob_shash != -1)
         return a->ob_shash;
     len = Py_SIZE(a);
+    if (len == 0) {
+        a->ob_shash = 0;
+        return 0;
+    }
     p = (unsigned char *) a->ob_sval;
-    x = *p << 7;
+    x = _Py_HashSecret.prefix;
+    x ^= *p << 7;
     while (--len >= 0)
         x = (1000003*x) ^ *p++;
     x ^= Py_SIZE(a);
+    x ^= _Py_HashSecret.suffix;
     if (x == -1)
         x = -2;
     a->ob_shash = x;
diff -r 73dad4940b88 Objects/object.c
--- a/Objects/object.c	Fri Jan 20 11:23:02 2012 +0000
+++ b/Objects/object.c	Sat Jan 28 18:05:49 2012 -0500
@@ -712,6 +712,8 @@
     return -1;
 }
 
+_Py_HashSecret_t _Py_HashSecret;
+
 long
 PyObject_Hash(PyObject *v)
 {
diff -r 73dad4940b88 Objects/unicodeobject.c
--- a/Objects/unicodeobject.c	Fri Jan 20 11:23:02 2012 +0000
+++ b/Objects/unicodeobject.c	Sat Jan 28 18:05:49 2012 -0500
@@ -7344,11 +7344,17 @@
     if (self->hash != -1)
         return self->hash;
     len = Py_SIZE(self);
+    if (len == 0) {
+        self->hash = 0;
+        return 0;
+    }
     p = self->str;
-    x = *p << 7;
+    x = _Py_HashSecret.prefix;
+    x ^= *p << 7;
     while (--len >= 0)
         x = (1000003*x) ^ *p++;
     x ^= Py_SIZE(self);
+    x ^= _Py_HashSecret.suffix;
     if (x == -1)
         x = -2;
     self->hash = x;
diff -r 73dad4940b88 PCbuild/pythoncore.vcproj
--- a/PCbuild/pythoncore.vcproj	Fri Jan 20 11:23:02 2012 +0000
+++ b/PCbuild/pythoncore.vcproj	Sat Jan 28 18:05:49 2012 -0500
@@ -1778,6 +1778,10 @@
 				RelativePath="..\Python\pythonrun.c"
 				>
 			</File>
+ 			<File
+				RelativePath="..\Python\random.c"
+				>
+			</File>
 			<File
 				RelativePath="..\Python\structmember.c"
 				>
diff -r 73dad4940b88 Python/pythonrun.c
--- a/Python/pythonrun.c	Fri Jan 20 11:23:02 2012 +0000
+++ b/Python/pythonrun.c	Sat Jan 28 18:05:49 2012 -0500
@@ -73,6 +73,7 @@
 extern void _PyUnicode_Fini(void);
 extern int _PyLong_Init(void);
 extern void PyLong_Fini(void);
+extern void _PyRandom_Init(void);
 
 #ifdef WITH_THREAD
 extern void _PyGILState_Init(PyInterpreterState *, PyThreadState *);
@@ -91,6 +92,7 @@
 int Py_IgnoreEnvironmentFlag; /* e.g. PYTHONPATH, PYTHONHOME */
 int Py_NoUserSiteDirectory = 0; /* for -s and site.py */
 int Py_UnbufferedStdioFlag = 0; /* Unbuffered binary std{in,out,err} */
+int Py_HashRandomizationFlag = 0; /* for -R and PYTHONHASHRANDOMIZATION */
 
 /* PyModule_GetWarningsModule is no longer necessary as of 2.6
 since _warnings is builtin.  This API should not be used. */
@@ -195,6 +197,10 @@
         Py_OptimizeFlag = add_flag(Py_OptimizeFlag, p);
     if ((p = Py_GETENV("PYTHONDONTWRITEBYTECODE")) && *p != '\0')
         Py_DontWriteBytecodeFlag = add_flag(Py_DontWriteBytecodeFlag, p);
+    if ((p = Py_GETENV("PYTHONHASHRANDOMIZATION")) && *p != '\0')
+        Py_HashRandomizationFlag = add_flag(Py_HashRandomizationFlag, p);
+    
+    _PyRandom_Init();
 
     interp = PyInterpreterState_New();
     if (interp == NULL)
diff -r 73dad4940b88 Python/random.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Python/random.c	Sat Jan 28 18:05:49 2012 -0500
@@ -0,0 +1,284 @@
+#include "Python.h"
+#ifdef MS_WINDOWS
+#include <windows.h>
+#else
+#include <fcntl.h>
+#endif
+
+static int random_initialized = 0;
+
+#ifdef MS_WINDOWS
+typedef BOOL (WINAPI *CRYPTACQUIRECONTEXTA)(HCRYPTPROV *phProv,\
+              LPCSTR pszContainer, LPCSTR pszProvider, DWORD dwProvType,\
+              DWORD dwFlags );
+typedef BOOL (WINAPI *CRYPTGENRANDOM)(HCRYPTPROV hProv, DWORD dwLen,\
+              BYTE *pbBuffer );
+
+static CRYPTGENRANDOM pCryptGenRandom = NULL;
+/* This handle is never explicitly released. Instead, the operating
+   system will release it when the process terminates. */
+static HCRYPTPROV hCryptProv = 0;
+
+static int
+win32_urandom_init(int raise)
+{
+    HINSTANCE hAdvAPI32 = NULL;
+    CRYPTACQUIRECONTEXTA pCryptAcquireContext = NULL;
+
+    /* Obtain handle to the DLL containing CryptoAPI. This should not fail. */
+    hAdvAPI32 = GetModuleHandle("advapi32.dll");
+    if(hAdvAPI32 == NULL)
+        goto error;
+
+    /* Obtain pointers to the CryptoAPI functions. This will fail on some early
+       versions of Win95. */
+    pCryptAcquireContext = (CRYPTACQUIRECONTEXTA)GetProcAddress(
+                               hAdvAPI32, "CryptAcquireContextA");
+    if (pCryptAcquireContext == NULL)
+        goto error;
+
+    pCryptGenRandom = (CRYPTGENRANDOM)GetProcAddress(hAdvAPI32,
+                                                     "CryptGenRandom");
+    if (pCryptGenRandom == NULL)
+        goto error;
+
+    /* Acquire context */
+    if (! pCryptAcquireContext(&hCryptProv, NULL, NULL,
+                               PROV_RSA_FULL, CRYPT_VERIFYCONTEXT))
+        goto error;
+
+    return 0;
+
+error:
+    if (raise)
+        PyErr_SetFromWindowsErr(0);
+    else
+        Py_FatalError("Failed to initialize Windows random API (CryptoGen)");
+    return -1;
+}
+
+/* Fill buffer with size pseudo-random bytes generated by the Windows CryptoGen
+   API. Return 0 on success, or -1 on error. */
+static int
+win32_urandom(unsigned char *buffer, Py_ssize_t size, int raise)
+{
+    Py_ssize_t orig_size = size;
+    Py_ssize_t chunk;
+
+    if (hCryptProv == 0)
+    {
+        if (win32_urandom_init(raise) == -1)
+            return -1;
+    }
+
+    while (size > 0)
+    {
+        chunk = Py_MIN(size, INT_MAX);
+        if (!pCryptGenRandom(hCryptProv, chunk, buffer))
+        {
+            /* CryptGenRandom() failed */
+            if (raise)
+                PyErr_SetFromWindowsErr(0);
+            else
+                Py_FatalError("Failed to initialized the randomized hash "
+                        "secret using CryptoGen)");
+            return -1;
+        }
+        buffer += chunk;
+        size -= chunk;
+    }
+    return 0;
+}
+
+#else
+
+/* Read size bytes from /dev/urandom into buffer.
+   Call Py_FatalError() on error. */
+static void
+dev_urandom_noraise(char *buffer, Py_ssize_t size)
+{
+    int fd;
+    Py_ssize_t n;
+
+    assert (0 < size);
+
+    fd = open("/dev/urandom", O_RDONLY);
+    if (fd < 0)
+        Py_FatalError("Failed to open /dev/urandom");
+
+    while (0 < size)
+    {
+        do {
+            n = read(fd, buffer, (size_t)size);
+        } while (n < 0 && errno == EINTR);
+        if (n <= 0)
+        {
+            /* stop on error or if read(size) returned 0 */
+            Py_FatalError("Failed to read bytes from /dev/urandom");
+            break;
+        }
+        buffer += n;
+        size -= (Py_ssize_t)n;
+    }
+    close(fd);
+}
+
+/* Read size bytes from /dev/urandom into buffer.
+   Return 0 on success, raise an exception and return -1 on error. */
+static int
+dev_urandom_python(char *buffer, Py_ssize_t size)
+{
+    int fd;
+    Py_ssize_t n;
+
+    if (size <= 0)
+        return 0;
+
+    Py_BEGIN_ALLOW_THREADS
+    fd = open("/dev/urandom", O_RDONLY);
+    Py_END_ALLOW_THREADS
+    if (fd < 0)
+    {
+        PyErr_SetFromErrnoWithFilename(PyExc_OSError, "/dev/urandom");
+        return -1;
+    }
+
+    Py_BEGIN_ALLOW_THREADS
+    do {
+        do {
+            n = read(fd, buffer, (size_t)size);
+        } while (n < 0 && errno == EINTR);
+        if (n <= 0)
+            break;
+        buffer += n;
+        size -= (Py_ssize_t)n;
+    } while (0 < size);
+    Py_END_ALLOW_THREADS
+
+    if (n <= 0)
+    {
+        /* stop on error or if read(size) returned 0 */
+        if (n < 0)
+            PyErr_SetFromErrno(PyExc_OSError);
+        else
+            PyErr_Format(PyExc_RuntimeError,
+                         "Failed to read %zi bytes from /dev/urandom",
+                         size);
+        close(fd);
+        return -1;
+    }
+    close(fd);
+    return 0;
+}
+#endif
+
+/* Fill buffer with pseudo-random bytes generated by a linear congruent
+   generator (LCG):
+
+       x(n+1) = (x(n) * 214013 + 2531011) % 2^32
+
+   Use bits 23..16 of x(n) to generate a byte. */
+static void
+lcg_urandom(unsigned int x0, unsigned char *buffer, size_t size)
+{
+    size_t index;
+    unsigned int x;
+
+    x = x0;
+    for (index=0; index < size; index++) {
+        x *= 214013;
+        x += 2531011;
+        /* modulo 2 ^ (8 * sizeof(int)) */
+        buffer[index] = (x >> 16) & 0xff;
+    }
+}
+
+/* Fill buffer with size pseudo-random bytes, not suitable for cryptographic
+   use, from the operating random number generator (RNG).
+
+   Return 0 on success, raise an exception and return -1 on error. */
+int
+_PyOS_URandom(void *buffer, Py_ssize_t size)
+{
+    if (size < 0) {
+        PyErr_Format(PyExc_ValueError,
+                     "negative argument not allowed");
+        return -1;
+    }
+    if (size == 0)
+        return 0;
+
+#ifdef MS_WINDOWS
+    return win32_urandom((unsigned char *)buffer, size, 1);
+#else
+    return dev_urandom_python((char*)buffer, size);
+#endif
+}
+
+void
+_PyRandom_Init(void)
+{
+    char *env;
+    void *secret = &_Py_HashSecret;
+    Py_ssize_t secret_size = sizeof(_Py_HashSecret);
+
+    if (random_initialized)
+        return;
+    random_initialized = 1;
+
+    /*
+      By default, hash randomization is disabled, and only
+      enabled if PYTHONHASHRANDOMIZATION is set to non-empty
+      or if "-R" is provided at the command line:
+    */
+    if (!Py_HashRandomizationFlag) {
+        /* Disable the randomized hash: */
+        memset(secret, 0, secret_size);
+        return;
+    }
+
+    /*
+      Hash randomization is enabled.  Generate a per-process secret,
+      using PYTHONHASHSEED if provided.
+    */
+
+    env = Py_GETENV("PYTHONHASHSEED");
+    if (env && *env != '\0') {
+        char *endptr = env;
+        unsigned long seed;
+        seed = strtoul(env, &endptr, 10);
+        if (*endptr != '\0'
+            || seed > 4294967295UL
+            || (errno == ERANGE && seed == ULONG_MAX))
+        {
+            Py_FatalError("PYTHONHASHSEED must be an integer "
+                          "in range [0; 4294967295]");
+        }
+        if (seed == 0) {
+            /* disable the randomized hash */
+            memset(secret, 0, secret_size);
+        }
+        else {
+            lcg_urandom(seed, (unsigned char*)secret, secret_size);
+        }
+    }
+    else {
+#ifdef MS_WINDOWS
+#if 1
+        (void)win32_urandom((unsigned char *)secret, secret_size, 0);
+#else
+        /* fast but weak RNG (fast initialization, weak seed) */
+        _PyTime_timeval t;
+        unsigned int seed;
+        _PyTime_gettimeofday(&t);
+        seed = (unsigned int)t.tv_sec;
+        seed ^= t.tv_usec;
+        seed ^= getpid();
+        lcg_urandom(seed, (unsigned char*)secret, secret_size);
+#endif
+#else /* #ifdef MS_WINDOWS */
+        dev_urandom_noraise((char*)secret, secret_size);
+#endif
+    }
+}
+


More information about the Python-bugs-list mailing list