Random Numbers

From OpenSSLWiki
Revision as of 15:56, 4 March 2013 by Jwalton (talk | contribs) (Fixed typo, emphasized ''not'')

Jump to: navigation, search

Random Numbers are a cryptographic primitive and cornerstone to nearly all cryptographic systems. They are used in almost all areas of cryptography, from key agreement and transport to session keys for bulk encryption. A quality source of random bits and proper use of OpenSSL APIs will help ensure your program is cryptographically sound. On the other hand, a poor source of randomness or incorrect library usage could result in loss of security. This article will help you use random number generation routines correctly when programming with the OpenSSL library.

OpenSSL provides a number of software based random number generators based on a variety of sources. A software based random number generator creates random numbers by executing a software algorithm. There are a number of algorithms specified by a number of standard bodies including NIST, ANSI X9 committee (X9.17 and X9.31) and XXX. In addition, the library can use custom hardware if the hardware has an ENIGNE interface. Its critical to ensure the generator is seeded properly so that each unique instance of a generator produces an equally unique stream of random bits.

Good random numbers can be hard to procure from deterministic processes such as a computer executing instructions. A number of cryptographic attacks have been developed because they are so hard to acquire. Especially vulnerable are headless servers, embedded devices, and mobile devices, and you may have to take extra steps to ensure an adequate supply of entropy is available. The extra steps could include Hedging on a headless server or embedded device, and Finger Painting on a mobile device. For recent attacks on low entropy devices (such as headless servers and mobile devices), see for example, When Good Randomness Goes Bad: Virtual Machine Reset Vulnerabilities and Hedging Deployed Cryptography , Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices, and Traffic sensor flaw that could allow driver tracking fixed.

Entropy

Entropy is the measure of "randomness" in a sequence of bits. Different sources have different entropy. For example, a physical process in nature may have 100% entropy which appears purely random. On the other hand, the written English language provides about 3 bits/byte (or character) which is at most 38%. Some estimates have shown English characters provide only 1 bit/byte (or 12%). A random stream stream produced by software will also have entropy and it likely will not be 100%.

Random number generators need quality entropy for input (a seed, discussed below) and must produce quality output (quod vide). When using OpenSSL's APIs, you will be asked to estimate entropy when seeding or reseeding (input). When estimating entropy you should error on the low side to ensure proper fitness of the generator. When receiving bytes, you will receive a code indicating the success/failure of the operation and quality of the bytes (output).

Sometimes the operating system offers block access to hardware random number generators via /dev/hwrng. /dev/hwrng can be a low volume device, and could potentially block. For example, the Intel 82802 Firmware Hub used with the and i840 chipset produces one byte of data in its register. At other times, /dev/hwrng can be a high volume device, such as Intel's Secure Key Technology. In virtualized environments, /dev/hwrng might actually be a VirtIO RNG.

Entropy is important for a healthy program, and you should investigate hardware modules to help acquire it, especially if poor entropy or entropy depletion are a concern. There are a number of inexpensive and high quality hardware modules on the market, including a $40UK EntropyKey. There are also a number of high quality and high priced hardware modules and accelerators.

If you lack /dev/random and cannot procure a hardware random number generator, you can also consider an alternate entropy gather such as the Entropy Gathering Daemon (EGD). EGD is an userspace substitute for /dev/random. OpenSSL provides native support for EGD via RAND_egd to connect to the Unix domain socket, and RAND_egd_bytes to extract bytes from the daemon.

Seeds

Most random number generators require a seed. A seed is a secret, unpredictable sequence of bytes that is transformed and then used to set the initial state of the generator. The seed ensures that each unique instance of a generator produces a unique stream of bits. No two generators should ever produce the same sequence of random numbers, even when faced with Virtual Machine (VM) rollback attacks (which could happen accidentally by a data center operator).

When seeding your generators, you should use at least 256 bits (32 bytes) of material. You can verify the required number of bits by grepping the source files for #define ENTROPY_NEEDED.

Initial

OpenSSL will attempt to seed the random number generator automatically upon instantiation if the operating system provides /dev/urandom. The urandom device may lack sufficient entropy for your needs, and you might want to reseed it immediately from /dev/random. On Unix and other operating systems that provide the block device, you can use RAND_load_file to load directly from /dev/random.

int rc = RAND_load_file("/dev/random", 32);
if(rc != 32) {
    /* RAND_load_file failed */
}

/* OK to proceed */

On Windows, you should seed your generator from the Wincrypt function CryptGenRandom.

HCRYPTPROV hProvider = ...;
BYTE seed[32];
BOOL rc = 0;

rc = CryptGenRandom(hProvider, seed, sizeof(seed));
if(rc == FALSE) {
    /* CryptGenRandom failed */
}

RAND_seed(seed, sizeof(seed));
/* OK to proceed */

Reseed

The OpenSSL API allows you to provide a seed and refresh the generator's state with reseeds at anytime during the program's execution. Two functions are provided for seeding and reseeding: RAND_seed and RAND_add. RAND_seed accepts a buffer and size; while RAND_add accepts a buffer, size, and entropy estimate in bytes. RAND_seed will call RAND_add assuming 100% entropy.

RAND_seed is shown below. The function is void, so it [apparently] cannot fail (or convey failures). Though the example uses the actual number of bytes written to the buffer, the entire buffer can be used to increase entropy (with hopes the unused bytes in the buffer has entropy to extract). Though you can use uninitialized bytes as input, you should not expect any entropy in the uninitialized bytes.

byte buffer[32];
int written = get_random_bytes(buffer, sizeof(buffer));

