Random Numbers

From OpenSSLWiki

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.

Good random numbers are notoriously hard to produce 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.

Contents

[edit] 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%). Other sources used as a random stream will have different estimates of entropy, and you will have to determine the quality.

Random number generators require 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).

[edit] Sources

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.

[edit] Testing

It is not possible to assess whether a source of randomness is truly random by merely examining its bits. An "ideal" source of truly random data can be thought of as a sequence of binary digits where each 1 or 0 is the result of flipping a perfectly fair, unbiased coin. Such a sequence of digits would have the following properties:

  • Each digit would have exactly 0.5 probability of being 1 and 0.5 probability of being 0
  • The production of any one digit would be entirely independent of any other digits

Given any arbitrary sequence of binary digits it is possible to examine it using statistical techniques. There are various suites of statistical tests available such as STS (Statistical Test Suite) available from NIST's RANDOM NUMBER GENERATION page. This suite provides a number of different tests including:

  • The Frequency (Monobit) Test: Checks whether the proportion of 0s and 1s in a given sequence are approximately as one would expect
  • The Runs Test: Tests whether the number of runs of consecutive identical digits of varying lengths within a given sequence is as expected
  • The Longest Run of Ones in a block: Confirms whether the longest single run of ones within a sequence is as would be expected

Examining random data using the tests above cannot determine whether a data source is truly random or not. However, it can indicate whether data is likely to be non-random.

[edit] 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.

[edit] Initialization

OpenSSL will attempt to seed the random number generator automatically upon instantiation by calling RAND_poll. RAND_poll seeds the random number generator using a system-specific entropy source, which is /dev/urandom on UNIX-like operating systems, and is a combination of CryptGenRandom and other sources of entropy on Windows.

Be careful when deferring to RAND_poll on some Unix systems because it does not seed the generator. See the code guarded with OPENSSL_SYS_VXWORKS in rand_unix.c. Additionally, RAND_poll can have negative interactions on newer Windows platforms, so your program could hang or crash depending on the potential issue. See Windows Issues below.

If the random number generator is not properly seeded, then it refuse to deliver random bytes and a "PRNG not seeded error" will occur.

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 */

[edit] 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. Even though you can use uninitialized bytes as input, you should not expect any entropy in the uninitialized bytes. Finally, the function get_random_bytes is a placeholder for an application supplied function which gathers random data.

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. 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.

RAND_poll can be used to reseed the generator using the system entropy source.

[edit] 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");
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", -1);
if(read <= 0)
    /* RAND_load_file failed */

/* OK to proceed */

If possible, you should use protected storage offered by the operating system. For example, you should avoid writing the file and store the seed in the iOS Keychain, Android KeyChain, or Windows DPAPI. 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).

[edit] 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.

[edit] 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 */

[edit] Hardware

Hardware random number generators are almost always better to use than a software based generator. Hardware generators are often called True Random Number generators (TRNG) or Non-Deterministic Random Number Generators since they don't rely on the deterministic behavior of executing software instructions. Their bits streams are nearly always indistinguishable from random streams, and their entropy is always nearly 100%.

Some hardware generators are easier to use than other. For example, an EntropyKey will provide a driver that replenishes /dev/random, so an application does not have to do anything special other than reading from the device. Other generators, such as Intel's Secure Key, must be integrated into an application. When integrating generators using OpenSSL, you will use the library's ENGINE API.

To integrate a hardware based random number generator, you should load the apporpriate ENGINE for the hardware based implementation. Once loaded, set the engine's RAND_method method as default with ENGINE_METHOD_RAND. After you load the engine and set RAND_method for the hardware generator, you simply use RAND_bytes as discussed earlier. There are no special steps necessary after the configuration.

If you have OpenSSL 1.0.1 and a machine with 3rd generation Core i5 or i7 processor (Ivy Bridge), then the Intel Secure Key Technology (formerly called Bull Mountain) [disclaimer] is available to you. 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, you must perform three steps:

  • load the rdrand engine
  • acquire a handle to the engine
  • set the default RAND_method to the engine

The code below shows you how to load the Intel random number generator engine and set the default RAND_method. The code is available for download at test-rdrand.c. While you can call ENGINE_load_builtin_engines to make all engines available, the code below focuses on the one engine of interest and loads it via ENGINE_load_rdrand. Before the call to ENGINE_load_rdrand, be sure to call OPENSSL_cpuid_setup to load the proper CPU capabilities. See OpenSSL's engine(3) for more details on engines, their loading, and operation.

Displaying the error code in hexadecimal gives you an error that is easily consumed by openssl errstr.

 1    unsigned long err = 0;
 2    int rc = 0;
 3
 4    OPENSSL_cpuid_setup();
 5    ENGINE_load_rdrand();
 6
 7    ENGINE* eng = ENGINE_by_id("rdrand");
 8    err = ERR_get_error();
 9
