Adaptive Code via C#. Agile coding with design patterns and SOLID principles (2014)

---

^[1^] If you want to interoperate with such platforms (there are still plenty of systems without /dev/random and /dev/urandom), that reinforces the utility of using our API; simply link against code that implements our API using the solution from Recipe 11.8 instead of the solution from this recipe.

11.4. Using the Standard Windows Randomness Infrastructure

Problem

You want to use random numbers on a Windows system.

Solution

Use CryptGenRandom( ) unless you absolutely need entropy, in which case see Recipe 11.8 and Recipe 11.20 through Recipe 11.23.

Discussion

Microsoft allows you to get cryptographically strong pseudo-random numbers using the CryptoAPI function CryptGenRandom( ). Unfortunately, there is no provision for any way to get entropy. The system does collect entropy behind the scenes, which it uses to improve the quality of the cryptographically strong pseudo-random numbers it gets.

Therefore, if this interface is being used to bind to the API we describe in Recipe 11.2, we can only implement spc_rand( ) and spc_keygen( ), both of which will be exactly the same. If you want to try to get actual entropy on Windows, the only solution as of this writing is to use EGADS, which we discuss in Recipe 11.8. Alternatively, you can collect it yourself, as discussed in Recipe 11.20 through Recipe 11.23.

To use CryptGenRand( ), you must first acquire an HCRYPTPROV context. To do this, use the function CryptAcquireContext( ) , which we discuss in some detail in Recipe 5.25. With an HCRYPTPROV context in hand, you can call CryptGenRandom( ) , which will return TRUE if it is successful; otherwise, it will return FALSE, but it should never fail. CryptGenRandom( ) has the following signature:

BOOL CryptGenRandom(HCRYPTPROV *hProv, DWORD dwLen, BYTE *pbBuffer);

This function has the following arguments:

hProv

Handle to a cryptographic service provider obtained via CryptAcquireContext( ).

dwLen

Number of bytes of random data required. The output buffer must be at least this large.

pbBuffer

Buffer into which the random data will be written.

Here we show how to use this function by binding it to the API from Recipe 11.2:

#include <windows.h>

#include <wincrypt.h>

static HCRYPTPROV hProvider;

void spc_rand_init(void) {

if (!CryptAcquireContext(&hProvider, 0, 0, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT))

ExitProcess((UINT)-1); /* Feel free to properly signal an error instead. */

}

unsigned char *spc_rand(unsigned char *pbBuffer, size_t cbBuffer) {

if (!hProvider) spc_rand_init( );

if (!CryptGenRandom(hProvider, cbBuffer, pbBuffer))

ExitProcess((UINT)-1); /* Feel free to properly signal an error instead. */

return pbBuffer;

}

unsigned char *spc_keygen(unsigned char *pbBuffer, size_t cbBuffer) {

if (!hProvider) spc_rand_init( );

if (!CryptGenRandom(hProvider, cbBuffer, pbBuffer))

ExitProcess((UINT)-1);

return pbBuffer;

}

See Also

Recipe 5.25, Recipe 11.2, Recipe 11.8, Recipe 11.20, Recipe 11.21, Recipe 11.22, Recipe 11.23

11.5. Using an Application-Level Generator

Problem

You are in an environment where you do not have access to a built-in, cryptographically strong pseudo-random number generator. You have obtained enough entropy to seed a pseudo-random generator, but you lack a generator.

Solution

For general-purpose use, we recommend a pseudo-random number generator based on the AES encryption algorithm run in counter (CTR) mode (see Recipe 5.9). This generator has the best theoretical security assurance, assuming that the underlying cryptographic primitive is secure. If you would prefer a generator based on a hash function, you can run HMAC-SHA1 (see Recipe 6.10) in counter mode.

In addition, the keystream of a secure stream cipher can be used as a pseudo-random number generator.

Discussion

Stream ciphers are actually cryptographic pseudo-random number generators. One major practical differentiator between the two terms is whether you are using the output of the generator to perform encryption. If you are, it is a stream cipher; otherwise, it is a cryptographic pseudo-random number generator.

Another difference is that, when you are using a stream cipher to encrypt data, you need to be able to reproduce the same stream of output to decrypt the encrypted data. With a cryptographic PRNG, there is generally no need to be able to reproduce a data stream. Therefore, the generator can be reseeded at any time to help protect against internal state guessing attacks, which is analogous to rekeying a stream cipher.

The primary concern with a good cryptographic PRNG at the application level is internal state compromise, which would allow an attacker to predict its output. As long as the cryptographic algorithms used by a PRNG are not broken and the generator is not used to produce more output than it is designed to support, state compromise is generally not feasible by simply looking at the generator's output. The number of outputs supported by a generator varies based on the best attacks possible for whatever cryptographic algorithms are in use.

The risk of state compromise is generally not a big deal when dealing with something like /dev/random, where the generator is in the kernel. The only way to compromise the state is to be inside the kernel. If that's possible, there are much bigger problems than /dev/urandom orCryptGenRandom( ) producing data that an attacker can guess.

In the user space, state compromise may be more of an issue, though. You need to work through the threats about which you are worried. Threats are likely to come only from code on the local machine, but what code? Are you worried about malicious applications running with the same permissions being able to somehow peer inside the current process to get the internal state? If so, perhaps you should have a separate process that only provides entropy and runs with a set of permissions where only itself and the superuser would be a concern (this is the recommended approach for using the EGADS package discussed in Recipe 11.8).

If state compromise is a potential issue, you might have to worry about more than an attacker guessing future outputs. You might also have to worry about an attacker backtracking, which means compromising previous outputs the generator made. Reseeding the generator periodically, as discussed in Recipe 11.6, can solve this problem. At best, an attacker should only be able to backtrack to the last reseeding (you can reseed without new entropy to mix in).

In practice, few people should have to worry very much about state compromise of their cryptographic PRNG. As was the case at the operating system level, if such attacks are a realistic threat, you will usually have far bigger threats, and mitigating those threats will help mitigate this one as well.

There is a lot that can go wrong when using a pseudo-random number generator. Coming up with a good construct turns out to be the easy part. Here are some things you should closely consider:

§ Pseudo-random number generators need to be seeded with an adequate amount of entropy; otherwise, they are still potentially predictable. We recommend at least 80 bits. See the various recipes elsewhere in this chapter for information on collecting entropy.

§ Be careful to pay attention to the maximum number of outputs a generator can produce before it will need to be reseeded with new entropy. At some point, generators start to leak information and will generally fall into a cycle. Note, though, that for the configurations we present, you will probably never need to worry about the limit in practice. For example, the generator based on AES-128 leaks a bit of information after 2⁶⁴ 16-byte blocks of output, and cycles after 2¹²⁸ such blocks.

§ When adding entropy to a system, it is best to collect a lot of entropy and seed all at once, instead of seeding a little bit at a time. We will illustrate why by example. Suppose that you seed a generator with one bit of entropy. An attacker has only one bit to guess, which can be done accurately after two outputs. If the attacker completely compromises the state after two outputs, and we then add another bit of entropy, he can once again guess the state easily. If we add one bit 128 times, there is still very little security overall if the generator state is compromised. However, if you add 128 bits of entropy to the generator all at once, an attack should essentially be infeasible.

§ If an attacker can somehow compromise the internal state of a pseudo-random number generator, then it might be possible to launch a backtracking attack, where old generator outputs can be recovered. Such attacks are easy to thwart; see Recipe 11.6.

In the following three subsections, we will look at three different techniques for pseudo-random number generators: using a block cipher such as AES, using a stream cipher directly, and using a cryptographic hash function such as SHA1.

Using generators based on block ciphers

If you are in an environment where you have use of a good block cipher such as AES, you have the makings of a cryptographically strong pseudo-random number generator. Many of the encryption modes for turning a block cipher into a stream cipher are useful for this task, but CTR mode has the nicest properties. Essentially, you create random outputs one block at a time by encrypting a counter that is incremented after every encryption operation.

The seed should be at least as large as the key size of the cipher, because it will be used to key a block cipher. In addition, it is useful to have additional seed data that sets the first plaintext (counter) value.

Our implementation is based on the code in Recipe 5.5 and has two exported routines. The first initializes a random number generator:

void spc_bcprng_init(SPC_BCPRNG_CTX *prng, unsigned char *key, int kl,

unsigned char *x, int xl);

This function has the following arguments:

prng

Pointer to a context object that holds the state for a block cipher-based PRNG. The caller may allocate the context object either dynamically or statically; this function will initialize it.

key

Buffer that should contain entropic data. This data is used to key the block cipher, and it is the required portion of the seed to the generator.

kl

Length of the key buffer in bytes; must be a valid value for the algorithm in use.

x

Buffer that may contain extra seed data, which we recommend you use if you have available entropy. If the specified size of this buffer is zero, this argument will be ignored. Note that if the buffer is larger than SPC_BLOCK_LEN (see Recipe 5.5) any additional data in the buffer will be ignored. Therefore, if you have sparse amounts of entropy, compress it to the right length before calling this function, as discussed in Recipe 11.16.

xl

Length of the extra seed buffer in bytes. It may be specified as zero to indicate that there is no extra seed data.

Once you have an instantiated generator, you can get cryptographically strong pseudo-random data from it with the following function:

