Random: Make Crypto.Random.atfork() set last_reseed=None (CVE-2013-1445)

== Summary ==

In PyCrypto before v2.6.1, the Crypto.Random pseudo-random number
generator (PRNG) exhibits a race condition that may cause it to generate
the same 'random' output in multiple processes that are forked from each
other.  Depending on the application, this could reveal sensitive
information or cryptographic keys to remote attackers.

An application may be affected if, within 100 milliseconds, it performs
the following steps (which may be summarized as "read-fork-read-read"):

1. Read from the Crypto.Random PRNG, causing an internal reseed;
2. Fork the process and invoke Crypto.Random.atfork() in the child;
3. Read from the Crypto.Random PRNG again, in at least two different
   processes (parent and child, or multiple children).

Only applications that invoke Crypto.Random.atfork() and perform the
above steps are affected by this issue.  Other applications are
unaffected.

Note: Some PyCrypto functions, such as key generation and PKCS#1-related
functions, implicitly read from the Crypto.Random PRNG.

== Technical details ==

Crypto.Random uses Fortuna[1] to generate random numbers.  The flow of
entropy looks something like this:

    /dev/urandom  -\
                    +-> "accumulator" --> "generator" --> output
    other sources -/   (entropy pools)     (AES-CTR)

- The "accumulator" maintains several pools that collect entropy from
  the environment.

- The "generator" is a deterministic PRNG that is reseeded by the
  accumulator.  Reseeding normally occurs during each request for random
  numbers, but never more than once every 100 ms (the "minimum reseed
  interval").

When a process is forked, the parent's state is duplicated in the child.
In order to continue using the PRNG, the child process must invoke
Crypto.Random.atfork(), which collects new entropy from /dev/urandom and
adds it to the accumulator.  When new PRNG output is subsequently
requested, some of the new entropy in the accumulator is used to reseed
the generator, causing the output of the child to diverge from its
parent.

However, in previous versions of PyCrypto, Crypto.Random.atfork() did
not explicitly reset the child's rate-limiter, so if the child requested
PRNG output before the minimum reseed interval of 100 ms had elapsed, it
would generate its output using state inherited from its parent.

This created a race condition between the parent process and its forked
children that could cause them to produce identical PRNG output for the
duration of the 100 ms minimum reseed interval.

== Demonstration ==

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']

== Solution ==

The solution is to upgrade to PyCrypto v2.6.1 or later, which properly
resets the rate-limiter when Crypto.Random.atfork() is invoked in the
child.

== References ==

[1] N. Ferguson and B. Schneier, _Practical Cryptography_,
    Indianapolis: Wiley, 2003, pp. 155-184.

1 files changed, 15 insertions, 0 deletions

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