RandomNumberGenerator

From Crypto++ Wiki
(Redirected from LCG)
Jump to navigation Jump to search
RandomNumberGenerator
Documentation
#include <cryptopp/cryptlib.h>

Random numbers are a primitive for cryptographic operations. They are used frequently, from generating asymmetric and symmetric keys, to initialization vectors, salts and nonces. The library abstracts them with the RandomNumberGenerator base class and its derivatives. Some of the generators are cryptographically secure, while others are not.

RandomNumberGenerator is intended to set up the interface, and you should not instantiate one. Trying to generate random numbers with RandomNumberGenerator will result in infinite stack recursion. It is OK to use a RandomNumberGenerator pointer or reference since polymorphism will ensure the derived object's implementation is used.

In general, use an auto-seeded generator like AutoSeededRandomPool. AutoSeeded* generators automatically seed the generator using the underlying OS's entropy pools. Entropy is retrieved using Crypto++'s OS_GenerateRandomBlock. On Linux, OS_GenerateRandomBlock uses /dev/random (blocking=true) or /dev/urandom (blocking=false); on Windows, it uses CryptGenRandom, and on the BSDs, it uses /dev/srandom (blocking=true) or /dev/urandom (blocking=false).

In addition to automatice seeds, you should seed the generator with any entropy you can get your hands on, even less than perfect ones. Entropy can include anything specific to the use, including any entropy a peer offers like a nonce used during key exchange. Using the peer's entropy before extracting your random bits will help mitigate some classes of attacks, like Virtual Machine playback attacks.

If you are using a generator in a multithreaded program, then use a single generator per thread or provide an external lock for a single generator. Wei Dai recommends using a generator on a per thread basis. Additionally, see WORKAROUND_MS_BUG_Q258000.

You should reseed the generator after a fork() to avoid multiple generators with the same internal state.

DefaultAutoSeededRNG

The library provides a typedef for DefaultAutoSeededRNG. In the non-FIPS DLL builds DefaultAutoSeededRNG is AutoSeededRandomPool. In the former FIPS DLL builds the library used AutoSeededX917RNG as the typedef. Both generators use OS_GenerateRandomBlock to gather seed material, so neither generator suffered the DUHK attacks.

OS Entropy

You can use OS_GenerateRandomBlock to gather entropy using whatever the underlying operating system provides. OS_GenerateRandomBlock is a global function, and not tied to any class.

On Linux, OS_GenerateRandomBlock uses /dev/random (blocking=true) or /dev/urandom (blocking=false); on Windows, it uses CryptGenRandom; and on the BSDs, it uses /dev/srandom (blocking=true) or /dev/urandom (blocking=false).

According to Theodore Ts'o on the Linux Kernel Crypto mailing list, Linux's /dev/random has been deprecated for a decade. From RFC PATCH v12 3/4: Linux Random Number Generator:

Practically no one uses /dev/random. It's essentially a deprecated interface; the primary interfaces that have been recommended for well over a decade is /dev/urandom, and now, getrandom(2).

OS_GenerateRandomBlock

OS_GenerateRandomBlock
Documentation
#include <cryptopp/osrng.h>

OS_GenerateRandomBlock is used to gather entropy using the OS and its signature is shown below:

void OS_GenerateRandomBlock(bool blocking, byte *output, size_t size)

Once you gather entropy with OS_GenerateRandomBlock, you can use it directly or use it to seed a generator. Below, the entropy is used directly for a key and initialization vector. The key draws from /dev/random, while the iv draws from /dev/urandom on Linux.

SecByteBlock key(AES::DEFAULT_KEYLENGTH), iv(AES::BLOCKSIZE);
string k,v;

OS_GenerateRandomBlock(true, key, key.size());
OS_GenerateRandomBlock(false, iv, iv.size());

HexEncoder hex(new StringSink(k));
hex.Put(key, key.size());
hex.MessageEnd();

hex.Detach(new StringSink(v));
hex.Put(iv, iv.size());
hex.MessageEnd();

cout << "Key: " << k << endl;
cout << "IV: " << v << endl;

The program will produce an output similar to below.

$ ./cryptopp-test.exe
Key: 774353D982E1A1FD4334C5D5D3AF9314
IV: 503E428E63E999B3D7E6CCDE0143197A

Seeding

Nearly all generators should be seeded before use. To test if a generator can incorporate a seed, call CanIncorporateEntropy. CanIncorporateEntropy will return true if the generator can incorporate a seed. Some generators, like Intel's deterministic random-bit generator (accessed via RDRAND) cannot accept entropy.

