The Implementation of Random_Device in VS2010

The implementation of random_device in VS2010?

According to a comment left on this question by Hans Passant, random_device uses advapi32:SystemFunction036, which according to MSDN is an alias for RtlGenRandom. This is verified by the runtime library source provided with VC++ 2010:

random_device::operator()() in <random> calls the following chain of functions:

_Random_device() // in xrngdev.cpp
    rand_s()     // in rand_s.c
        RtlGenRandom()/SystemFunction036()  // in advapi32.dll

According to a comment left by Michael Howard on one of his blog articles, "Cryptographically Secure Random number on Windows without using CryptoAPI", RtlGenRandom uses the following:

The RNG generates as specified in FIPS 186-2 appendix 3.1 with SHA-1
as the G function. With entropy from:
The current process ID (GetCurrentProcessID).
The current thread ID (GetCurrentThreadID).
The ticks since boot (GetTickCount).
The current time (GetLocalTime).
Various high-precision performance counters (QueryPerformanceCounter).
An MD4 hash of the user's environment block, which includes username, computer name, and search path. MD4 is a hashing algorithm
that creates a 128-bit message digest from input data to verify data
integrity.
High-precision internal CPU counters, such as RDTSC, RDMSR, RDPMC
Low-level system information: Idle Process Time, Io Read Transfer Count, I/O Write Transfer Count, I/O Other Transfer Count, I/O Read
Operation Count, I/O Write Operation Count, I/O Other Operation Count,
Available Pages, Committed Pages, Commit Limit, Peak Commitment, Page
Fault Count, Copy On Write Count, Transition Count, Cache Transition
Count, Demand Zero Count, Page Read Count, Page Read I/O Count, Cache
Read Count, Cache I/O Count, Dirty Pages Write Count, Dirty Write I/O
Count, Mapped Pages Write Count, Mapped Write I/O Count, Paged Pool
Pages, Non Paged Pool Pages, Paged Pool Allocated space, Paged Pool
Free space, Non Paged Pool Allocated space, Non Paged Pool Free space,
Free System page table entry, Resident System Code Page, Total System
Driver Pages, Total System Code Pages, Non Paged Pool Lookaside Hits,
Paged Pool Lookaside Hits, Available Paged Pool Pages, Resident System
Cache Page, Resident Paged Pool Page, Resident System Driver Page,
Cache manager Fast Read with No Wait, Cache manager Fast Read with
Wait, Cache manager Fast Read Resource Missed, Cache manager Fast Read
Not Possible, Cache manager Fast Memory Descriptor List Read with No
Wait, Cache manager Fast Memory Descriptor List Read with Wait, Cache
manager Fast Memory Descriptor List Read Resource Missed, Cache
manager Fast Memory Descriptor List Read Not Possible, Cache manager
Map Data with No Wait, Cache manager Map Data with Wait, Cache manager
Map Data with No Wait Miss, Cache manager Map Data Wait Miss, Cache
manager Pin-Mapped Data Count, Cache manager Pin-Read with No Wait,
Cache manager Pin Read with Wait, Cache manager Pin-Read with No Wait
Miss, Cache manager Pin-Read Wait Miss, Cache manager Copy-Read with
No Wait, Cache manager Copy-Read with Wait, Cache manager Copy-Read
with No Wait Miss, Cache manager Copy-Read with Wait Miss, Cache
manager Memory Descriptor List Read with No Wait, Cache manager Memory
Descriptor List Read with Wait, Cache manager Memory Descriptor List
Read with No Wait Miss, Cache manager Memory Descriptor List Read with
Wait Miss, Cache manager Read Ahead IOs, Cache manager Lazy-Write IOs,
Cache manager Lazy-Write Pages, Cache manager Data Flushes, Cache
manager Data Pages, Context Switches, First Level Translation buffer
Fills, Second Level Translation buffer Fills, and System Calls.
System exception information consisting of Alignment Fix up Count, Exception Dispatch Count, Floating Emulation Count, and Byte Word
Emulation Count.
System lookaside information consisting of Current Depth, Maximum Depth, Total Allocates, Allocate Misses, Total Frees, Free Misses,
Type, Tag, and Size.
System interrupt information consisting of context switches, deferred procedure call count, deferred procedure call rate, time
increment, deferred procedure call bypass count, and asynchronous
procedure call bypass count.
System process information consisting of Next Entry Offset, Number Of Threads, Create Time, User Time, Kernel Time, Image Name, Base
Priority, Unique Process ID, Inherited from Unique Process ID, Handle
Count, Session ID, Page Directory Base, Peak Virtual Size, Virtual
Size, Page Fault Count, Peak Working Set Size, Working Set Size, Quota
Peak Paged Pool Usage, Quota Paged Pool Usage, Quota Peak Non Paged
Pool Usage, Quota Non Paged Pool Usage, Page file Usage, Peak Page
file Usage, Private Page Count, Read Operation Count, Write Operation
Count, Other Operation Count, Read Transfer Count, Write Transfer
Count, and Other Transfer Count.

