Merge tag 'v2.6.1' (fix CVE-2013-1445)

This is the PyCrypto 2.6.1 release.

Dwayne Litzenberger (4):
      Random: Make Crypto.Random.atfork() set last_reseed=None (CVE-2013-1445)
      Fortuna: Add comments for reseed_interval and min_pool_size to FortunaAccumulator
      Update the ChangeLog
      Release v2.6.1

8 files changed, 271 insertions, 6 deletions

diff --git a/ChangeLog b/ChangeLog
index c2314c4..f37948f 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,55 @@
+2.6.1
+=====
+	* [CVE-2013-1445] Fix PRNG not correctly reseeded in some situations.
+
+	  In previous versions of PyCrypto, the Crypto.Random PRNG exhibits a
+	  race condition that may cause forked processes to generate identical
+	  sequences of 'random' numbers.
+
+	  This is a fairly obscure bug that will (hopefully) not affect many
+	  applications, but the failure scenario is pretty bad.  Here is some
+	  sample code that illustrates the problem:
+
+	      from binascii import hexlify
+	      import multiprocessing, pprint, time
+	      import Crypto.Random
+
+	      def task_main(arg):
+	          a = Crypto.Random.get_random_bytes(8)
+	          time.sleep(0.1)
+	          b = Crypto.Random.get_random_bytes(8)
+	          rdy, ack = arg
+	          rdy.set()
+	          ack.wait()
+	          return "%s,%s" % (hexlify(a).decode(),
+	                            hexlify(b).decode())
+
+	      n_procs = 4
+	      manager = multiprocessing.Manager()
+	      rdys = [manager.Event() for i in range(n_procs)]
+	      acks = [manager.Event() for i in range(n_procs)]
+	      Crypto.Random.get_random_bytes(1)
+	      pool = multiprocessing.Pool(processes=n_procs,
+	                                  initializer=Crypto.Random.atfork)
+	      res_async = pool.map_async(task_main, zip(rdys, acks))
+	      pool.close()
+	      [rdy.wait() for rdy in rdys]
+	      [ack.set() for ack in acks]
+	      res = res_async.get()
+	      pprint.pprint(sorted(res))
+	      pool.join()
+
+	  The output should be random, but it looked like this:
+
+	      ['c607803ae01aa8c0,2e4de6457a304b34',
+	       'c607803ae01aa8c0,af80d08942b4c987',
+	       'c607803ae01aa8c0,b0e4c0853de927c4',
+	       'c607803ae01aa8c0,f0362585b3fceba4']
+
+	  This release fixes the problem by resetting the rate-limiter when
+	  Crypto.Random.atfork() is invoked.  It also adds some tests and a
+	  few related comments.
+
 2.6
 ===
 	* [CVE-2012-2417] Fix LP#985164: insecure ElGamal key generation.
diff --git a/Doc/pycrypt.rst b/Doc/pycrypt.rst
index f8df9fb..4b2e488 100644
--- a/Doc/pycrypt.rst
+++ b/Doc/pycrypt.rst
@@ -2,7 +2,7 @@
 Python Cryptography Toolkit
 ====================================
 
-**Version 2.6**
+**Version 2.6.1**
 
 The Python Cryptography Toolkit describes a package containing various
 cryptographic modules for the Python programming language.  This
diff --git a/lib/Crypto/Random/Fortuna/FortunaAccumulator.py b/lib/Crypto/Random/Fortuna/FortunaAccumulator.py
index 42e998c..5ffe825 100644
--- a/lib/Crypto/Random/Fortuna/FortunaAccumulator.py
+++ b/lib/Crypto/Random/Fortuna/FortunaAccumulator.py
@@ -97,8 +97,25 @@ def which_pools(r):
 
 class FortunaAccumulator(object):
 