RAND_seed(buffer, written);
/* OK to proceed */

RAND_add is similar to RAND_seed but requires an entropy estimate. The estimate should be the number of full bytes of entropy in the buffer. If you have a 32 byte buffer with about 50% entropy, you should provide 16 as the entropy estimate. RAND_add is also a void function, so it cannot fail (or convey failures). The example also uses the actual number of bytes written to the buffer, but the entire buffer can be used to increase entropy. Note that RAND_add takes a double, so be sure to avoid integer math. Otherwise, the entropy estimate calculation could result in 0.

char phrase[64];
int written = get_random_phrase(phrase, sizeof(phrase));

RAND_add(phrase, written, 0.12f * written /* 12% */);
/* OK to proceed */

On Windows machines, you can also use RAND_screen and RAND_event on Windows machines. RAND_screen will mix the contents of the screen into the generator. RAND_event can be used with programs that process Windows Messages. Both methods should only be used with interactive programs, and not services nor drivers.

Persisting

If you are worried about slow starts - or the time it takes to get the random number generator in good working order - you can write out a future seed and use it upon the next program execution. To save the future seed, use the library's RAND_save_file function. When using RAND_save_file, you only need to specify a filename. RAND_save_file returns the number of bytes written or -1 to indicate bytes were written without an appropriate seed (failure).

int written = RAND_save_file("prng-seed.bin");
if(written <= 0)
    /* RAND_save_file failed */

/* OK to proceed */

At program startup, you can attempt to read the saved seed with RAND_load_file. You can specify the number of bytes to read, or -1 to indicate the entire file should be used. The bytes read are automatically added to the generator. RAND_load_file returns the number of bytes read.

int read = RAND_load_file("prng-seed.bin", -1);
if(read <= 0)
    /* RAND_load_file failed */

/* OK to proceed */

When writing the seed to the filesystem, be sure to protect the the seed through the file system's permission scheme (Linux has not realized userland needs help from the kernel when storing secrets). On mobile devices, you should avoid writing the file and store the seed in the iOS Keychain, Android KeyChain, or Windows DPAPI.

Generation

After the generator has been seeded and is in good working order, you can extract bytes. You have three functions to extract bytes. First is RAND_bytes and the second is RAND_pseudo_bytes. Both are software based and produce a pseudo-random stream. The third method is hardware based and it reuses RAND_bytes.

Software

RAND_bytes will fetch cryptographically strong random bytes. Cryptographically strong bytes are suitable for high integrity needs, such as long term key generation. If your generator is using a software algorithm, then the bytes will be pseudo-random (but still cryptographically strong). RAND_bytes returns 1 for success, and 0 otherwise. If you changed the RAND_METHOD and it is not supported, then the function will return -1. In case of error, you can call ERR_get_error.

byte buffer[128];

int rc = RAND_bytes(buffer, sizeof(buffer));
unsigned long err = ERR_get_error();

if(rc != 1) {
    /* RAND_bytes failed */
    /* `err` is valid    */
}

/* OK to proceed */

RAND_pseudo_bytes returns pseudo-random bytes which can be cryptographically strong. The function returns 1 if the bytes are cryptographically strong, and 0 otherwise. If your application has high integrity requirements, it should not use RAND_pseudo_bytes.

When using RAND_pseudo_bytes, both 0 and 1 indicate success. If you change the RAND_METHOD and it is not supported, then the function will return -1. In case of error, you can call ERR_get_error.

byte buffer[32];

int rc = RAND_pseudo_bytes(buffer, sizeof(buffer));
unsigned long err = ERR_get_error();

if(rc != 0 && rc != 1) {
    /* RAND_pseudo_bytes failed */
    /* `err` is valid           */
}

/* OK to proceed */

Hardware

To use a hardware based random number generator, you should load the apporpriate ENGINE for the hardware based implementation. Once you set the hardware generator, you simply use RAND_bytes as discussed earlier. There are no special steps necessary after the call to load the engine.

If you have OpenSSL 1.0.1 and a machine with Core i5 or i7 processors, then the Intel Secure Key Technology (formerly called Bull Mountain) is available for you to use. Secure Key is Intel's latest hardware based random number generator. The hardware generator is accessed through the ENGINE API and wraps the rdrand instruction. According to Intel, RDRAND-enabled version of OpenSSL outperformed the non-RDRAND version by an order of magnitude.

To ensure RAND_bytes uses the hardware engine, simply call:

ENGINE_load_rdrand();

According to Intel documentation, the random number generator does not need to be seeded via the RAND_seed function because the generator is self-seeding. For optimal performance, code that is aware of the underlying random engine can forgo gathering entropy.

ENGINE_load_rdrand is a void function, so it cannot fail or cannot convey failures. The source code for is located in eng_rdrand.c and shown below.

void ENGINE_load_rdrand (void)
{
    extern unsigned int OPENSSL_ia32cap_P[];

    if (OPENSSL_ia32cap_P[1] & (1<<(62-32)))
    {
        ENGINE *toadd = ENGINE_rdrand();
        if(!toadd) return;
        ENGINE_add(toadd);
        ENGINE_free(toadd);
        ERR_clear_error();
    }
}

Miscellaneous

Two miscellaneous items remaining are generator status and cleanup.

You can query the generator's state with RAND_status. RAND_status returns 1 if the generator is in good working order. If your generator is not in good working order, you should reseed it with at least 256 bits (32 bytes) of entropy. The function purposefully hides the number of bytes needed.

RAND_cleanup securely erases the memory used by the random number generator.

FIPS Mode

Thread Safety