To seed or reseed a generator that accepts a seed, call IncorporateEntropy to add the entropy to the generator.

If you are using an AutoSeeded* generator, then the library will attempt to seed the generator for you using the underlying OS's entropy pool by way of OS_GenerateRandomBlock. You can call still seed an auto-seeded generator and add more entropy if you have it.

You should reseed the generator after a fork() to avoid multiple generators with the same internal state.

IncorporateEntropy

To seed one of the Crypto++ random number generators, call the IncorporateEntropy function. It takes a pointer to a byte block and a length:

void IncorporateEntropy (const byte *input, size_t length)

A sample using IncorporateEntropy is shown below.

RandomPool prng;
SecByteBlock seed(32);

OS_GenerateRandomBlock(false, seed, seed.size());
prng.IncorporateEntropy(seed, seed.size());

string s;
HexEncoder hex(new StringSink(s));

hex.Put(seed, seed.size());
hex.MessageEnd();

cout << "Seed: " << s << endl;

The program will produce an output similar to below.

$ ./cryptopp-test.exe
Seed: 6BA0DC9C85A7133287A70A4C14BCA3B150025B3F621C8930B08A91F304245067

RandomNumberSink

RandomNumberSink
Documentation
#include <cryptopp/filters.h>

A RandomNumberSink allows you to add entropy to a generator. Internally, it calls IncorporateEntropy for you. Note: this is one of the times pumpAll = false is used for a Source.

const unsigned int BLOCKSIZE = 16 * 8;
SecByteBlock scratch( BLOCKSIZE );

RandomPool prng;
FileSource entropy("/dev/urandom", false, new RandomNumberSink(prng));

// Add 16 bytes of entropy before generating a block of random bits
entropy.Pump(16);
prng.GenerateBlock( scratch, scratch.size() );

// Add 16 bytes of entropy before generating a block of random bits
entropy.Pump(16);
prng.GenerateBlock( scratch, scratch.size() );
...

Generation

This section details how to generate random numbers using the different generators. In general, you should seed a generator immediately before using it to generate bits. You should do so before each call, and not just once. Doing so helps avoid virtual machine playback attacks.

There are generally two ways to get a random number from a generator. First is with GenerateBlock, and second is with GenerateIntoBufferedTransformation. GenerateBlock takes a pointer to a buffer and a length. Internally, GenerateBlock wraps the buffer in an ArraySource and then calls GenerateIntoBufferedTransformation. The second method is GenerateIntoBufferedTransformation and its where the real work is performed. When generating into the BufferedTransformation, the generator produces the stream and places it in the specified channel.

LC_RNG

LC_RNG
Documentation
#include <cryptopp/rng.h>

LC_RNG is a Linear Congruential Generator. Though this generator has no cryptographic value, it does allow one to reproduce results when debugging a program. Additionally, it is generally faster at generating a byte block (or stream). If one seeds the LCG with 0x00, a steady stream of 0x80 is the result. Other seeds perform as expected.

If you want to use the original constants as specified in S.K. Park and K.W. Miller's CACM paper, then you should #define LCRNG_ORIGINAL_NUMBERS before compiling the Crypto++ library. The define is available in config.h.

Current RandomPool

RandomPool
Documentation
#include <cryptopp/randpool.h>

RandomPool is a PGP style random pool. Crypto++ 5.5 and later versions of RandomPool use AES and are hardened against VM rollback attacks. Crypto++ 5.4 and early followed PGP 2.6.x and used MDC<SHA> via typedef MDC<SHA> RandomPoolCipher. From the current randpoool.cpp:

RandomPool::RandomPool()
    : m_pCipher(new AES::Encryption), m_keySet(false)
{
    memset(m_key, 0, m_key.SizeInBytes());
    memset(m_seed, 0, m_seed.SizeInBytes());
}

RandomPool uses time, so each run of the generator will produce different results. But the difference between runs is weak (it only differs by the time of the call), so be sure to seed the generator with unpredictable data.

Using the generator is similar to the following:

// Must be at least 16 for RandomPool
const unsigned int SEEDSIZE = 16;
SecByteBlock seed( SEEDSIZE );

// Scratch Area
const unsigned int BLOCKSIZE = 16 * 8;
SecByteBlock scratch( BLOCKSIZE );
...

// Random Pool Initalization
CryptoPP::RandomPool rng( SEEDSIZE );
rng.IncorporateEntropy( seed, seed.size() );
    
rng.GenerateBlock( scratch, scratch.size() );

Old RandomPool