-    min_pool_size = 64      # TODO: explain why
-    reseed_interval = 0.100   # 100 ms    TODO: explain why
+    # An estimate of how many bytes we must append to pool 0 before it will
+    # contain 128 bits of entropy (with respect to an attack).  We reseed the
+    # generator only after pool 0 contains `min_pool_size` bytes.  Note that
+    # unlike with some other PRNGs, Fortuna's security does not rely on the
+    # accuracy of this estimate---we can accord to be optimistic here.
+    min_pool_size = 64  # size in bytes
+
+    # If an attacker can predict some (but not all) of our entropy sources, the
+    # `min_pool_size` check may not be sufficient to prevent a successful state
+    # compromise extension attack.  To resist this attack, Fortuna spreads the
+    # input across 32 pools, which are then consumed (to reseed the output
+    # generator) with exponentially decreasing frequency.
+    #
+    # In order to prevent an attacker from gaining knowledge of all 32 pools
+    # before we have a chance to fill them with enough information that the
+    # attacker cannot predict, we impose a rate limit of 10 reseeds/second (one
+    # per 100 ms).  This ensures that a hypothetical 33rd pool would only be
+    # needed after a minimum of 13 years of sustained attack.
+    reseed_interval = 0.100     # time in seconds
 
     def __init__(self):
         self.reseed_count = 0
@@ -112,6 +129,15 @@ class FortunaAccumulator(object):
         self.pools = [FortunaPool() for i in range(32)]     # 32 pools
         assert(self.pools[0] is not self.pools[1])
 
+    def _forget_last_reseed(self):
+        # This is not part of the standard Fortuna definition, and using this
+        # function frequently can weaken Fortuna's ability to resist a state
+        # compromise extension attack, but we need this in order to properly
+        # implement Crypto.Random.atfork().  Otherwise, forked child processes
+        # might continue to use their parent's PRNG state for up to 100ms in
+        # some cases. (e.g. CVE-2013-1445)
+        self.last_reseed = None
+
     def random_data(self, bytes):
         current_time = maybe_monotonic_time()
         if (self.last_reseed is not None and self.last_reseed > current_time): # Avoid float comparison to None to make Py3k happy
diff --git a/lib/Crypto/Random/_UserFriendlyRNG.py b/lib/Crypto/Random/_UserFriendlyRNG.py
index c2a2eae..957e006 100644
--- a/lib/Crypto/Random/_UserFriendlyRNG.py
+++ b/lib/Crypto/Random/_UserFriendlyRNG.py
@@ -90,9 +90,24 @@ class _UserFriendlyRNG(object):
         """Initialize the random number generator and seed it with entropy from
         the operating system.
         """
+
+        # Save the pid (helps ensure that Crypto.Random.atfork() gets called)
         self._pid = os.getpid()
+
+        # Collect entropy from the operating system and feed it to
+        # FortunaAccumulator
         self._ec.reinit()
 
+        # Override FortunaAccumulator's 100ms minimum re-seed interval.  This
+        # is necessary to avoid a race condition between this function and
+        # self.read(), which that can otherwise cause forked child processes to
+        # produce identical output.  (e.g. CVE-2013-1445)
+        #
+        # Note that if this function can be called frequently by an attacker,
+        # (and if the bits from OSRNG are insufficiently random) it will weaken
+        # Fortuna's ability to resist a state compromise extension attack.
+        self._fa._forget_last_reseed()
+
     def close(self):
         self.closed = True
         self._osrng = None
diff --git a/lib/Crypto/SelfTest/Random/__init__.py b/lib/Crypto/SelfTest/Random/__init__.py
index 48d84ff..f972bf0 100644
--- a/lib/Crypto/SelfTest/Random/__init__.py
+++ b/lib/Crypto/SelfTest/Random/__init__.py
@@ -32,6 +32,7 @@ def get_tests(config={}):
     from Crypto.SelfTest.Random import OSRNG;               tests += OSRNG.get_tests(config=config)
     from Crypto.SelfTest.Random import test_random;         tests += test_random.get_tests(config=config)
     from Crypto.SelfTest.Random import test_rpoolcompat;    tests += test_rpoolcompat.get_tests(config=config)