unsigned char *spc_bcprng_rand(SPC_BCPRNG_CTX *prng, unsigned char *buf, size_t l);

This function has the following arguments:

prng

Pointer to the generator's context object.

buf

Buffer into which the random data will be written.

l

Number of bytes that should be placed into the output buffer.

This function never fails (save for a catastrophic error in encryption), and it returns the address of the output buffer.

Here is an implementation of this generator API, which makes use of the block cipher interface we developed in Recipe 5.5:

/* NOTE: This code should be augmented to reseed after each request

/* for pseudo-random data, as discussed in Recipe 11.6

/*

#ifndef WIN32

#include <string.h>

#include <pthread.h>

#else

#include <windows.h>

#endif

/* if encryption operations fail, you passed in a bad key size or are using a

* hardware API that failed. In that case, be sure to perform error checking.

*/

typedef struct {

SPC_KEY_SCHED ks;

unsigned char ctr[SPC_BLOCK_SZ];

unsigned char lo[SPC_BLOCK_SZ]; /* Leftover block of output */

int ix; /* index into lo */

int kl; /* The length of key used to key the cipher */

} SPC_BCPRNG_CTX;

#ifndef WIN32

static pthread_mutex_t spc_bcprng_mutex = PTHREAD_MUTEX_INITIALIZER;

#define SPC_BCPRNG_LOCK( ) pthread_mutex_lock(&spc_bcprng_mutex);

#define SPC_BCPRNG_UNLOCK( ) pthread_mutex_unlock(&spc_bcprng_mutex);

#else

static HANDLE hSpcBCPRNGMutex;

#define SPC_BCPRNG_LOCK( ) WaitForSingleObject(hSpcBCPRNGMutex, INFINITE)

#define SPC_BCPRNG_UNLOCK( ) ReleaseMutex(hSpcBCPRNGMutex)

#endif

static void spc_increment_counter(SPC_BCPRNG_CTX *prng) {

int i = SPC_BLOCK_SZ;

while (i--)

if (++prng->ctr[i]) return;

}

void spc_bcprng_init(SPC_BCPRNG_CTX *prng, unsigned char *key, int kl,

unsigned char *x, int xl) {

int i = 0;

SPC_BCPRNG_LOCK( );

SPC_ENCRYPT_INIT(&(prng->ks), key, kl);

memset(prng->ctr, 0, SPC_BLOCK_SZ);

while (xl-- && i < SPC_BLOCK_SZ)

prng->ctr[i++] = *x++;

prng->ix = 0;

prng->kl = kl;

SPC_BCPRNG_UNLOCK( );

}

unsigned char *spc_bcprng_rand(SPC_BCPRNG_CTX *prng, unsigned char *buf, size_t l) {

unsigned char *p;

SPC_BCPRNG_LOCK( );

for (p = buf; prng->ix && l; l--) {

*p++ = prng->lo[prng->ix++];

prng->ix %= SPC_BLOCK_SZ;

}

while (l >= SPC_BLOCK_SZ) {

SPC_DO_ENCRYPT(&(prng->ks), prng->ctr, p);

spc_increment_counter(prng);

p += SPC_BLOCK_SZ;

l -= SPC_BLOCK_SZ;

}

if (l) {

SPC_DO_ENCRYPT(&(prng->ks), prng->ctr, prng->lo);

spc_increment_counter(prng);

prng->ix = l;

while (l--) p[l] = prng->lo[l];

}

SPC_BCPRNG_UNLOCK( );

return buf;

}

If your block cipher has 64-bit blocks and has no practical weaknesses, do not use this generator for more than 2³⁵ bytes of output (2³² block cipher calls). If the cipher has 128-bit blocks, do not exceed 2⁶⁸ bytes of output (2⁶⁴ block cipher calls). If using a 128-bit block cipher, it is generally acceptable not to check for this condition, as you generally would not reasonably expect to ever use that many bytes of output.

To bind this cryptographic PRNG to the API in Recipe 11.2, you can use a single global generator context that you seed in spc_rand_init( ) , requiring you to get a secure seed. Once that's done (assuming the generator variable is a statically allocated global variable named spc_prng), you can simply implement spc_rand( ) as follows:

unsigned char *spc_rand(unsigned char *buf, size_t l) {

return spc_bcprng_rand(&spc_prng, buf, l);

}

Note that you should probably be sure to check that the generator is seeded before calling spc_bcprng_rand( ).

Using a stream cipher as a generator

As we mentioned, stream ciphers are themselves pseudo-random number generators, where the key (and the initialization vector, if appropriate) constitutes the seed. If you are planning to use such a cipher, we strongly recommend the SNOW 2.0 cipher, discussed in Recipe 5.2.

Because of the popularity of the RC4 cipher, we expect that people will prefer to use RC4, even though it does not look as good as SNOW. The RC4 stream cipher does make an acceptable pseudo-random number generator, and it is incredibly fast if you do not rekey frequently (that is particularly useful if you expect to need a heck of a lot of numbers). If you do rekey frequently to avoid backtracking attacks, a block cipher-based approach may be faster; time it to make sure.

RC4 requires a little bit of work to use properly, given a standard API. First, most APIs want you to pass in data to encrypt. Because you want only the raw keystream, you must always pass in zeros. Second, be sure to use RC4 in a secure manner, as discussed in Recipe 5.23.

If your RC4 implementation has the API discussed in Recipe 5.23, seeding it as a pseudo-random number generator is the same as keying the algorithm. RC4 can accept keys up to 256 bytes in length.

WARNING

Because of limitations in RC4, you should throw away the first 256 bytes of RC4 output, as discussed in Recipe 5.23.

After encrypting 256 bytes and throwing the results away, you can then, given an RC4 context, get random data by encrypting zeros. Assuming the RC4 API from Recipe 5.23 and assuming you have a context statically allocated in a global variable named spc_prng, here's a binding of RC4 to the spc_rand( ) function that we introduced in Recipe 11.2:

/* NOTE: This code should be augmented to reseed after each request

/* for pseudo-random data, as discussed in Recipe 11.6

/*

#ifndef WIN32

#include <pthread.h>

static pthread_mutex_t spc_rc4rng_mutex = PTHREAD_MUTEX_INITIALIZER;

#define SPC_RC4RNG_LOCK( ) pthread_mutex_lock(&spc_rc4rng_mutex)

#define SPC_RC4RNG_UNLOCK( ) pthread_mutex_unlock(&spc_rc4rng_mutex)

#else

#include <windows.h>

static HANDLE hSpcRC4RNGMutex;

#define SPC_RC4RNG_LOCK( ) WaitForSingleObject(hSpcRC4RNGMutex, INFINITE)

#define SPC_RC4RNG_UNLOCK( ) ReleaseMutex(hSpcRC4RNGMutex)

#endif

#define SPC_ARBITRARY_SIZE 16

unsigned char *spc_rand(unsigned char *buf, size_t l) {

static unsigned char zeros[SPC_ARBITRARY_SIZE] = {0,};

unsigned char *p = buf;

#ifdef WIN32

if (!hSpcRC4RNGMutex) hSpcRC4RNGMutex = CreateMutex(0, FALSE, 0);

#endif

SPC_RC4RNG_LOCK( );

while (l >= SPC_ARBITRARY_SIZE) {

RC4(&spc_prng, SPC_ARBITRARY_SIZE, zeros, p);

l -= SPC_ARBITRARY_SIZE;

p += SPC_ARBITRARY_SIZE;

}

if (l) RC4(&spc_prng, l, zeros, p);

SPC_RC4RNG_UNLOCK( );

return buf;

}

Note that, although we don't show it in this code, you should ensure that the generator is initialized before giving output.

Because using this RC4 API requires encrypting zero bytes to get the keystream output, in order to be able to generate data of arbitrary sizes, you must either dynamically allocate and zero out memory every time or iteratively call RC4 in chunks of up to a fixed size using a static buffer filled with zeros. We opt for the latter approach.

WARNING

RC4 is only believed to be a strong source of random numbers for about 2³⁰ outputs. After that, we strongly recommend that you reseed it with new entropy. If your application would not conceivably use that many outputs, it should generally be okay not to check that condition.

Using a generator based on a cryptographic hash function

The most common mistake made when trying to use a hash function as a cryptographic pseudo-random number generator is to continually hash a piece of data. Such an approach gives away the generator's internal state with every output. For example, suppose that your internal state is some value X, and you generate and output Y by hashing X. The next time you need random data, rehashing X will give the same results, and any attacker who knows the last outputs from the generator can figure out the next outputs if you generate them by hashing Y.

One very safe way to use a cryptographic hash function in a cryptographic pseudo-random number generator is to use HMAC in counter mode, as discussed in Recipe 6.10. Here we implement a generator based on the HMAC-SHA1 implementation from Recipe 6.10. You should be able to adapt this code easily to any HMAC implementation you want to use.

/* NOTE: This code should be augmented to reseed after each request

/* for pseudo-random data, as discussed in Recipe 11.6

/*

#ifndef WIN32

#include <string.h>

#include <pthread.h>

#else

#include <windows.h>

#endif

/* If MAC operations fail, you passed in a bad key size or you are using a hardware

* API that failed. In that case, be sure to perform error checking.

*/

#define MAC_OUT_SZ 20