If you need the old RandomPool generator which uses MDC<SHA> then you can find it at OldRandomPool. The OldRandomPool class was added at Crypto++ 6.0 to help provide an upgrade path. For Crypto++ 5.6.5 and earlier, you must apply the 6.0 change yourself. The check-ins of interest are Commit 02e3a794443a, Add OldRandomPool class (Issue 452) and Commit 5fbbc5311cea, Add self tests for OldRandomPool (Issue 452). The issue was tracked at Issue 452, Add OldRandomPool for pre-Crypto++ 5.5 compatibility.

There's now a wiki page about it at Old RandomPool.

AutoSeededRandomPool

AutoSeededRandomPool
Documentation
#include <cryptopp/osrng.h>

Unlike LC_RNG and RandomPool, AutoSeeded generators do not require a seed. An auto seeded random pool was suggested by Leonard Janke, which Wei later incorporated into Crypto++ with version [?].

// Scratch Area
const unsigned int BLOCKSIZE = 16 * 8;
SecByteBlock scratch( BLOCKSIZE );

// Construction
CryptoPP::AutoSeededRandomPool rng;

// Random Block
rng.GenerateBlock( scratch, scratch.size() );

AutoSeededX917RNG

AutoSeededX917RNG
Documentation
#include <cryptopp/osrng.h>

When using an X9.17 generator, you must specify an approved Block Cipher as a template parameter. If you use TripleDES (DES_EDE3), then its an X9.17 generator. If you use AES (AES), then its an X9.31 generator (the underlying algorithm did not change).

// Scratch Area
const unsigned int BLOCKSIZE = 16 * 8;
SecByteBlock scratch( BLOCKSIZE );

// Construction
CryptoPP::AutoSeededX917RNG<CryptoPP::DES_EDE3> rng;

// Random Block
rng.GenerateBlock( scratch, scratch.size() );

RDRAND

RDRAND
Documentation
#include <cryptopp/rdrand.h>

The library provides the RDRAND generator. The following demonstrates using the generator.

SecByteBlock key(AES::DEFAULT_KEYLENGTH), iv(AES::BLOCKSIZE);
string k,v;

RDRAND prng;
if (prng.Available())
{
    prng.GenerateBlock(key, key.size());
    prng.GenerateBlock(iv, iv.size());

    HexEncoder hex(new StringSink(k));
    hex.Put(key, key.size());
    hex.MessageEnd();

    hex.Detach(new StringSink(v));
    hex.Put(iv, iv.size());
    hex.MessageEnd();

    cout << "Key: " << k << endl;
    cout << "IV: " << v << endl;
}
else
{
    cout << "Failed to generate Key and IV" << endl;
}

If you call GenerateBlock on a machine without RDRAND circuit, then a RDRAND_Err exception will be thrown.

NIST DRBG

NIST_DRBG
Documentation
#include <cryptopp/drbg.h>

The library provides two NIST's Deterministic Random Bit Generators (DRBGs). They are Hash_DRBG, and HMAC_DRBG. They are discussed at NIST DRBGs wiki page.

The generators have their own page because they are trickier to use due to randomness requirements during instantiation. In addition, they accept at least three other types of randomness distinct from the entropy required during instantiation.

RandomNumberSource

RandomNumberSource
Documentation
#include <cryptopp/filters.h>

A RandomNumberSource allows you to use a generator in a pipeline.

const unsigned int BLOCKSIZE = 16 * 8;
SecByteBlock scratch( BLOCKSIZE );

AutoSeededRandomPool prng;

// Extract BLOCKSIZE bytes of random bits
RandomNumberSource(prng, scratch.size(), true, new ArraySink( scratch, scratch.size() ));

Creating a Generator

If you would like to create generator, then derive a class from RandomNumberGenerator and provide the implementation. You must provide an override for GenerateBlock. The library's default implementation for GenerateIntoBufferedTransformation should be sufficient.

By default, the library returns false for CanIncorporateEntropy, so be sure to override it as required.

Example Generator

You can find an example of creating a generator at Mersenne Twister. The generator is somewhat tricky to implement because it is word oriented, and not byte oriented.

The Mersenne Twister provides overrides for GenerateBlock, GenerateWord32 and Discard. Because the generator is word oriented, there are two implications for an implementation. First, the result of GenerateWord32 must be consistent with the result of calling GenerateBlock with 1, 2, 3 and 4 byte arrays. For example, if GenerateWord32 returns 0xD091BB5C, then GenerateBlock must return 0xD0 0x91 0xBB 0x5C for 1, 2, 3 and 4 byte arrays. Second, Discard rounds up to a multiple of a word size, and then discards the required number of words (and not bytes).

Reproducibility

