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.
Fortuna: Add comments for reseed_interval and min_pool_size to FortunaAccumulator
Update the ChangeLog
Release v2.6.1

This release is identical to PyCrypto v2.6, except it fixes the
Crypto.Random race condition (CVE-2013-1445) and adds a few related
comments.
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
whitespace changes (pre-AEAD)

[dlitz@dlitz.net: Whitespace changes extracted from the author's pull request:]
- [9c13f9c] Rename 'IV' parameter to 'nonce' for AEAD modes.
- [4ec64d8] Removed last references to ApiUsageError
- [ee46922] Removed most 'import *' statements
Made blockalgo.py more PEP-8 compliant (pre-AEAD)

[dlitz@dlitz.net: Original commit was:]

commit ca460a79aecdbf6e5973e99f8bdbf3888b6d34d2
Author: Legrandin <helderijs@gmail.com>
Date:   Sun Aug 4 22:46:06 2013 +0200

    Made blockalgo.py more PEP-8 compliant

    The second parameter of the _GHASH constructor
    is now the length of the block (block_size)
    and not the full module.

[dlitz@dlitz.net: Included only style-related changes that apply cleanly to the master branch (pre-AEAD)]
[dlitz@dlitz.net: Omitted functional changes that were made in the author's original commit.]
[dlitz@dlitz.net: Omitted some changes that broke exception messages onto multiple lines.]
[dlitz@dlitz.net: Omitted some changes that broke arithmetic expressions onto multiple lines.]
Add HMAC.verify() and HMAC.hexverify() with constant-time comparison

In the current implementation, it is left up to the caller
to assess if the locally computed MAC matches the MAC associated
to the received message.

However, the most natural way to do that (use == operator)
is also deepy unsecure, see here:

http://seb.dbzteam.org/crypto/python-oauth-timing-hmac.pdf

With this patch, the new HMAC.verify() method accepts
the given MAC and perform the check on behalf of the caller.
The method will use constant-time code (still dependent on the length
of the MAC, but not on the actual content).

[dlitz@dlitz.net: Modified commit message subject line.]
[dlitz@dlitz.net: Whitespace fixed with "git rebase --whitespace=fix"]
MAC unit tests become independent of hashes

The MAC unit tests assume that the MAC algorithm is
based on hash functions (HMAC).
Additionally, a single test vector is quite complex
in that it includes result for multiple tests (each
performed on the same data, but with different
hashes).

This patch simplifies the MAC unit test so that it does
not depend on hashes and a test vector is simply made up by:
* 1 input
* 1 result
* All parameters to pass to the new() function

[dlitz@dlitz.net: Replaced custom MacMismatchError with ValueError.]
[dlitz@dlitz.net: Replaced 'import *' with appropriate imports.]
[dlitz@dlitz.net: Whitespace fixed with "git rebase --whitespace=fix"]
Clarify message about incorrect length in the counter block.

When the counter function returns an incorrect counter block to
the cipher in CTR mode, the error message includes both the required and
the provided amount of data (in bytes).
blockalgo: Fix MODE_OPENPGP comment

[dlitz@dlitz.net: Extracted from the following commit:]
    commit 5306cf38ba060a70e5397ec48a5cea00c2bf0203
    Author: Legrandin <helderijs@gmail.com>
    Date:   Wed Jan 23 22:37:53 2013 +0100

        Added support for CCM mode (AES cipher only)
Added KDF unit tests to suite
Removed most 'import *' statements

[dlitz@dlitz.net: Re-ordered commits; so don't import S2V yet]
[dlitz@dlitz.net: Included an additional 'import *' change from the following commit:]
    commit 4ec64d8eaaa4965889eb8e3b801fc77aa84e0a4e
    Author: Legrandin <helderijs@gmail.com>
    Date:   Tue Sep 10 07:28:08 2013 +0200

        Removed last references to ApiUsageError

[dlitz@dlitz.net: Removed unrelated whitespace changes]
Add CTR mode benchmark
Add support for CMAC

This patch adds support for CMAC (RFC4493, NIST SP800-38B).

[dlitz@dlitz.net: Replaced MacMismatchError with ValueError]
[dlitz@dlitz.net: Whitespace fixed with "git rebase --whitespace=fix"]
Add support for CCM mode (AES only).

[dlitz@dlitz.net: Included changes from the following commits from the author's pull request:]
- [5306cf3] Added support for CCM mode (AES cipher only)
- [9abe301] Added CCM tests
- [f0c1395] Add MacMismatchError and ApiUsageError
- [fb62fae] ApiUsageError becomes TypeError
- [9c13f9c] Rename 'IV' parameter to 'nonce' for AEAD modes.
- [4ec64d8] Removed last references to ApiUsageError
- [80bfd35] Corrected AES-CCM examples
[dlitz@dlitz.net: Removed unrelated documentation change]
[dlitz@dlitz.net: Renamed 'targs' back to 'args']
[dlitz@dlitz.net: Whitespace fixed with "git rebase --whitespace=fix"]
Add EAX authenticated encryption mode

[dlitz@dlitz.net: Included changes from the following commits from the author's pull request:]
- [9c13f9c] Rename 'IV' parameter to 'nonce' for AEAD modes.
- [ca460a7] Made blockalgo.py more PEP-8 compliant; The second parameter
            of the _GHASH constructor is now the length of the block
            (block_size) and not the full module.
[dlitz@dlitz.net: Fixed unresolved conflict in lib/Crypto/Cipher/blockalgo.py]
Add support for SIV (Synthetic IV) mode

This patch add supports for SIV, an AEAD block cipher
mode defined in RFC5297. SIV is only valid for AES.

The PRF of SIV (S2V) is factored out in the Protocol.KDF module.

See the following example to get a feeling of the API (slightly
different than other AEAD mode, during decryption).

Encryption (Python 2):

	>>> from Crypto.Cipher import AES
	>>> key = b'0'*32
	>>> siv = AES.new(key, AES.MODE_SIV)
	>>> ct  = siv.encrypt(b'Message')
	>>> mac = siv.digest()

Decryption (Python 2):

	>>> from Crypto.Cipher import AES, MacMismatchError
	>>> key = b'0'*32
	>>> siv = AES.new(key, AES.MODE_SIV)
	>>> pt  = siv.decrypt(ct + mac)
	>>> try:
	>>>	siv.verify(mac)
	>>>	print "Plaintext", pt
	>>> except MacMismatchError:
	>>>     print "Error"

This change also fixes the description/design of AEAD API.

With SIV (RFC5297), decryption can only start when the MAC is known.
The original AEAD API did not support that.

For SIV the MAC is now exceptionally passed together with the ciphertext
to the decrypt() method.

[dlitz@dlitz.net: Included changes from the following commits from the author's pull request:]
- [9c13f9c] Rename 'IV' parameter to 'nonce' for AEAD modes.
- [d7727fb] Fix description/design of AEAD API.
- [fb62fae] ApiUsageError becomes TypeError [whitespace]
- [4ec64d8] Removed last references to ApiUsageError [whitespace]
- [ee46922] Removed most 'import *' statements
- [ca460a7] Made blockalgo.py more PEP-8 compliant;
            The second parameter of the _GHASH constructor
            is now the length of the block (block_size)
            and not the full module.
[dlitz@dlitz.net: A conflict that was not resolved in the previous
                  commit was originally resolved here.  Moved the
                  resolution to the previous commit.]
[dlitz@dlitz.net: Replaced MacMismatchError with ValueError]
[dlitz@dlitz.net: Replaced ApiUsageError with TypeError]
[dlitz@dlitz.net: Whitespace fixed with "git rebase --whitespace=fix"]
Add support for GCM mode (AES only).

The main change done by this commit is adding support
for MODE_GCM (NIST SP 800 38D). Test vectors are included.

The mode uses a C extension (Crypto.Util.galois._ghash)
to compute the GHASH step. The C implementation is the most
basic one and it is still significantly (5x times) slower than CTR.
Optimizations can be introduced using tables (CPU/memory trade-off)
or even AES NI instructions on newer x86 CPUs.

This patch also simplifies Crypto.Cipher.blockalgo.py by:
 * removing duplicated code previously shared by digest() and verify().
 * removing duplicated code previously shared by Crypto.Hash.CMAC
   and Crypto.Cipher.block_algo (management of internal buffers
   for MACs that can only operate on block aligned data, like
   CMAC, CBCMAC, and now also GHASH).

[dlitz@dlitz.net: Included changes from the following commits from the author's pull request:]
- [9c13f9c] Rename 'IV' parameter to 'nonce' for AEAD modes.
- [ca460a7] Made blockalgo.py more PEP-8 compliant;
            The second parameter of the _GHASH constructor
            is now the length of the block (block_size)
            and not the full module.
[dlitz@dlitz.net: Replaced MacMismatchError with ValueError]
[dlitz@dlitz.net: Replaced ApiUsageError with TypeError]
[dlitz@dlitz.net: Replaced renamed variable `ht` with original `h`]
[dlitz@dlitz.net: Whitespace fixed with "git rebase --whitespace=fix"]
Add key setup speed benchmark for all AEAD modes.