typedef struct {

SPC_HMAC_CTX ctx;

unsigned char ctr[MAC_OUT_SZ];

unsigned char lo[MAC_OUT_SZ]; /* Leftover block of output */

int ix; /* index into lo. */

} SPC_MPRNG_CTX;

#ifndef WIN32

static pthread_mutex_t spc_mprng_mutex = PTHREAD_MUTEX_INITIALIZER;

#define SPC_MPRNG_LOCK( ) pthread_mutex_lock(&spc_mprng_mutex)

#define SPC_MPRNG_UNLOCK( ) pthread_mutex_unlock(&spc_mprng_mutex)

#else

static HANDLE hSpcMPRNGMutex;

#define SPC_MPRNG_LOCK( ) WaitForSingleObject(hSpcMPRNGMutex, INFINITE)

#define SPC_MPRNG_UNLOCK( ) ReleaseMutex(hSpcMPRNGMutex)

#endif

static void spc_increment_mcounter(SPC_MPRNG_CTX *prng) {

int i = MAC_OUT_SZ;

while (i--)

if (++prng->ctr[i])

return;

}

void spc_mprng_init(SPC_MPRNG_CTX *prng, unsigned char *seed, int l) {

SPC_MPRNG_LOCK( );

SPC_HMAC_Init(&(prng->ctx), seed, l);

memset(prng->ctr, 0, MAC_OUT_SZ);

prng->ix = 0;

SPC_MPRNG_UNLOCK( );

}

unsigned char *spc_mprng_rand(SPC_MPRNG_CTX *prng, unsigned char *buf, size_t l) {

unsigned char *p;

SPC_MPRNG_LOCK( );

for (p = buf; prng->ix && l; l--) {

*p++ = prng->lo[prng->ix++];

prng->ix %= MAC_OUT_SZ;

}

while (l >= MAC_OUT_SZ) {

SPC_HMAC_Reset(&(prng->ctx));

SPC_HMAC_Update(&(prng->ctx), prng->ctr, sizeof(prng->ctr));

SPC_HMAC_Final(p, &(prng->ctx));

spc_increment_mcounter(prng);

p += MAC_OUT_SZ;

l -= MAC_OUT_SZ;

}

if (l) {

SPC_HMAC_Reset(&(prng->ctx));

SPC_HMAC_Update(&(prng->ctx), prng->ctr, sizeof(prng->ctr));

SPC_HMAC_Final(prng->lo, &(prng->ctx));

spc_increment_mcounter(prng);

prng->ix = l;

while (l--) p[l] = prng->lo[l];

}

SPC_MPRNG_UNLOCK( );

return buf;

}

This implementation has two publicly exported functions. The first initializes the generator:

void spc_mprng_init(SPC_MPRNG_CTX *prng, unsigned char *seed, int l);

This function has the following arguments:

prng

Context object used to hold the state for a MAC-based PRNG.

seed

Buffer containing data that should be filled with entropy (the seed). This data is used to key the MAC.

l

Length of the seed buffer in bytes.

The second function actually produces random data:

unsigned char *spc_mprng_rand(SPC_MPRNG_CTX *prng, unsigned char *buf, size_t l);

This function has the following arguments:

prng

Context object used to hold the state for a MAC-based PRNG.

out

Buffer into which the random data will be placed.

l

Number of random bytes to be placed into the output buffer.

If your hash function produces n-bit outputs and has no practical weaknesses, do not use the generator after you run the MAC more than 2n ^/2 times. For example, with SHA1, this generator should be not be a problem for at least 2⁸⁰ × 20 bytes. In practice, you probably will not have to worry about this issue.

To bind this cryptographic pseudo-random number generator to the API in Recipe 11.2, you can use a single global generator context that you seed in spc_rand_init( ), requiring you to get a secure seed. Once that is done (assuming the generator variable is a statically allocated global variable named spc_prng), you can simply implement spc_rand( ) as follows:

unsigned char *spc_rand(unsigned char *buf, size_t l) {

return spc_bcprng_rand(&spc_prng, buf, l);

}

Note that, although we don't show it in the previous code, you should ensure that the generator is initialized before giving output.

See Also

Recipe 5.2, Recipe 5.5, Recipe 5.9, Recipe 5.23, Recipe 6.10, Recipe 11.2, Recipe 11.6, Recipe 11.8, Recipe 11.16

11.6. Reseeding a Pseudo-Random Number Generator

Problem

You have an application-level pseudo-random number generator such as the ones presented in Recipe 11.5, and you want to reseed it, either because you have new entropy to mix in or because you would like to prevent against backtracking attacks.

Solution

Create a new seed by getting a sufficient number of bytes from the generator to seed the generator. If mixing in entropy, compress the entropy down to the seed size if necessary, as discussed in Recipe 11.16, then XOR the compressed seed with the generator output. Finally, reseed the generator with the resulting value.

Discussion

There are two common reasons why you may want to reseed a PRNG. First, your threat model may include the possibility of the internal state of your PRNG being compromised, and you want to prevent against an attacker's being able to figure out numbers that were output before the state compromise. Reseeding, if done right, essentially transforms the internal state in a way that preserves entropy while making it essentially impossible to backtrack. Protecting against backtracking attacks can be done cheaply enough, so there is no excuse for not doing it.

Second, you may want to add entropy into the state. This could serve a number of purposes. For example, you might want to add entropy to the system. Remember, however, that cryptographic generators have a maximum amount of entropy they can contain, so adding entropy to a generator state can look unnecessary.

When available, however, reseeding with entropy is a good conservative measure, for several reasons. For one reason, if you have underestimated the amount of entropy that a generator has, adding entropy is a good thing. For another, if the generator has lost any entropy, new entropy can help replenish it. Such entropy loss is natural because cryptographic algorithms are not as good as their theoretical ideals. In addition, because we generally do not know the exact strength of our algorithms, it is hard to determine how quickly entropy gets lost. (Note, however, that if the algorithms are as strong as believed, it should be quite slowly.)

While a generator based on AES or HMAC-SHA1, implemented as discussed in Recipe 11.5, probably never loses more than a miniscule amount of entropy before 2⁶⁴ outputs, it is always good to be conservative and assume that it drains quickly, particularly if you have entropy to spare.

WARNING

When adding entropy to a system, it is best to collect a lot of entropy and seed all at once, instead of seeding a little bit at a time. We will illustrate why by example. Suppose you seed a generator with one bit of entropy. An attacker has only one bit to guess, which can be done accurately after two outputs. If the attacker completely compromises the state after two outputs, and we then add another bit of entropy, he can once again guess the state easily.

If we add one bit 128 times, there is still very little security overall if the generator state is compromised. However, if you add 128 bits of entropy to the generator all at once, an attack should essentially be infeasible.

The actions you should take to reseed a generator are different depending on whether you are actually adding entropy to the state of the generator or just trying to thwart a backtracking attack. However, the first step is the same in both cases.

1. Figure out how big a seed you need. At the very least, you need a seed that is as many bits in length as bits of entropy you think are in the generator. Generally, this will be at least as large as the key size of the underlying primitive (or the output size when using a one-way hash function instead of a cipher).

2. If you need to introduce new entropy, properly compress the data containing entropy. In particular, you must transform the data into a seed of the proper size, with minimal loss of entropy. One easy way to do that is to process the string with a cryptographic hash function (truncating the hash output to the desired length, if necessary). Then XOR the compressed entropy with the seed output by the generator.

3. Take the value and use it to reseed the generator. If you are using a counter-based generator, you can either reset the counter or choose not to do so. In fact, it is preferable to take a bit of extra output from the generator so that the counter can be set to a random value.

For example, using the block cipher-based PRNG from Recipe 11.5, here is a function that reseeds the generator, given new, uncompressed data containing entropy:

void spc_bcprng_reseed(SPC_BCPRNG_CTX *prng, unsigned char *new_data, size_t l) {

size_t i;

unsigned char m[SPC_MAX_KEYLEN + SPC_BLOCK_SZ];

SPC_BCPRNG_LOCK( );

if (prng->kl > SPC_MAX_KEYLEN) prng->kl = SPC_MAX_KEYLEN;

spc_bcprng_rand(prng, m, prng->kl + SPC_BLOCK_SZ);

while (l > prng->kl) {

for (i = 0; i < prng->kl; i++) m[i] ^= *new_data++;

l -= prng->kl;

spc_bcprng_init(prng, m, prng->kl, m + prng->kl, SPC_BLOCK_SZ);

spc_bcprng_rand(prng, m, prng->kl + SPC_BLOCK_SZ);

}

for (i = 0; i <l; i++) m[i] ^= *new_data++;

spc_bcprng_init(prng, m, prng->kl, m + prng->kl, SPC_BLOCK_SZ);

SPC_BCPRNG_UNLOCK( );

}

To handle compression of the data that contains entropy, we avoid using a hash function. Instead, we break the data up into chunks no larger than the required seed size, and reseed multiple times until we have run out of data. This is an entropy-preserving way of processing the data that does not require the use of a cryptographic hash function.

See Also

Recipe 11.5, Recipe 11.16

11.7. Using an Entropy Gathering Daemon-Compatible Solution

Problem

Your application needs randomness, and you want it to be able to run on Unix-based platforms that lack the /dev/random and /dev/urandom devices discussed in Recipe 11.3—for example, machines that need to support legacy operating systems.