There's a full explanation (including diagrams) in Chapter 8 of Writing Secure Code, 2nd Edition.

How do I use boost::random_device to generate a cryptographically secure 64 bit integer?

Analyzing your question is harder than it might seem:

You seed the mersenne twister with rd(), which returns an unsigned int, and therefore (on most platforms) contains at most 32 random bits.

Everything that the mersenne twister does from this point on is determined by those 32 bits.

This means that the value can only take on 2**32 different values, which can be a problem if any attack vector exists that attacks whatever you do with this number by brute force. In fact, the mersenne twister's seeding routine may even reduce the number of possible values for the first result, since it distributes the 32 random bits over its complete state (to ensure that this is not the case you would have to analyse the seed routine boost uses).

The primary weakness of the mersenne twister (its state can be derived after seeing 624 numbers) is not even of interest in this case however, since you generate a sequence that is so short (1 value).

Generating 64 cryptographically secure bits

Assuming that unsigned int is equivalent to uint32_t on your platform, you can easily generate 64 cryptographically secure random bits by using boost::random_device:

boost::random_device rd;
std::uint64_t value = rd();
value = (value << 32) | rd();

This is fairly secure, since the implementations for both linux and windows use the operating system's own cryptographically secure randomness sources.

Generating cryptographically secure values with arbitrary distributions

While the previous works well enough, you may wish for a more flexible solution. This is easy to do by realizing that you can actually use the random distributions boost provides with random_device as well. A simple example would be to rewrite the previous solution like this:

boost::random_device rd;
boost::random::uniform_int_distribution<std::uint64_t> dis;
std::uint64_t value = dis(rd);

(While this can in theory also provide a more robust solution if the previous one does not actually contain a number in [0, 2**32), this is not a problem in practice.)

Binding distribution to generator

To improve usability you will often find usage of boost::bind to bind distribution and generator together. Since boost::bind copies its arguments, and the copy ctor is deleted for boost::random_device, you need to use a little trick:

boost::random_device rd;
boost::random::uniform_int_distribution<std::uint64_t> dis;
boost::function<std::uint64_t()> gen = boost::bind(dis, boost::ref(rd));
std::uint64_t value = gen();

Using engines for random number generation

Is there a recommended way of generating Random bytes and adding entropy in OpenSSL?

Yes. See the OpenSSL wiki on Random Numbers. It takes you through adding entropy for a seed, and extracting bytes for use in keying and other secret material.

Adding entropy for seeding is covered under Random Numbers and Seeds. Extracting bytes for use in keysing and other secret material is covered at Random Numbers and Generation.

Where can I get other Engine implementations, and how can I swap them in?

OpenSSL comes with a few engines related to random numbers. The default is a software based PRNG engine, md_rand. You can find its source code at <openssl src>/crypto/rand/md_rand.c. Another is Intel's RDRAND engine. You can find the source at <openssl src>/crypto/engine/eng_rdrand.c.