10    if(NULL == eng) {
11        fprintf(stderr, "ENGINE_load_rdrand failed, err = 0x%lx\n", err);
12        abort(); /* failed */
13    }
14
15    rc = ENGINE_init(eng);
16    err = ERR_get_error();
17
18    if(0 == rc) {
19        fprintf(stderr, "ENGINE_init failed, err = 0x%lx\n", err);
20        abort(); /* failed */
21    }
22  
23    rc = ENGINE_set_default(eng, ENGINE_METHOD_RAND);
24    err = ERR_get_error();
25
26    if(0 == rc) {
27        fprintf(stderr, "ENGINE_set_default failed, err = 0x%lx\n", err);
28        abort(); /* failed */
29    }
30
31    /* OK to proceed */
32
33    ...
34    ENGINE_finish(eng);
35    ENGINE_free(eng);
36    ENGINE_cleanup();

If you hardware does not support the Intel generator, you will receive a NULL pointer at line 7 and encounter error 0x2606c043 at line 8. The error can then be fed to openssl errstr:

$ ./test-rdrand.exe
...
ENGINE_load_rdrand failed, err = 0x2606c043
$ openssl errstr 0x2606c043
error:2606C043:engine routines:ENGINE_FREE_UTIL:passed a null parameter
Verifying rdrand code path
Line 13 attempts to set the default RAND_method to that provided by the engine using ENGINE_set_default with ENGINE_METHOD_RAND. Upon success, OpenSSL will internally use OPENSSL_ia32_rdrand for random number generation. To verify code correctness, simply set a breakpoint on the function and wait for the debugger to snap as shown in the figure to the right.

The 0x2606c043 error is actually caused by ENGINE_load_rdrand. The function will verify the capabilities of the hardware and load the generator's engine if available. ENGINE_load_rdrand is a void function, so it cannot fail or cannot convey failures (which we know is incorrect from a test run). The source code can be found in eng_rdrand.c and is 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();
    }
}

A patch is available to provide ENGINE_R_NO_SUCH_ENGINE error code for non-RdRand CPUs. See [openssl.org #3143]: ENGINE_load_rdrand sane failure code for details.

$ ./test-rdrand.exe
...
ENGINE_load_rdrand failed, err = 0x26077074
$ openssl errstr 0x26077074
error:26077074:engine routines:ENGINE_init:no such engine

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.

Additionally (or more importantly), the following will not cause a crash when using the hardware random number generator (and it fails silently so all looks good from outside the fishbowl):

/* Bad - don't do this in production */
byte seed[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
RAND_seed(seed, sizeof(seed));

Finally, you can test if your Mac OS X system has rdrand available with the following (thanks to Dave Zarzycki):

$ sysctl hw.optional.rdrand
hw.optional.rdrand: 1

On Linux, you can cat cpuinfo:

$ cat /proc/cpuinfo | grep -i rdrand
rdrand	: 1

[edit] Windows Issues

Windows platforms offer two potential problems to OpenSSL's RAND_poll. First is a hang due to the heap walk, and second is Application Verifier failures due to use of Windows' API call netstatget.

See Bug 2100 for details on the heap walk issue. See UAC related errors on windows 7 64-bit with Application Verifier for details and a workaround for the Application Verifier issue.

[edit] Miscellaneous

Two miscellaneous items remaining are generator cleanup and status. RAND_cleanup securely erases the memory used by the random number generator.

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 for the reseed operation.

On Android, take care to specify -mfloat-abi=softfp when building the library for use via JNI. If you specify -mfloat-abi=hard or -mhard-float (even if the hardware support a floating point unit), then the entropy estimate passed to RAND_add will always be 0.0f. See Hard-float and JNI for details.

By default, OpenSSL will use the RDRANG engine to generate random numbers if the hardware is available. The behavior has been changed, but the change is only available through git at the moment. If you are concerned with RDRANG tampering, then see the discussion of ENGINEs and RDRAND.

[edit] FIPS Mode

FIPS mode is a special mode of operation which specifies the library should operate according to the security policies and procedures specified in FIPS 140-2. The mode requires use of the FIPS Capable OpenSSL library, and must be enabled with a call to FIPS_mode_set. Once in FIPS mode, a default DRBG is used as specified in SP800-90.

The default DRBG is 256-bit CTR AES using a derivation function, and is decided by the application and not the library module. In the case of an OpenSSL application it is specified in rand_lib.c via the OPENSSL_DRBG_DEFAULT_TYPE and OPENSSL_DRBG_DEFAULT_FLAGS preprocessor macros to allow them to be overridden by local compilation options or at runtime.

To use the FIPS random number generator, simply use RAND_bytes as described earlier. Note that the call to FIPS_mode_set must succeed in order to operate in FIPS 140 mode.

[edit] Thread Safety

The random number generators (among other parts of OpenSSL) are not thread safe by default. To ensure thread safety, you must call CRYPTO_set_locking_callback.

[edit] Fork Safety

OpenSSL's random number generator is not fork-safe, so the issue should be carefully understood and remediated if necessary. See Random Fork-Safety for details.

[edit] See also

Personal tools