Solution

Use a third-party software package that gathers and outputs entropy, such as the Entropy Gathering and Distribution System (EGADS). Then use the Entropy Gathering Daemon (EGD) interface to read entropy. EGD is a tool for entropy harvesting and was the first tool to export this API.

When implementing our randomness API from Recipe 11.2, use entropy gathered over the EGD interface in places where entropy is needed; then, to implement the rest of the API, use data from that interface to seed an application-level cryptographic pseudo-random number generator (seeRecipe 11.5).

Discussion

A few entropy collection systems exist as processes outside the kernel and distribute entropy through the EGD socket interface. Such systems set up a server process, listening on a Unix domain socket. To read entropy, you communicate over that interface using a simple protocol.

One such system is EGADS (described in the next recipe and available from http://www.securesoftware.com/egads). Another system is EGD itself, which we do not recommend as of this writing for several reasons, primarily because we think its entropy estimates are too liberal.

Such entropy collection systems usually are slow to collect good entropy. If you can interactively collect input from a user, you might want to use one of the techniques in Recipe 11.19 instead to force the user to add entropy to the system herself. That approach will avoid arbitrary hangs as you wait for crucial entropy from an EGD-compatible system.

The EGD interface is more complex than the standard file interface you get when dealing with the /dev/random device. Traditionally, you would just read the data needed. With EGD, however, you must first write one of five commands to the socket. Each command is a single byte of data:

0x00

Query the amount of entropy believed to be available. This information is not at all useful, particularly because you cannot use it in any decision to read data without causing a race condition.

0x01

Read data if available. This command takes a single-byte argument specifying how many bytes of data should be read, if that much data is available. If not enough entropy is available, any available entropy may be immediately returned. The first byte of the result is the number of bytes being returned, so do not treat this information as entropy. Note that you can never request or receive more than 255 bytes of entropy at a time.

0x02

Read data when available. This command takes the same argument as the previous command. However, if not enough entropy is available, this command will block until the request can be fulfilled. In addition, the response for the command is simply the requested bytes; the initial byte is not the number of bytes being returned.

0x03

Write entropy to the internal collector. This command takes three arguments. The first is a two-byte value (most significant byte first) specifying how many bits of entropy are believed to be in the data. The second is a one-byte value specifying how many bytes of data are to be written. The third is the entropic data itself.

0x04

Get the process identifier of the EGD process. This returns a byte-long header that specifies how long the result is in bytes, followed by the actual process identifier, most significant byte first.

In this recipe, we implement the randomness interface from Recipe 11.2. In addition, we provide a function called spc_rand_add_entropy( ) , which provides an interface to the command for providing the server with entropy. That function does not allow the caller to specify an entropy estimate. We believe that user-level processes should be allowed to contribute data to be put into the mix but shouldn't be trusted to estimate entropy, primarily because you may have just cause not to trust the estimates of other processes running on the same machine that might be adding entropy. That is, if you are using an entropy server that gathers entropy slowly, you do not want an attacker from another process adding a big known value to the entropy system and claiming that it has 1,000 bits of entropy.

In part because untrusted programs can add bad entropy to the mix, we recommend using a highly conservative solution where such an attack is not likely to be effective. That means staying away from EGD, which will use estimates from any untrusted process. While EGADS implements the EGD interface, it ignores the entropy estimate supplied by the user. It does mix the entropy into its state, but it assumes that it contains no entropy.

The following code implements the spc_entropy( ) and spc_keygen( ) functions from Recipe 11.2 using the EGD interface. We omit spc_rand( ) but assume that it exists (it is called by spc_keygen( ) when appropriate). To implement spc_rand( ), see Recipe 11.5.

When implementing spc_entropy( ) and spc_keygen( ), we do not cryptographically postprocess the entropy to thwart statistical analysis if we do not have as much entropy as estimated, as you can generally expect servers implementing the EGD interface to do this (EGADS certainly does). If you want to be absolutely sure, you can do your own cryptographic postprocessing, as shown in Recipe 11.16.

Note that the following code requires you to know in advance the file on the filesystem that implements the EGD interface. There is no standard place to look for EGD sockets, so you could either make the location of the socket something the user can configure, or require the user to run the collector in such a way that the socket lives in a particular place on the filesystem.

Of course, the socket should live in a "safe" directory, where only the user running the entropy system can write files (see Recipe 2.4). Clearly, any user who needs to be able to use the server must have read access to the socket.

#include <sys/types.h>

#include <sys/socket.h>

#include <sys/un.h>

#include <sys/uio.h>

#include <unistd.h>

#include <string.h>

#include <errno.h>

#include <stdio.h>

#define EGD_SOCKET_PATH "/home/egd/socket"

/* NOTE: this needs to be augmented with whatever you need to do in order to seed

* your application-level generator. Clearly, seed that generator after you've

* initialized the connection with the entropy server.

*/

static int spc_egd_fd = -1;

void spc_rand_init(void) {

struct sockaddr_un a;

if ((spc_egd_fd = socket(PF_UNIX, SOCK_STREAM, 0)) = = -1) {

perror("Entropy server connection failed");

exit(-1);

}

a.sun_len = sizeof(a);

a.sun_family = AF_UNIX;

strncpy(a.sun_path, EGD_SOCKET_PATH, sizeof(a.sun_path));

a.sun_path[sizeof(a.sun_path) - 1] = 0;

if (connect(spc_egd_fd, (struct sockaddr *)&a, sizeof(a))) {

perror("Entropy server connection failed");

exit(-1);

}

}

unsigned char *spc_keygen(unsigned char *buf, size_t l) {

ssize_t nb;

unsigned char nbytes, *p, tbytes;

static unsigned char cmd[2] = {0x01,};

if (spc_egd_fd = = -1) spc_rand_init( );

for (p = buf; l; l -= tbytes) {

/* Build and send the request command to the EGD server */

cmd[1] = (l > 255 ? 255 : l);

do {

if ((nb = write(spc_egd_fd, cmd, sizeof(cmd))) = = -1 && errno != EINTR) {

perror("Communication with entropy server failed");

exit(-1);

}

} while (nb = = -1);

/* Get the number of bytes in the result */

do {

if ((nb = read(spc_egd_fd, &nbytes, 1)) = = -1 && errno != EINTR) {

perror("Communication with entropy server failed");

exit(-1);

}

} while (nb = = -1);

tbytes = nbytes;

/* Get all of the data from the result */

while (nbytes) {

do {

if ((nb = read(spc_egd_fd, p, nbytes)) = = -1) {

if (errno = = -1) continue;

perror("Communication with entropy server failed");

exit(-1);

}

} while (nb = = -1);

p += nb;

nbytes -= nb;

}

/* If we didn't get as much entropy as we asked for, the server has no more

* left, so we must fall back on the application-level generator to avoid

* blocking.

*/

if (tbytes != cmd[l]) {

spc_rand(p, l);

break;

}

}

return buf;

}

unsigned char *spc_entropy(unsigned char *buf, size_t l) {

ssize_t nb;

unsigned char *p;

static unsigned char cmd = 0x02;

if (spc_egd_fd = = -1) spc_rand_init( );

/* Send the request command to the EGD server */

do {

if ((nb = write(spc_egd_fd, &cmd, sizeof(cmd))) = = -1 && errno != EINTR) {

perror("Communcation with entropy server failed");

exit(-1);

}

} while (nb = = -1);

for (p = buf; l; p += nb, l -= nb) {

do {

if ((nb = read(spc_egd_fd, p, l)) = = -1) {

if (errno = = -1) continue;

perror("Communication with entropy server failed");

exit(-1);

}

} while (nb = = -1);

}

return buf;

}

void spc_egd_write_entropy(unsigned char *data, size_t l) {

ssize_t nb;

unsigned char *buf, nbytes, *p;

static unsigned char cmd[4] = { 0x03, 0, 0, 0 };

for (buf = data; l; l -= cmd[3]) {

cmd[3] = (l > 255 ? 255 : l);

for (nbytes = 0, p = cmd; nbytes < sizeof(cmd); nbytes += nb) {

do {

if ((nb = write(spc_egd_fd, cmd, sizeof(cmd) - nbytes)) = = -1) {

if (errno != EINTR) continue;

perror("Communication with entropy server failed");

exit(-1);

}

} while (nb = = -1);

}

for (nbytes = 0; nbytes < cmd[3]; nbytes += nb, buf += nb) {

do {

if ((nb = write(spc_egd_fd, data, cmd[3] - nbytes)) = = -1) {

if (errno != EINTR) continue;

perror("Communication with entropy server failed");

exit(-1);

}

} while (nb = = -1);

}

}

}

See Also

§ EGADS by Secure Software, Inc.: http://www.securesoftware.com/egads

§ Recipe 2.4, Recipe 11.2, Recipe 11.3, Recipe 11.5, Recipe 11.16, Recipe 11.19

11.8. Getting Entropy or Pseudo-Randomness Using EGADS

Problem

You want to use a library-level interface to EGADS for gathering entropy or getting cryptographically strong pseudo-random data. For example, you may need entropy on a system such as Microsoft Windows, where there is no built-in API for getting it.

Solution

Use the EGADS API as described in the following Section 11.8.3.

Discussion

EGADS, the Entropy Gathering and Distribution System, is capable of performing many functions related to random numbers. First, it provides a high-level interface for getting random values, such as integers, numbers in a particular range, and so on. Second, EGADS does its own entropy collection, and has a library-level API for accessing the collector, making it a simple API to use for any of your randomness needs.

EGADS supports a variety of Unix variants, including Darwin, FreeBSD, Linux, OpenBSD, and Solaris. In addition, it supports Windows NT 4.0, Windows 2000, and Windows XP. Unfortunately, EGADS does not support Windows 95, Windows 98, or Windows ME because it runs as a service (which is a subsystem that does not exist on these versions of Windows). EGADS is available from http://www.securesoftware.com/egads.

EGADS is a good solution for the security-minded because it is conservative. It contains a conservative entropy collector and a conservative pseudo-random number generator. Both of these components have provable security properties that rely only on the strength of the AES cryptographic algorithm. EGADS does a good job of protecting against compromised entropy sources, which other PRNGs tend not to do. It also provides a good amount of protection against backtracking attacks, meaning that if the internal generator state does get compromised, few if any of the previous generator outputs will be recoverable.

To use EGADS, you must install the package, start up the server that comes with it, include egads.h, and link against the correct library, which will typically be libegads.so on Unix (libegads.dyld on Darwin) and egads.lib on Windows.

Before you can use any of the functions in the EGADS package, you must first initialize a PRNG context by calling egads_init( ) :

void egads_init(prngctx_t *ctx, char *sockname, char *rfile, int *err);

This function has the following arguments:

ctx

PRNG context object that is to be initialized. The caller should allocate the object either statically or dynamically.

sockname

If not specified as NULL, this is the address of the server. On Unix, this is the name of the Unix domain socket created by the EGADS server. On Windows, this is the name of the mailslot object created by the EGADS service. If specified as NULL, which is normally how it should be specified, the compiled-in default will be used.

rfile

Name of a file from which entropy can be read. On Unix, this defaults to /dev/random if it is specified as NULL. This argument is always ignored on Windows.

err

If any error occurs, an error code will be stored in this argument. A value of 0 indicates that no error occurred; otherwise, one of the RERR_* constants defined in egads.h will be returned. NULL may not be specified here.

The function egads_entropy( ) establishes a connection to the entropy gateway and obtains the requested number of bytes of raw entropy. If not enough entropy is currently available to satisfy the request, this function will block until there is. Its signature nearly matches that of spc_entropy( )from Recipe 11.2:

void egads_entropy(prngctx_t *ctx, char *buf, int nbytes, int *err);

This function has the following arguments:

ctx

PRNG context object that has been initialized.

out

Buffer into which the entropy data will be placed.

nbytes

Number of bytes of entropy that should be written into the output buffer. You must be sure that the output buffer is sufficiently large to hold the requested data.

err

If any error occurs, an error code will be stored in this argument. A value of 0 indicates that no error occurred; otherwise, one of the RERR_* constants defined in egads.h will be returned. NULL may be not be specified here.

The function PRNG_output( ) allows you to get byte strings of cryptographically random data. Its signature nearly matches that of spc_rand( ) from Recipe 11.2:

void PRNG_output(prng_ctx *ctx, char *buf, int64 nbytes);

This function has the following arguments:

ctx

PRNG context object that has been initialized.

buf

Buffer into which the entropy data will be placed.

nbytes

Number of bytes of random data that should be written into the output buffer. You must be sure that the output buffer is sufficiently large to hold the requested data.

The function egads_destroy( ) resets a PRNG context object. Before the memory for the context object is freed or goes out of scope (because it is statically allocated on the stack), egads_destroy( ) must be called on a successfully initialized context object. This ensures that the connection to the EGADS server or service is broken, and that any other memory or state maintained by EGADS that is associated with the context object is cleaned up.

void egads_destroy(prngctx_t *ctx);

This ctx argument is the successfully initialized PRNG context that is to be destroyed. It is the caller's responsibility to free any memory used to allocate the object

The rest of the EGADS API allows you to retrieve pseudo-random values of particular data types. All functions in this API take a final argument that, on completion of the call, contains the success or failure status. On failure, the error argument contains an integer error code. On success, it will be 0.

void egads_randlong(prngctx_t *ctx, long *out, int *error);

void egads_randulong(prngctx_t *ctx, unsigned long *out, int *error);

void egads_randint(prngctx_t *ctx, int *out, int *error);

void egads_randuint(prngctx_t *ctx, unsigned int *out, int *error);

void egads_randrange(prngctx_t *ctx, int *out, int min, int max, int *error);

The egads_randlong( ) function gets a pseudo-random long value, whereas egads_randulong( ) gets a pseudo-random unsigned long value from to ULONG_MAX inclusive. The functions egads_randint( ) and egads_randuint( ) do the same things, but on integer types instead of longs. To get a random integer in a specified range, use the function egads_randrange( ) . The min and max arguments are both inclusive, meaning that they are both values that can possibly be returned.

void egads_randreal(prngctx_t * ctx, double *out, int *error);

void egads_randuniform(prngctx_t *ctx, double *out, double min, double max,

int *error);

void egads_gauss(prngctx_t *ctx, double *out, double mu, double sigma,

int *error);

void egads_normalvariate(prngctx_t *ctx, double *out, double mu, double sigma,

int *error);

void egads_lognormalvariate(prngctx_t *ctx, double *out, double mu, double sigma,

int *error);

void egads_paretovariate(prngctx_t *ctx, double *out, double alpha, int *error);

void egads_weibullvariate(prngctx_t *ctx, double *out, double alpha, double beta,

int *error);

void egads_expovariate(prngctx_t *ctx, double *out, double lambda, int *error);

void egads_betavariate(prngctx_t *ctx, double *out, double alpha, double beta,

int *error);

void egads_cunifvariate(prngctx_t *ctx, double *out, double mean, double arc,

int *error);

The egads_randreal( ) function produces a real number between 0 and 1 (inclusive) that is uniformly distributed across that space. To get a real number in a particular range, use the function egads_randuniform( ) . For those needing random data in a nonuniform distribution, there are numerous functions in the previous API to produce random floats in various common distributions. The semantics for these functions should be obvious to anyone who is already familiar with the particular distribution.

void egads_randstring(prngctx_t *ctx, char *out, int len, int *error);

The function egads_randstring( ) generates a random string that can contain any printable character. That is, it produces characters between ASCII 33 and ASCII 126 (inclusive) and thus contains no whitespace characters. The output buffer must be allocated by the caller, and it must be at least as long as the specified length plus an additional byte to accommodate the terminating zero that the function will write to the buffer.

void egads_randfname(prngctx_t *ctx, char *out, int len, int *error);

The function egads_randfname( ) produces a random string suitable for use as a filename. Generally, you are expected to concatenate the generated string with a base path. This function expects the destination buffer to be allocated already, and to be allocated with enough space to hold the string plus a terminating NULL, which this function will add.

See Also

§ EGADS by Secure Software, Inc.: http://www.securesoftware.com/egads

§ Recipe 11.2

11.9. Using the OpenSSL Random Number API

Problem

Many functions in the OpenSSL library require the use of the OpenSSL pseudo-random number generator. Even if you use something like /dev/urandom yourself, OpenSSL will use its own API under the hood and thus must be seeded properly.

Unfortunately, some platforms and some older versions of OpenSSL require the user to provide a secure seed. Even modern implementations of OpenSSL merely read a seed from /dev/urandom when it is available; a paranoid user may wish to do better.

When using OpenSSL, you may want to use the provided PRNG for other needs, just for the sake of consistency.

Solution

OpenSSL exports its own API for manipulating random numbers, which we discuss in the next section. It has its own cryptographic PRNG, which must be securely seeded.

To use the OpenSSL randomness API, you must include openssl/rand.h in your code and link against the OpenSSL crypto library.

Discussion

WARNING

Be sure to check all return values for the functions below; they may return errors.

With OpenSSL, you get a cryptographic PRNG but no entropy gateway. Recent versions of OpenSSL try to seed its PRNG using /dev/random, /dev/urandom, and EGD, trying several well-known EGD socket locations. However, OpenSSL does not try to estimate how much entropy its PRNG has. It is up to you to ensure that it has enough before the PRNG is used.

On Windows systems, a variety of sources are used to attempt to gather entropy, although none of them actually provides much real entropy. If an insufficient amount of entropy is available, OpenSSL will issue a warning, but it will keep going anyway. You can use any of the sources we have discussed elsewhere in this chapter for seeding the OpenSSL PRNG. Multiple API functions are available that allow seed information to be passed to the PRNG.

One such function is RAND_seed( ) , which allows you to pass in arbitrary data that should be completely full of entropy. It has the following signature:

void RAND_seed(const void *buf, int num);

This function has the following arguments:

buf

Buffer containing the entropy to seed the PRNG.

num

Length of the seed buffer in bytes.

If you have data that you believe contains entropy but does not come close to one bit of entropy per bit of data, you can call RAND_add( ) , which is similar to RAND_seed( ) except that it allows you to provide an indication of how many bits of entropy the data has:

void RAND_add(const void *buf, int num, double entropy);

If you want to seed from a device or some other file (usually, you only want to use a stored seed), you can use the function RAND_load_file( ) , which will read the requested number of bytes from the file. Because there is no way to determine how much entropy is contained in the data, OpenSSL assumes that the data it reads from the file is purely entropic.

int RAND_load_file(const char *filename, long max_bytes);

If -1 is specified as the length parameter to this function, it reads the entire file. This function returns the number of bytes read. The function can be used to read from the /dev/random and /dev/urandom devices on Unix systems that have them, but you must make sure that you don't specify -1 for the number of bytes to read from these files; otherwise, the function will never return!

To implement PRNG state saving with OpenSSL, you can use RAND_write_file( ) , which writes out a representation of the PRNG's internal state that can be used to reseed the PRNG when needed (e.g., after a reboot):

int RAND_write_file(const char *filename);

If there is any sort of error, RAND_write_file( ) will return -1. Note that the system may write a seed file without enough entropy, in which case it will also return -1. Otherwise, this function returns the number of bytes written to the seed file.

To obtain pseudo-random data from the PRNG, use the function RAND_bytes( ) :

int RAND_bytes(unsigned char *buf, int num);

If the generator is not seeded with enough entropy, this function could produce output that may be insecure. In such a case, the function will return 0. Make sure that you always check for this condition!

WARNING

Do not, under any circumstances, use the API function, RAND_pseudo_bytes( ) . It is not a cryptographically strong PRNG and therefore is not worth using for anything that has even a remote possibility of being security-relevant.

You can implement spc_rand( ) , the cryptographic pseudo-randomness function from Recipe 11.2, by simply calling RAND_bytes( ) and aborting if that function returns 0.

#include <stdio.h>

#include <stdlib.h>

#include <openssl/rand.h>

unsigned char *spc_rand(unsigned char *buf, size_t l) {

if (!RAND_bytes(buf, l)) {

fprintf(stderr, "The PRNG is not seeded!\n");

abort( );

}

return buf;

}

See Also

Recipe 11.2

11.10. Getting Random Integers

Problem

Given a pseudo-random number generation interface that returns an array of bytes, you need to get random values in the various integer data types.

Solution

For dealing with an integer that can contain any value, you may simply write bytes directly into every byte of the integer.

Discussion

WARNING

Do not use this solution for getting random floating-point values; it will not produce numbers in a uniform distribution because of the mechanics of floating-point formats.

To get a random integer value, all you need to do is fill the bytes of the integer with random data. You can do this by casting a pointer to an integer to a binary string, then passing it on to a function that fills a buffer with random bytes. For example, use the following function to get a random unsigned integer, using the spc_rand( ) interface defined in Recipe 11.2:

unsigned int spc_rand_uint(void) {

unsigned int res;

spc_rand((unsigned char *)&res, sizeof(unsigned int));

return res;

}

This solution can easily be adapted to other integer data types simply by changing all the instances of unsigned int to the appropriate type.

See Also

Recipe 11.2

11.11. Getting a Random Integer in a Range

Problem

You want to choose a number in a particular range, with each possible value equally likely. For example, you may be simulating dice rolling and do not want any number to be more likely to come up than any other. You want all numbers in the range to be possible values, including both endpoints. That is, if you ask for a number between 1 and 6, you'd like both 1 and 6 to be as likely as 2, 3, 4, or 5.

Solution

There are multiple ways to handle this problem. The most common is the least correct, and that is to simply reduce a random integer (see Recipe 11.10) modulo the size of the range and add to the minimum possible value. This can lead to slight biases in your random numbers, which can sometimes lead to practical attacks, because it means that some outputs are more likely than others.

We discuss more exact solutions in the next section.

Discussion

In all cases, you will start with a function that gives you a random unsigned number that can be any value, such as spc_rand_uint( ) from Recipe 11.10. You will mold numbers returned from this function into numbers in a specific range.

If you need random numbers in a particular range, the general approach is to get a number between zero and one less than the number of values in the range, then add the result to the smallest possible value in the range.

Ideally, when picking a random number in a range, you would like every possible value to be equally likely. However, if you map from an arbitrary unsigned integer into a range, where the range does not divide evenly into the number of possible integers, you are going to run into problems.

Suppose you want to create a random number in a range using an unsigned 8-bit type. When you get a random unsigned 8-bit value, it can take on 256 possible values, from 0 to 255. If you are asking for a number between 0 and 9 inclusive, you could simply take a random value and reduce it modulo 10.

The problem is that the numbers 0 through 5 are more likely values than are 6 through 9. 26 possible values will reduce to each number between 0 and 5, but only 25 values will yield 6 through 9.

In this example, the best way to solve this problem is to discard any random numbers that fall in the range 250-255. In such a case, simply get another random value and try again. We took this approach in implementing the function spc_rand_range( ) . The result will be a number greater than or equal to a minimum value and less than or equal to maximum value.

WARNING

Some programmers may expect this function to exclude the upper limit as a possible value; however, we implement this function in such a way that it is not excluded.

#include <limits.h>

#include <stdlib.h>

int spc_rand_range(int min, int max) {

unsigned int rado;

int range = max - min + 1;

if (max < min) abort( ); /* Do your own error handling if appropriate.*/

do {

rado = spc_rand_uint( );

} while (rado > UINT_MAX - (UINT_MAX % range));

return min + (rado % range);

}

You might worry about a situation where performance suffers because this code has to retry too many times. The worst case for this solution is when the size of the range is UINT_MAX / 2 + 1. Even in such a case, you would not expect to call spc_rand_uint( ) very many times. The average number of times it would be called here would be slightly less than two. While the worst-case performance is theoretically unbounded, the chances of calling spc_rand_uint( ) more than a dozen times are essentially zero. Therefore, this technique will not have a significant performance impact for most applications.

If you are okay with some items being slightly more likely than others, there are two different things you can do, both of which are fairly easy. First, you can perform a modulo operation and an addition to get the integer in the right range, and just not worry about the fact that some values are more likely than others:

#include <stdlib.h>

int spc_rand_range(int min, int max) {

if (max < min) abort( );

return min + (spc_rand_uint( ) % (max - min + 1));

}

Of course, this solution clumps together all the values that are more likely to be chosen, which is somewhat undesirable. As an alternative, you can spread them out by using division and rounding down, instead of a simple modulus:

#include <limits.h>

int spc_rand_range(int min, int max) {

if (max < min) abort( );

return min + (int)((double)spc_rand_uint( ) *

(max - min + 1) / (double)UINT_MAX) % (max - min);

}

Note the modulo operation in this solution. That is to prevent getting a value that is out of range in the very rare occasion that spc_rand_uint( ) returns UINT_MAX.

See Also

Recipe 11.10

11.12. Getting a Random Floating-Point Value with Uniform Distribution

Problem

When looking for a random floating-point number, we usually want a value between 0 and 1 that is just as likely to be between 0 and 0.1 as it is to be between 0.9 and 1.

Solution

Because of the way that floating-point numbers are stored, simply casting bits to a float will make the distribution nonuniform. Instead, get a random unsigned integer, and divide.

Discussion

Because integer values are uniformly distributed, you can get a random integer and divide so that it is a value between 0 and 1:

#include <limits.h>

double spc_rand_real(void) {

return ((double)spc_rand_uint( )) / (double)UINT_MAX;

}

Note that to get a random number between 0 and n, you can multiply the result of spc_rand_real( ) by n. To get a real number within a range inclusive of the range's bounds, do this:

#include <stdlib.h>

double spc_rand_real_range(double min, double max) {

if (max < min) abort( );

return spc_rand_real( ) * (max - min) + min;

}

11.13. Getting Floating-Point Values with Nonuniform Distributions

Problem

You want to select random real numbers in a nonuniform distribution.

Solution

The exact solution varies depending on the distribution. We provide implementations for many common distributions in this recipe.

Discussion

Do not worry if you do not know what a particular distribution is; if you have never seen it before, you really should not need to know what it is. A uniform distribution (as discussed in Recipe 11.12) is far more useful in most cases.

In all cases, we start with a number with uniform distribution using the API from Recipe 11.12.

Note that these functions use math operations defined in the standard math library. On many platforms, you will have to link against the appropriate library (usually by adding -lm to your link line).

#include <math.h>

#define NVCONST 1.7155277699141

double spc_rand_normalvariate(double mu, double sigma) {

double myr1, myr2, t1, t2;

do {

myr1 = spc_rand_real( );

myr2 = spc_rand_real( );

t1 = NVCONST * (myr1 - 0.5) / myr2;

t2 = t1 * t1 / 4.0;

} while (t2 > -log(myr2));

return mu + t1 * sigma;

}

double spc_rand_lognormalvariate(double mu, double sigma) {

return exp(spc_rand_normalvariate(mu, sigma));

}

double spc_rand_paretovariate(double alpha) {

return 1.0 / pow(spc_rand_real( ), 1.0 / alpha);

}

double spc_rand_weibullvariate(double alpha, double beta) {

return alpha * pow(-log(spc_rand_real( )), 1.0 / beta);

}

double spc_rand_expovariate(double lambda) {

double myr = spc_rand_real( );

while (myr <= 1e-7)

myr = spc_rand_real( );

return -log(myr) / lambda;

}

double spc_rand_betavariate(double alpha, double beta) {

double myr1, myr2;

myr1 = spc_rand_expovariate(alpha);

myr2 = spc_rand_expovariate(1.0 / beta);

return myr2 / (myr1 + myr2);

}

#define SPC_PI 3.1415926535

double spc_rand_cunifvariate(double mean, double arc) {

return (mean + arc * (spc_rand_real( ) - 0.5)) / SPC_PI;

}

See Also

Recipe 11.12

11.14. Getting a Random Printable ASCII String

Problem

You want to get a random printable ASCII string.

Solution

If you do not want whitespace characters, the printable ASCII characters have values from 33 to 126, inclusive. Simply get a random number in that range for each character.

If you want to choose from a different character set (such as the base64 character set), map each character to a specific numeric value between 0 and the number of characters you have. Select a random number in that range, and map the number back to the corresponding character.

Discussion

The code presented in this section returns a random ASCII string of a specified length, where the specified length includes a terminating NULL byte. We use the printable ASCII characters, meaning that we never output whitespace or control characters.

Assuming a good underlying infrastructure for randomness, each character should be equally likely. However, the ease with which an attacker can guess a single random string is related not only to the entropy in the generator, but also to the length of the output. If you use a single character, there are only 94 possible values, and a guess will be right with a probability of 1/94 (not having entropy can give the attacker an even greater advantage).

As a result, your random strings should use no fewer than 10 random characters (not including the terminating NULL byte), which gives you about 54 bits of security. For a more conservative security margin, you should go for 15 to 20 characters.

#include <stdlib.h>

char *spc_rand_ascii(char *buf, size_t len) {

char *p = buf;

while (--len)

*p++ = (char)spc_rand_range(33, 126);

*p = 0;

return buf;

}

11.15. Shuffling Fairly

Problem

You have an ordered list of items that you would like to shuffle randomly, then visit one at a time. You would like to do so securely and without biasing any element.

Solution

For each index, swap the item at that index with the item at a random index that has not been fully processed, including the current index.

Discussion

Performing a statistically fair shuffle is actually not easy to do right. Many developers who implement a shuffle that seems right to them off the top of their heads get it wrong.

We present code to shuffle an array of integers here. We perform a statistically fair shuffle, using the spc_rand_range( ) function from Recipe 11.11.

#include <stdlib.h>

void spc_shuffle(int *items, size_t numitems) {

int tmp;

size_t swapwith;

while (--numitems) {

/* Remember, it must be possible for a value to swap with itself */

swapwith = spc_rand_range(0, numitems);

tmp = items[swapwith];

items[swapwith] = items[numitems];

items[numitems] = tmp;

}

}

If you need to shuffle an array of objects, you can use this function to first permute an array of integers, then use that permutation to reorder the elements in your array. That is, if you have three database records, and you shuffle the list [1, 2, 3], getting [3, 1, 2], you would build a new array consisting of the records in the listed order.

See Also

Recipe 11.11

11.16. Compressing Data with Entropy into a Fixed-Size Seed

Problem

You are collecting data that may contain entropy, and you will need to output a fixed-size seed that is smaller than the input. That is, you have a lot of data that has a little bit of entropy, yet you need to produce a fixed-size seed for a pseudo-random number generator. At the same time, you would like to remove any statistical biases (patterns) that may be lingering in the data, to the extent possible.

Alternatively, you have data that you believe contains one bit of entropy per bit of data (which is generally a bad assumption to make, even if it comes from a hardware generator; see Recipe 11.19), but you'd like to remove any patterns in the data that could facilitate analysis if you're wrong about how much entropy is there. The process of removing patterns is called whitening.

Solution

You can use a cryptographic hash function such as SHA1 to process data into a fixed-size seed. It is generally a good idea to process data incrementally, so that you do not need to buffer potentially arbitrary amounts of data with entropy.

Discussion

TIP

Be sure to estimate entropy conservatively. ( See Recipe 11.19.)

It is a good idea to use a cryptographic algorithm to compress the data from the entropy source into a seed of the right size. This helps preserve entropy in the data, up to the output size of the message digest function. If you need fewer bytes for a seed than the digest function produces, you can always truncate the output. In addition, cryptographic processing effectively removes any patterns in the data (assuming that the hash function is a pseudo-random function). Patterns in the data can help facilitate breaking an entropy source (in part or in full), particularly when that source does not actually produce as much entropy as was believed.

Most simpler compression methods are not going to do as good a job at preserving entropy. For example, suppose that your compression function is simply XOR. More concretely, suppose you need a 128-bit seed, and you XOR data in 16-byte chunks into a single buffer. Suppose also that you believe you have collected 128 bits of entropy from numerous calls to a 128-bit timestamp operation.

In any particular timestamp function, all of the entropy is going to live in a few of the least significant bits. Now suppose that only two or three of those bits are likely to contain any entropy. The XOR-everything strategy will leave well over 120 bits of the result trivial to guess. The remaining eight bits can be attacked via brute force. Therefore, even if the input had 128 bits of entropy, the XOR-based compression algorithm destroyed most of the entropy.

SHA1 is good for these purposes. See Recipe 6.5 for how to use SHA1.

See Also

Recipe 6.5, Recipe 11.19

11.17. Getting Entropy at Startup

Problem

You want to be able to seed a cryptographic pseudo-random number generator securely as soon as a machine boots, without having to wait for interaction from the user or other typical sources of entropy.

Solution

If you have never been able to seed the generator securely, prompt for entropy on install or first use (see Recipe 11.20 and Recipe 11.21).

Otherwise, before shutting down the generator, have it output enough material to reseed itself to a file located in a secure part of the filesystem. The next time the generator starts, read the seed file and use the data to reseed, as discussed in Recipe 11.6.

Discussion

It can take a noticeable amount of time for a PRNG to gather enough entropy that it is safe to begin outputting random data. On some systems with /dev/random as the entropy source, users could be forced to sit around indefinitely, not knowing how to get more entropy into the system.

It would be nice if you did not have to collect entropy every time a program starts up or the machine reboots. You should need to get entropy only once per application, then be able to store that entropy until the next time you need it.

If you have sufficient trust in the local filesystem, you can certainly do this by writing out a seed to a file, which you can later use to initialize the generator when it starts back up. Of course, you need to make sure that there are no possible security issues in file access. In particular, the location you use for saving seed files needs to be a secure location (see Recipe 2.4 for more on how to ensure this programmatically). In addition, you should be sure not to store a seed on a potentially untrusted filesystem, such as an NFS mount, and you should probably use advisory file locking in an attempt to defeat any accidental race conditions on the seed file.

You should also consider the threat of an insider with physical access to the machine compromising the seed file. For that reason, you should always strive to add new entropy to a generator after every startup as soon as enough bits can be collected. Using a seed file should be considered a stopgap measure to prevent stalling on startup.

See Also

Recipe 2.4, Recipe 11.6, Recipe 11.20, Recipe 11.21

11.18. Statistically Testing Random Numbers

Problem

You are using a hardware random number generator or some other entropy source that hasn't been cryptographically postprocessed, and you would like to determine whether it ever stops producing quality data. Alternatively, you want to have your generator be FIPS 140 compliant (perhaps for FIPS certification purposes).

Solution

FIPS 140-2 tests, which are ongoing throughout the life of the generator, are necessary for FIPS 140 compliance. For actual statistical tests of data produced by a source, the full set of tests provided by FIPS 140-1 are much more useful, even though they are now irrelevant to the FIPS certification process.

Discussion

WARNING

FIPS 140 tests are useful for proving that a stream of random numbers are weak, but the tests don't demonstrate at all when the numbers are good. In particular, it is incredibly easy to have a weak generator yet still pass FIPS tests by processing data with a cryptographic primitive like SHA1 before running the tests. FIPS 140 is only useful as a safety net, for when an entropy source you think is strong turns out not to be.

FIPS 140 is a standard authored by the U.S. National Institute of Standards and Technology (NIST; see http://csrc.nist.gov/cryptval/). The standard details general security requirements for cryptographic software deployed in government systems (primarily cryptographic "providers"). There are many aspects to the FIPS 140 standard, one of which is a set of tests that all entropy harvesters and pseudo-random number generators must be able to run to achieve certification.

FIPS 140-1 was the original standard and had several tests for random number sources; most of these occurred on startup, but one occurred continuously. Those tests only needed to be implemented for the two highest levels of FIPS compliance (Levels 3 and 4), which few applications sought.

In FIPS 140-2, only a single test from FIPS 140-1 remains. This test is mandatory any time a random number generator or entropy source is used.

Although the FIPS 140-1 standard is being obsoleted by 140-2, it is important to note that a module can routinely fail the FIPS 140-1 tests and still be FIPS 140-1 compliant. For Level 3 compliance, the user must be able to run the tests on command, and if the tests fail, the module must go into an error state. For Level 4 compliance, the module must comply with the requirements of Level 3, plus the tests must be run at "power-up." A weak random number generator, such as the one implemented by the standard C library function rand( ), should be able to get Level 3 certification easily.

FIPS 140-1 testing is a reasonable tool for ensuring that entropy sources are producing quality data, if those entropy sources are not using any cryptographic operations internally. If they are, the entropy source will almost certainly pass these tests, even if it is a very poor entropy source. For the same reason, this set of tests is not good for testing cryptographic PRNGs, because all such generators will pass these tests with ease, even if they are poor. For example, simply hashing an incrementing counter that starts at zero using MD5 will produce a data stream that passes these tests, even though the data in that stream is easily predictable.

FIPS 140-2 testing generally is not very effective unless a failed hardware device starts producing a repeating pattern (e.g., a string of zero bits). The FIPS 140-2 test consists of comparing consecutive generator outputs (on a large boundary size; see the next section). If your "random number generator" consists only of an ever-incrementing 128-bit counter, you will never fail this test.

For this reason, we think the full suite of FIPS 140-1 tests is the way to go any time you really want to test whether an entropy source is producing good data, and it is a good idea to run these tests on startup, and then periodically, when feasible. You should always support the continuous test that FIPS 140-2 mandates whenever you are using hardware random number generators that could possibly be prone to disastrous failure, because it might help you detect such a failure.

FIPS 140-1 power-up and on-demand tests

The FIPS 140-1 standard specifies four statistical tests that operate on 20,000 consecutive bits of output (2,500 bytes).

In the first test, the "Monobit" test, the number of bits set to 1 are counted. The test passes if the number of bits set to 1 is within a reasonable proximity to 10,000. The function spc_fips_monobit( ) , implemented as follows, performs this test, returning 1 on success, and 0 on failure.

#define FIPS_NUMBYTES 2500

#define FIPS_MONO_LOBOUND 9654

#define FIPS_MONO_HIBOUND 10346

/* For each of the 256 possible bit values, how many 1 bits are set? */

static char nb_tbl[256] = {

0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,

4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4,

4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2,

3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5,

4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3,

4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3,

3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5,

6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,

4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5,

6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8

};

int spc_fips_monobit(unsigned char data[FIPS_NUMBYTES]) {

int i, result;

for (i = result = 0; i < FIPS_NUMBYTES; i++)

result += nb_tbl[data[i]];

return (result > FIPS_MONO_LOBOUND && result < FIPS_MONO_HIBOUND);

}

The second test is the "Poker" test, in which the data is broken down into consecutive 4-bit values to determine how many times each of the 16 possible 4-bit values appears. The square of each result is then added together and scaled to see whether the result falls in a particular range. If so, the test passes. The function spc_fips_poker( ) , implemented as follows, performs this test, returning 1 on success and 0 on failure:

#define FIPS_NUMBYTES 2500

#define FIPS_POKER_LOBOUND 1.03

#define FIPS_POKER_HIBOUND 57.4

int spc_fips_poker(unsigned char data[FIPS_NUMBYTES]) {

int i;

long counts[16] = {0,}, sum = 0;

double result;

for (i = 0; i < FIPS_NUMBYTES; i++) {

counts[data[i] & 0xf]++;

counts[data[i] >> 4]++;

}

for (i = 0; i < 16; i++)

sum += (counts[i] * counts[i]);

result = (16.0 / 5000) * (double)sum - 5000.0;

return (result > FIPS_POKER_LOBOUND && result < FIPS_POKER_HIBOUND);

}

The third and fourth FIPS 140-1 statistical tests are implemented as follows to run in parallel in a single routine. The third test, the "Runs" test, goes through the data stream and finds all the "runs" of consecutive bits that are identical. The test then counts the maximum length of each run. That is, if there are three consecutive zeros starting at the first position, that's one run of length three, but it doesn't count as any runs of length two or any runs of length one. Runs that are longer than six bits are counted as a six-bit run. At the end, for each length of run, the count for consecutive zeros of that run length and the count for consecutive ones are examined. If either fails to fall within a specified range, the test fails. If all of the results are in an appropriate range for the run length in question, the test passes.

The fourth test, the "Long Runs" test, also calculates runs of bits. The test looks for runs of 34 bits or longer. Any such runs cause the test to fail; otherwise, it succeeds.

#define FIPS_NUMBYTES 2500

#define FIPS_LONGRUN 34

#define FIPS_RUNS_1_LO 2267

#define FIPS_RUNS_1_HI 2733

#define FIPS_RUNS_2_LO 1079

#define FIPS_RUNS_2_HI 1421

#define FIPS_RUNS_3_LO 502

#define FIPS_RUNS_3_HI 748

#define FIPS_RUNS_4_LO 223

#define FIPS_RUNS_4_HI 402

#define FIPS_RUNS_5_LO 90

#define FIPS_RUNS_5_HI 223

#define FIPS_RUNS_6_LO 90

#define FIPS_RUNS_6_HI 223

/* Perform both the "Runs" test and the "Long Run" test */

int spc_fips_runs(unsigned char data[FIPS_NUMBYTES]) {

/* We allow a zero-length run size, mainly just to keep the array indexing less

* confusing. It also allows us to set cur_val arbitrarily below (if the first

* bit of the stream is a 1, then runs[0] will be 1; otherwise, it will be 0).

*/

int runs[2][7] = {{0,},{0,}};

int cur_val, i, j, runsz;

unsigned char curr;

for (cur_val = i = runsz = 0; i < FIPS_NUMBYTES; i++) {

curr = data[i];

for (j = 0; j < 8; j++) {

/* Check to see if the current bit is the same as the last one */

if ((curr & 0x01) ^ cur_val) {

/* The bits are different. A run is over, and a new run of 1 has begun */

if (runsz >= FIPS_LONGRUN) return 0;

if (runsz > 6) runsz = 6;

runs[cur_val][runsz]++;

runsz = 1;

cur_val = (cur_val + 1) & 1; /* Switch the value. */

} else runsz++;

curr >>= 1;

}

}

return (runs[0][1] > FIPS_RUNS_1_LO && runs[0][1] < FIPS_RUNS_1_HI &&

runs[0][2] > FIPS_RUNS_2_LO && runs[0][2] < FIPS_RUNS_2_HI &&

runs[0][3] > FIPS_RUNS_3_LO && runs[0][3] < FIPS_RUNS_3_HI &&

runs[0][4] > FIPS_RUNS_4_LO && runs[0][4] < FIPS_RUNS_4_HI &&

runs[0][5] > FIPS_RUNS_5_LO && runs[0][5] < FIPS_RUNS_5_HI &&

runs[0][6] > FIPS_RUNS_6_LO && runs[0][6] < FIPS_RUNS_6_HI &&

runs[1][1] > FIPS_RUNS_1_LO && runs[1][1] < FIPS_RUNS_1_HI &&

runs[1][2] > FIPS_RUNS_2_LO && runs[1][2] < FIPS_RUNS_2_HI &&

runs[1][3] > FIPS_RUNS_3_LO && runs[1][3] < FIPS_RUNS_3_HI &&

runs[1][4] > FIPS_RUNS_4_LO && runs[1][4] < FIPS_RUNS_4_HI &&

runs[1][5] > FIPS_RUNS_5_LO && runs[1][5] < FIPS_RUNS_5_HI &&

runs[1][6] > FIPS_RUNS_6_LO && runs[1][6] < FIPS_RUNS_6_HI);

}

The FIPS continuous output test

The FIPS continuous output test requires that random number generators (which would include both entropy sources and PRNGs) have the data they are going to produce broken up into "blocks" of at least 16 bytes. If the generator has a "natural" block size of greater than 16 bytes, that should always get used. Otherwise, any size 16 bytes or greater can be used. We recommend never using blocks larger than 16 bytes (unless required) because the underlying generator uses larger blocks naturally.^[2^]

This test collects the first block of output and never gives it to anyone. Instead, it is compared against the second block of output and thrown away. The second block may be output if it is not identical to the first block; otherwise, the system must fail. The second output is also saved and is then compared to the third block. This process continues for all generator outputs.

The following (non-thread-safe) code adds a FIPS-compliant wrapper to the spc_entropy( ) function from Recipe 11.2 (note that this assumes that spc_entropy( ) does not cryptographically postprocess its data, because otherwise the test is all but worthless).

#include <stdlib.h>

#include <string.h>

#define RNG_BLOCK_SZ 16

char *spc_fips_entropy(char *outbuf, int n) {

static int i, bufsz = -1;

static char b1[RNG_BLOCK_SZ], b2[RNG_BLOCK_SZ];

static char *last = b1, *next = b2;

char *p = outbuf;

if (bufsz = = -1) {

spc_entropy(next, RNG_BLOCK_SZ);

bufsz = 0;

}

while (bufsz && n--)

*p++ = last[RNG_BLOCK_SZ - bufsz--];

while (n >= RNG_BLOCK_SZ) {

/* Old next becomes last here */

*next ^= *last;

*last ^= *next;

*next ^= *last;

spc_entropy(next, RNG_BLOCK_SZ);

for (i = 0; i < RNG_BLOCK_SZ; i++)

if (next[i] != last[i]) goto okay;

abort( );

okay:

memcpy(p, next, RNG_BLOCK_SZ);

p += RNG_BLOCK_SZ;

n -= RNG_BLOCK_SZ;

}

if (n) {

*next ^= *last;

*last ^= *next;

*next ^= *last;

spc_entropy(next, RNG_BLOCK_SZ);

for (i = 0; i < RNG_BLOCK_SZ; i++)

if (next[i] != last[i])

goto okay2;

abort( );

okay2:

memcpy(p, next, n);

bufsz = RNG_BLOCK_SZ - n;

}

return outbuf;

}

See Also

§ NIST Cryptographic Module Validation Program home page: http://csrc.nist.gov/cryptval/

§ Recipe 11.2