Checklist

• documentation is added or updated (RAND_add() needs to be updated)

Introduction

The broken 'RAND_add()/RAND_bytes()' pattern

In the thread [openssl-dev] Plea for a new public OpenSSL RNG API I explained in detail that the different reseeding concepts of the classic OpenSSL RNG and the new RAND_DRBG API (pushing entropy via RAND_add() vs. pulling entropy via get_entropy() callback) make it so difficult to get both APIs work together in harmony, at least as far as reseeding is concerned. The following is a brief excerpt from that thread:

In OpenSSL, the classical way for the RNG consumer to add his own randomness is to call RAND_add() before calling RAND_bytes(). If the new RAND_OpenSSL() method (the "compatibility layer" hiding the public RAND_DRBG instance) is the default, then this does not work as expected anymore:

The reason is that a call to RAND_add() adds the provided randomness only to a global buffer (rand_bytes), from which it will be pulled during the next reseed. But no reseed is triggered. So the next RAND_bytes() call will be unaffected from the RAND_add(), which is not what the consumer expected. (The same holds for RAND_seed(), since drbg_seed() only calls into drbg_add())

Reseeding of DRBGs occurs only at the following occasions:

• immediately after a fork() (new)
• if the reseed_counter exceeds the reseed_interval
• if RAND_DRBG_generate() is called requesting prediction_resistance
• RAND_DRBG_reseed() is called explicitely

Note: Currently it looks like the situation is even worse: if RAND_add() is called multiple times before a reseed occurs, then the result of the previous call is overwritten.

In this pull request I propose a solution to this problem for general discussion.

Some background information on seeding the DRBG

NIST SP 800-90Ar1 has the concept of security_strength. Currently there are three different security strengths for the CTR_DRBG, specified by the NIDs NID_aes_128_ctr, NID_aes_192_ctr, NID_aes_256_ctr. Their parameter values are hardcoded (in ctr_init()) and taken from 'Table 3: Definitions for the CTR_DRBG' on page 49 of NIST SP 800-90Ar1. In particular, there is no need to have an extra RANDOMNESS_NEEDED constant.

The role of the derivation function for seeding

The internal state of the CTR_DRBG consists of two vectors

    unsigned char K[<keylen>];
    unsigned char V[<blocklen>];

so the total number of seed bytes (seedlen in Table 3) equals seedlen = keylen + blocklen. (As mentioned earlier: in the NIST document, everything is in bits, whereas in OpenSSL, entropy is in bits, buffer lengths are in bytes).

Seeding without derivation function

If no derivation function is used, the unmodified input is used to seed (K,V). This means, one has to provide exactly seedlen=keylen+blocken bytes, which in the case of a high quality entropy source contains much more entropy than needed: 8 * seedlen > security_strength.

Seeding with derivation function

If a derivation function is used (which we always do), then the input can be of variable length between drbg->min_entropylen and drbg->max_entropylen. The DF takes a variable length input and produces a pseudorandom output from which (K,V) is seeded. This is done using AES-CTR. In some sense, the DF acts as a meat grinder, compressing the entropy of the input.

Using the derivation has two advantages: 1) min_entropylen = keylen < seedlen , so you need less input if your input has full entropy and 2) The input can be of variable size min_entropylen < inputsize < max_entropylen , which is good if your input has low entropy (say, only 2 bits per byte).

All values can be found in Table 3 and are hardcoded in ctr_init():

	int ctr_init(RAND_DRBG *drbg)
	{
		...

		ctr->keylen = keylen;
		drbg->strength = keylen * 8;
		drbg->seedlen = keylen + 16;

		if (drbg->flags & RAND_DRBG_FLAG_CTR_USE_DF) {
			/* df initialisation */
			static unsigned char df_key[32] = {
				0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,
				0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f,
				0x10,0x11,0x12,0x13,0x14,0x15,0x16,0x17,
				0x18,0x19,0x1a,0x1b,0x1c,0x1d,0x1e,0x1f
			};
			/* Set key schedule for df_key */
			AES_set_encrypt_key(df_key, drbg->strength, &ctr->df_ks);

			drbg->min_entropylen = ctr->keylen;
			drbg->max_entropylen = DRBG_MAX_LENGTH;
			drbg->min_noncelen = drbg->min_entropylen / 2;
			drbg->max_noncelen = DRBG_MAX_LENGTH;
			drbg->max_perslen = DRBG_MAX_LENGTH;
			drbg->max_adinlen = DRBG_MAX_LENGTH;
		} else {
			drbg->min_entropylen = drbg->seedlen;
			drbg->max_entropylen = drbg->seedlen;
			/* Nonce not used */
			drbg->min_noncelen = 0;
			drbg->max_noncelen = 0;
			drbg->max_perslen = drbg->seedlen;
			drbg->max_adinlen = drbg->seedlen;
		}

		...
	}

The easiest way would be if get_entropy() would allocate a buffer of length max_entropylen and fill it with bytes until the entropy threshold has been reached. However, max_entropylen = DRBG_MAX_LENGTH is an astronomically high value. But this value is only a theoretical upper limit from the NIST document. I changed this members value to a more realistic value:

	drbg->max_entropylen = 32 * drbg_min_entropylen    /* similar for adinlen, etc. */

This corresponds to the very pessimistic estimate that the entropy of the input lies between 1/4 bits-per-byte and 8 bits-per-byte. That should be enough.

Now in the callback, the buffer is filled until the required entropy threshold is reached. If the buffer overflows (which should never happen), get_entropy() fails. To facilitate this, I added a new "class" RAND_POOL which acts as container for this variable sized random input.