+    from Crypto.SelfTest.Random import test__UserFriendlyRNG; tests += test__UserFriendlyRNG.get_tests(config=config)
     return tests
 
 if __name__ == '__main__':
diff --git a/lib/Crypto/SelfTest/Random/test__UserFriendlyRNG.py b/lib/Crypto/SelfTest/Random/test__UserFriendlyRNG.py
new file mode 100644
index 0000000..771a663
--- /dev/null
+++ b/lib/Crypto/SelfTest/Random/test__UserFriendlyRNG.py
@@ -0,0 +1,171 @@
+# -*- coding: utf-8 -*-
+# Self-tests for the user-friendly Crypto.Random interface
+#
+# Written in 2013 by Dwayne C. Litzenberger <dlitz@dlitz.net>
+#
+# ===================================================================
+# The contents of this file are dedicated to the public domain.  To
+# the extent that dedication to the public domain is not available,
+# everyone is granted a worldwide, perpetual, royalty-free,
+# non-exclusive license to exercise all rights associated with the
+# contents of this file for any purpose whatsoever.
+# No rights are reserved.
+#
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+# EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+# NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
+# BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
+# ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+# CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+# SOFTWARE.
+# ===================================================================
+
+"""Self-test suite for generic Crypto.Random stuff """
+
+from __future__ import nested_scopes
+
+__revision__ = "$Id$"
+
+import binascii
+import pprint
+import unittest
+import os
+import time
+import sys
+if sys.version_info[0] == 2 and sys.version_info[1] == 1:
+    from Crypto.Util.py21compat import *
+from Crypto.Util.py3compat import *
+
+try:
+    import multiprocessing
+except ImportError:
+    multiprocessing = None
+
+import Crypto.Random._UserFriendlyRNG
+import Crypto.Random.random
+
+class RNGForkTest(unittest.TestCase):
+
+    def _get_reseed_count(self):
+        """
+        Get `FortunaAccumulator.reseed_count`, the global count of the
+        number of times that the PRNG has been reseeded.
+        """
+        rng_singleton = Crypto.Random._UserFriendlyRNG._get_singleton()
+        rng_singleton._lock.acquire()
+        try:
+            return rng_singleton._fa.reseed_count
+        finally:
+            rng_singleton._lock.release()
+
+    def runTest(self):
+        # Regression test for CVE-2013-1445.  We had a bug where, under the
+        # right conditions, two processes might see the same random sequence.
+
+        if sys.platform.startswith('win'):  # windows can't fork
+            assert not hasattr(os, 'fork')    # ... right?
+            return
+
+        # Wait 150 ms so that we don't trigger the rate-limit prematurely.
+        time.sleep(0.15)
+
+        reseed_count_before = self._get_reseed_count()
+
+        # One or both of these calls together should trigger a reseed right here.
+        Crypto.Random._UserFriendlyRNG._get_singleton().reinit()
+        Crypto.Random.get_random_bytes(1)
+
+        reseed_count_after = self._get_reseed_count()
+        self.assertNotEqual(reseed_count_before, reseed_count_after)  # sanity check: test should reseed parent before forking
+
+        rfiles = []
+        for i in range(10):
+            rfd, wfd = os.pipe()
+            if os.fork() == 0:
+                # child
+                os.close(rfd)
+                f = os.fdopen(wfd, "wb")
+
+                Crypto.Random.atfork()
+
+                data = Crypto.Random.get_random_bytes(16)
+
+                f.write(data)
+                f.close()
+                os._exit(0)
+            # parent
+            os.close(wfd)
+            rfiles.append(os.fdopen(rfd, "rb"))
+
+        results = []
+        results_dict = {}
+        for f in rfiles:
+            data = binascii.hexlify(f.read())
+            results.append(data)
+            results_dict[data] = 1
+            f.close()
+
+        if len(results) != len(results_dict.keys()):
+            raise AssertionError("RNG output duplicated across fork():\n%s" %
+                                 (pprint.pformat(results)))
+
+
+# For RNGMultiprocessingForkTest
+def _task_main(q):
+    a = Crypto.Random.get_random_bytes(16)
+    time.sleep(0.1)     # wait 100 ms
+    b = Crypto.Random.get_random_bytes(16)
+    q.put(binascii.b2a_hex(a))
+    q.put(binascii.b2a_hex(b))
+    q.put(None)      # Wait for acknowledgment
+
+
+class RNGMultiprocessingForkTest(unittest.TestCase):
+
+    def runTest(self):
+        # Another regression test for CVE-2013-1445.  This is basically the
+        # same as RNGForkTest, but less compatible with old versions of Python,
+        # and a little easier to read.
+
+        n_procs = 5
+        manager = multiprocessing.Manager()
+        queues = [manager.Queue(1) for i in range(n_procs)]
+
+        # Reseed the pool
+        time.sleep(0.15)
+        Crypto.Random._UserFriendlyRNG._get_singleton().reinit()
+        Crypto.Random.get_random_bytes(1)
+
+        # Start the child processes
+        pool = multiprocessing.Pool(processes=n_procs, initializer=Crypto.Random.atfork)
+        map_result = pool.map_async(_task_main, queues)
+
+        # Get the results, ensuring that no pool processes are reused.
+        aa = [queues[i].get(30) for i in range(n_procs)]
+        bb = [queues[i].get(30) for i in range(n_procs)]
+        res = list(zip(aa, bb))
+
+        # Shut down the pool
+        map_result.get(30)
+        pool.close()
+        pool.join()
+
+        # Check that the results are unique
+        if len(set(aa)) != len(aa) or len(set(res)) != len(res):
+            raise AssertionError("RNG output duplicated across fork():\n%s" %
+                                 (pprint.pformat(res),))
+
+
+def get_tests(config={}):
+    tests = []
+    tests += [RNGForkTest()]
+    if multiprocessing is not None:
+        tests += [RNGMultiprocessingForkTest()]
+    return tests
+
+if __name__ == '__main__':
+    suite = lambda: unittest.TestSuite(get_tests())
+    unittest.main(defaultTest='suite')
+
+# vim:set ts=4 sw=4 sts=4 expandtab:
diff --git a/lib/Crypto/__init__.py b/lib/Crypto/__init__.py
index 79c8286..db238d7 100644
--- a/lib/Crypto/__init__.py
+++ b/lib/Crypto/__init__.py
@@ -43,9 +43,9 @@ Crypto.Util
 
 __all__ = ['Cipher', 'Hash', 'Protocol', 'PublicKey', 'Util', 'Signature', 'IO']
 
-__version__ = '2.6'     # See also below and setup.py
+__version__ = '2.6.1'     # See also below and setup.py
 __revision__ = "$Id$"
 
 # New software should look at this instead of at __version__ above.
-version_info = (2, 6, 0, 'final', 0)    # See also above and setup.py
+version_info = (2, 6, 1, 'final', 0)    # See also above and setup.py
 
diff --git a/setup.py b/setup.py
index 903a81f..ba0cc0d 100644
--- a/setup.py
+++ b/setup.py
@@ -381,7 +381,7 @@ class TestCommand(Command):
     sub_commands = [ ('build', None) ]
 
 kw = {'name':"pycrypto",
-      'version':"2.6",  # See also: lib/Crypto/__init__.py
+      'version':"2.6.1",  # See also: lib/Crypto/__init__.py
       'description':"Cryptographic modules for Python.",
       'author':"Dwayne C. Litzenberger",
       'author_email':"dlitz@dlitz.net",