If you need a generator to reproduce results between runs, then you have three choices. First is to use LC_RNG, second is to use OFB_Mode<T>::Encryption or CTR_Mode<T>::Encryption, and third is to use AES_RNG. AES_RNG is not part of the Crypto++ library, but you can download it below.

OFB_Mode<T>::Encryption

OFB_Mode<T>::Encryption is used by the Crypto++ library in test.cpp to generate random numbers (where T is a block cipher like AES). The encryptor subscribes to the RandomNumberGenerator interface by way of AdditiveCipherTemplate<T>, so it can be used anywhere a Crypto++ generator is required.

Seeding occurs by keying the cipher. Keying the cipher with the same key and IV will produce the same bit stream. In the case of test.cpp, time is used, so the results can be reproduced using the same time string (the time used is printed to the console during a run of cryptest.exe v).

Note: other modes, like CBC and CFB, do not inherit from AdditiveCipherTemplate<T>, so they cannot be used as a random number generator.

An example of using OFB_Mode<T>::Encryption is shown below. Notice a random seed is fetched from the OS using OS_GenerateRandomBlock, and then same seed is used to key the cipher in the loop.

SecByteBlock seed(32 + 16);
OS_GenerateRandomBlock(false, seed, seed.size());

for(unsigned int i = 0; i < 10; i++)
{
    OFB_Mode<AES>::Encryption prng;
    prng.SetKeyWithIV(seed, 32, seed + 32, 16);

    SecByteBlock t(16);
    prng.GenerateBlock(t, t.size());

    string s;
    HexEncoder hex(new StringSink(s));

    hex.Put(t, t.size());
    hex.MessageEnd();

    cout << "Random: " << s << endl;
}

Running the program produces results similar to below.

$ ./cryptopp-test.exe
Random: DF3D3F8E8A21C39C0871B375013AA2CD
Random: DF3D3F8E8A21C39C0871B375013AA2CD
Random: DF3D3F8E8A21C39C0871B375013AA2CD
Random: DF3D3F8E8A21C39C0871B375013AA2CD
Random: DF3D3F8E8A21C39C0871B375013AA2CD
Random: DF3D3F8E8A21C39C0871B375013AA2CD
Random: DF3D3F8E8A21C39C0871B375013AA2CD
Random: DF3D3F8E8A21C39C0871B375013AA2CD
Random: DF3D3F8E8A21C39C0871B375013AA2CD
Random: DF3D3F8E8A21C39C0871B375013AA2CD

CTR_Mode<T>::Encryption

In addition to OFB_Mode<T>::Encryption, CTR_Mode<T>::Encryption (where T is a block cipher like AES) allows you to use the block cipher as a random number generators because CTR mode inherits from AdditiveCipherTemplate<T>. As with OFB mode, CTR mode seeding occurs by keying the cipher. Keying the cipher with the same key and IV will produce the same bit stream.

The sample code is left as an exercise to the reader, but it does not differ much from the example for OFB_Mode<T>::Encryption. Just copy and paste and it should work.

AES_RNG

The AES_RNG generator uses AES-256, and it will be strong enough to meet most needs as long as its used correctly. It also allows you to use an arbitrarily sized seed because it relies upon SHA-512 to expand then extract entropy that is used to key the underlying cipher.

If you supply a seed, then the generator will always produce the same sequence because it forgoes calls to time when generating a sequence. Repeating a sequence would usually be considered "using the generator incorrectly". If you don't provide a seed to the constructor, then the generator will use OS_GenerateRandomBlock and each run will produce different results. This is usually considered "using the generator correctly".

An example of using AES_RNG is shown below. Notice a random seed is fetched from the OS using OS_GenerateRandomBlock, and then same seed is used in the AES_RNG constructor within the loop.

// Example of using a seed for reproducible results.
SecByteBlock seed(32);
OS_GenerateRandomBlock(false, seed, seed.size());

for(unsigned int i = 0; i < 10; i++)
{
    AES_RNG prng(seed, seed.size());
    
    SecByteBlock t(16);
    prng.GenerateBlock(t, t.size());
    
    string s;
    HexEncoder hex(new StringSink(s));
    
    hex.Put(t, t.size());
    hex.MessageEnd();
    
    cout << "Random: " << s << endl;
}

Running the program produces results similar to below.

$ ./cryptopp-test.exe
Random: B40DEFDE59036914A513711803B52F3C
Random: B40DEFDE59036914A513711803B52F3C
Random: B40DEFDE59036914A513711803B52F3C
Random: B40DEFDE59036914A513711803B52F3C
Random: B40DEFDE59036914A513711803B52F3C
Random: B40DEFDE59036914A513711803B52F3C
Random: B40DEFDE59036914A513711803B52F3C
Random: B40DEFDE59036914A513711803B52F3C
Random: B40DEFDE59036914A513711803B52F3C
Random: B40DEFDE59036914A513711803B52F3C