You can also use hardware based RNGs if you have the hardware. You can even write your own engine that provides a SHA-512 HMAC. Or even one that combines (XORs) an SHA-512 HMAC with with RDRAND. The Mersenne Twister is popular, and you could even write an engine for it, too.

Here's how you swap in an engine to use for random numbers. Its taken from the OpenSSL wiki, and it swaps-in the Intel RDRAND engine:

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

... I am trying to use the RAND_bytes API of OpenSSL ...

You never do anything other than use RAND_bytes, RAND_add and friends as normal. How you use RAND_bytes, RAND_add and friends never changes.

The Mersenne Twister is popular, and you could even write an engine for it, too...

If you do this, then you might consider posting the source code for others to use. I would suggest creating a page on OpenSSL's wiki, explain the Mersenne Twister engine, explain how to use it, and provide a patch for it.

The other choice is to submit it to the RT system (the bug tracker) as a feature/enhancement. But its been my observation that most things wither and die once they enter RT.

Initialization Vector Creation

Use a cryptography PRNG, just like you do for the key.

On windows use CryptGenRandom/RtlGenRandom and on Linux/Unix use /dev/urandom. Those get seeded by the OS, so you don't need to take care of it.

If you really want to create your own PRNG, look into Fortuna. Don't use a Mersenne twister.

Why do I keep getting the same first digit while I've seeded a generator with time?

You are setting initial states into your random-generator that are very similar. Depending on the quality of the generator, this may or may not result in similar outputs. To illustrate, I've augmented your sample to (a) print only the first sequence, since that is what we care about, and (b) print several results of various resolution:

int main(){
    auto t = time(0);
    cout << "time: " << t << endl;
    default_random_engine e(t);
    default_random_engine e2(t);
    default_random_engine e3(t);
    default_random_engine e4(t);
    uniform_int_distribution<int> uniform_dist(0, 9);
    uniform_int_distribution<int> uniform_dist2(0,999);
    uniform_int_distribution<int> uniform_dist3(0,99999);
    uniform_int_distribution<int> uniform_dist4(0,9999999);
    cout << "sequence: ";
    cout << uniform_dist(e) << " " << uniform_dist2(e2) << " " << uniform_dist3(e3) << " " << uniform_dist4(e4);
    cout << endl;
    return 0;
}

When run:

$ ./a.out
time: 1541162210
sequence: 7 704 70457 7070079
$ ./a.out
time: 1541162211
sequence: 7 704 70457 7070157
$ ./a.out
time: 1541162212
sequence: 7 704 70458 7070236
$ ./a.out
time: 1541162213
sequence: 7 704 70459 7070315
$ ./a.out
time: 1541162214
sequence: 7 704 70460 7070393
$ ./a.out
time: 1541162215
sequence: 7 704 70461 7070472
$ ./a.out
time: 1541162216
sequence: 7 704 70461 7070550
$ ./a.out
time: 1541162217
sequence: 7 704 70462 7070629
$ ./a.out
time: 1541162218
sequence: 7 704 70463 7070707
$ ./a.out
time: 1541162219
sequence: 7 704 70464 7070786

While I do not know exactly what this random-generator implementation is doing, you can easily see that it is performing a very simple transformation of your seed into state, and state into output values. As other comments have suggested, there are better random generators and better seeds. Also note that the quality varies between implementations; Visual Studio 2017 does not exhibit this behavior.

Uniform random number generator in c++

You have to initialize the engine with a seed, otherwise the default seed is going to be used:

eng.seed(static_cast<unsigned int >(time(NULL)));

However, true randomness is something you cannot achieve on a deterministic machine without additional input. Every pseudo-random number generator is periodical in some way, which is something you wouldn't expect from a non-deterministic number. For example std::mt19937 has a period of 2¹⁹⁹³⁷-1 iterations. True randomness is hard to achieve, as you would have to monitor something that doesn't seem deterministic (user input, atmospheric noise). See Jerry's and Handprint's answer.

If you don't want a time based seed you can use std::random_device as seen in emsr's answer. You could even use std::random_device as generator, which is the closest you'll get to true randomness with standard library methods only.

The Implementation of Random_Device in VS2010