This is my vision of how get_entropy() should be used. Even if get_entropy() pulls from /dev/urandom or other full-entropy sources, the implementers should have the freedom to return more than the requested entropy from alternative entropy sources and/or be allowed to return cumulate low entropy input.

Summary of the pull request

The solution is split in two parts:

• Commit 1 fixes the entropy pushing part, i.e. drbg_add()
• Commit 2 fixes the entropy pulling part, i.e. drbg_get_entropy(), and restores the original semantics of RAND_poll()

This splitting is only for the moment to keep the changes overseeable and facilitate reviewing. Also, to keep things simple as long this is still WIP, I will avoid force pushing and address comments by adding new commits. I will squash the commits with a proper commit message when this goes out of WIP.

Commit 1: Make drbg_add() reseed the RAND_DRBG immediately

The obvious solution to use RAND_DRBG_reseed() creates a circular dependency, because now RAND_add() is involved both in pushing and pulling randomness:

RAND_add() -> drbg_add() -> RAND_DRBG_reseed() -> get_entropy()
                       -> get_entropy_from_system() -> RAND_poll_ex() -> RAND_add()

Using RAND_DRBG_generate() with additional input (generating and discarding some dummy output) instead of RAND_DRBG_reseed() does not solve the problem, because RAND_DRBG_generatE() can autoreseed occcasionally.

Instead, we add a new function rand_drbg_add() which is identical to RAND_DRBG_reseed(), except that it does not pull fresh entropy (and consequently does not reset the reseed_counter). This function is used only by the RAND_METHOD drbg_add().

Now the left hand side becomes:

RAND_add() -> drbg_add() -> rand_drbg_add()

The first commit breaks RAND_poll_ex(), but this function is rewritten and replaced by RAND_pool_fill() the second commit.

Commit 2: Cutting the Gordian knot: Decouple the reseeding code from the two RNG APIs

We do this by adding a new API for collecting entropy: The static fixed size RAND_BYTES_BUFFER is replaced by a more elaborate RAND_POOL "class" which acts as a container for collecting variable length randomness input for the derivation function.

The functions RAND_poll() and drbg_get_entropy() manage their own instances of such a RAND_POOL object, which they allocate and pass down the stack to the function RAND_POOL_fill() (formerly: RAND_poll_ex(). Since the lifetime and scope of these RAND_POOL objects is limited to the stack frame of RAND_poll() and drbg_get_entropy(), respectively, there is no need for locking.

Note also, that the RAND_POOL is completely decoupled from the RNG, the RAND_POOL_fill() callback has no notion which kind of RNG is reseeded from the data fed into the pool. Instead, the RAND_POOL class provides a rich API (@richsalz: no pun intended ;-) ) which appears a little oversized if one adheres to the principle that the operating system's RNG is the optimal entropy source with "full entropy" (8 bits per byte) and that it is not necessary to consider additional entropy sources or sources with lower entropy rates.

However, if one seeks for a flexible way of mixing in various entropy resources, as requested by multiple contributers, then such an API may come in handy. Currently, its just a blueprint and proof-of-concept. It provides a set of accessors providing information to the callbacks on which they could base there decisions on how much entropy should be added from the availabe resources.

I don't have a concept yet, how such a variable reseeding scheme could be managed and configured. But that's not part of this PR anyway. Input welcome, here or on openssl-dev.

Remarks

Randomness vs. Entropy

Many occurrances of the term "entropy" have been replaced by the more vague term "randomness" only recently. Although being mathematician, I have no problems using "entropy" synonymously to "randomness" in colloquial language. So originally I considered that discussion vain.

However, now this recent change change turns out to be really handy, because it enables me to consistently distinguish between a double randomness argument and a int entropy argument. The former is a floating point value measured in bytes, whereas the other is an integer value measured in bits and has a strict meaning in the sense of NIST SP800-90Ar1.

int RAND_POOL_add(RAND_POOL *pool, const void *buffer, int num, double randomness)
{
    size_t len  = (size_t)num;
    int entropy = (int)(randomness * 8.0);
    ...
}

TODO(DRBG)

Some places where I seek particular feedback or closer review have been marked with TODO(DRBG). These TODO's need to be resolved and removed before the PR can go out of WIP.

In particular, please have a closer look a the TODO(DRBG) comment preceding rand_drbg_add().

Reviewing and Testing

Since the RNG is a critical part of OpenSSL, any change to the code is like an open heart surgery. I'm not a seasoned committer and don't have the resources to test it on all platforms and under all circumstances. So I am grateful for any independent testing, in particular the DRBG chaining and forking stuff, since I a am only familiar with libcrypto and not such with libssl.

What I tested: I successfully ran the standard tests and did a little debugging with gdb to check the main code paths:

# global DRBG, fetching entropy from os for instantiation     (break at rbg_get_entropy)
./util/shlib_wrap.sh gdb --args ./apps/openssl rand -hex 32

# chained DRBG, fetching entropy from parent DRBGfor instantiation   (break at drbg_get_entropy, then add breakpoint inside 'if (drbg->parent)'-clause)
./util/shlib_wrap.sh gdb --args ./apps/openssl s_client -host www.openssl.org -port 443

# global DRBG, RAND_add()         (break at drbg_add)
echo 'This is a random number' > /tmp/randfile
./util/shlib_wrap.sh gdb --args ./apps/openssl rand -hex -rand /tmp/randfile  12

# test
./util/shlib_wrap.sh gdb --args ./test/drbgtest