Test Suite and GlobalRNG

The test and validation suites use GlobalRNG declared in validate.h and defined in test.cpp. GlobalRNG is simply a function:

RandomNumberGenerator & GlobalRNG()
{
    static OFB_Mode<AES>::Encryption s_globalRNG;
    return dynamic_cast<RandomNumberGenerator&>(s_globalRNG);
}

Before using GlobalRNG, the test suite seeds the generator like so:

// Pad the seed with space to make it easier to reproduce results
std::string seed = IntToString(time(NULL));
seed.resize(16, ' ');

OFB_Mode<AES>::Encryption& prng = dynamic_cast<OFB_Mode<AES>::Encryption&>(GlobalRNG());
prng.SetKeyWithIV((byte *)seed.data(), 16, (byte *)seed.data());

You should not use the test suite's GlobalRNG because you will have undefined symbol errors during link since your project does not include the test.cpp source file from the test suite.

Alternate Generators

If you need a generator similar in form and function to GlobalRNG, then use an AutoSeededRandomPool. Its one of the easiest generators to use safely.

You can also copy/paste the code above into your project. Be aware of the pitfalls in making s_globalRNG static, especially if its being used in other compilation units. If you want to avoid the C++ static initialization problems, then don't use the generator across translation units. Instead, create a local RNG in a function when its needed. Also see Static Initialization Order Fiasco on the wiki.

Windows Phone 8 and Windows Store 8

Crypto++ is multi-platform, and the platforms include traditional Windows desktops and servers. Crypto++ 5.6.4 increased support for Windows Phone, Windows Store and Universal Windows Platform (UWP). Improved support includes better platform integration and specialized ARM implementations. Also see Issue 143: Support for Universal Windows Platform (UWP) and Issue 164: Need NonblockingRng based on BCryptGenRandom for Windows on the GitHub bug tracker.

Random numbers can be a problem on Windows Phone 8 and Windows Store 8 because Microsoft does not provide a way for the library to obtain random numbers for its AutoSeeded generators. The coverage of the WinCrypt API and CryptoNG API simply has a big hole at Windows Phone 8 and Windows Store 8.

When compiling osrng.cpp you may see the following warning:

cl.exe /nologo /W4 /D_MBCS /Zi /TP /EHsc /MD /FI sdkddkver.h /FI winapifamily.h
/DWINAPI_FAMILY=WINAPI_FAMILY_PHONE_APP /c osrng.cpp
osrng.cpp
WARNING: Compiling for Windows but an OS RNG is not available. This is likely a
Windows Phone 8 or Windows Store 8 app.

Remediations

There are a few ways to approach the Windows Phone 8 and Windows Store 8 gaps. First, you can abandon the platform. This appears to be the strategy used by Microsoft.

Second, you can call the managed CryptographicBuffer.GenerateRandom method for random numbers. You can also instantiate a non-AutoSeeded generator and seed it from CryptographicBuffer.GenerateRandom.

Third, you can set WINVER or _WIN32_WINNT to 0x0A00. 0x0A00 is Windows 10, and it signals Windows Phone 10, Windows Store 10 and Windows Universal Platform. Microsoft provides Bcrypt for this platform, so the library can obtain random numbers without the need for the managed CryptographicBuffer.GenerateRandom.

Fourth, you can sample sensor data and use the sampled data as the seed to a non-AutoSeeded generator. If you select this option, then be sure to extract entropy with a function like HKDF. Also be aware that sensors vary among devices - some devices are sensor rich, and other devices are sensor anemic. Anemic devices usually have one sensor and its an accelerometer for gaming. Examples of using this technique are available for Android and iOS, but not Windows Phone and Windows Store. Also see Android Activity on the Crypto++ wiki.

Sample Programs

LCG.zip - Demonstrates using the Linear Congruential PRNG to generate pseudo random bytes

RandomPool.zip - Demonstrates using a RandomPool to generate pseudo random bytes

AutoSeededX917.zip - Demonstrates using a AutoSeededX917RNG to generate pseudo random bytes

ASRP.zip - Demonstrates using an AutoSeededRandomPool to generate pseudo random bytes

AES_RNG.zip - AES-256 based random number generator that produces the same bit stream given the same seed is used in the constructor.

mersenne.zip - patch to provide Mersenne Twister implementation for Crypto++.