RandomNumberGenerator

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

Random numbers are a primitive for cryptographic operations. The library abstracts them with the RandomNumberGenerator base class and its derivatives. Some of the generators are cryptographically secure, while others are not.

In general, use an AutoSeeded generator, and add entropy to the generator before extracting bits. Entropy should 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.

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

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.

Finally, the library does not offer the generators specified by NIST SP800-90A, Recommendation for Random Number Generation Using Deterministic Random Bit Generators. This is important because the ANSI X9.17 and X9.31 generators are in deprecated status, and must not be used after 2015. See SP800-131 for details.

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

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.

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.

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.

RandomPool

RandomPool
Documentation
#include <cryptopp/randpool.h>

RandomPool is a PGP style random pool. Early versions of RandomPool used MDC<SHA> via typedef MDC<SHA> RandomPoolCipher.

Current versions of RandomPool used use AES. From 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() );

AutoSeededRandomPool

AutoSeededRandomPool
Documentation
#include <cryptopp/osrng.h>

Unlike LG_RNG and RandomPool, AutoSeeded generators do not require a seed. An auto seeded random pool was suggested by [?], 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() );

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() ));

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

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.