Random Seeding¶

The de facto method of seeding a Random Number Engine in C++ is broken:

std::mt19937 rng{std::random_device{}()};

This initialization one-liner is unfortunately perpetuated by well-meaning sites like cppreference and Stack Exchange. Of course, these are better than the plethora of results for “C++ random number” that make the horrifying suggestion to use rand() seeded with srand((int) time(0)).

So what is the problem with this one-liner? The simple issue is std::mt19937 has an internal state of \(19937\) bits, but you are only initializing it with \(32\) bits of randomness. Internally, std::mersenne_twister_engine uses the provided number as a seed for a std::linear_congruential_engine, which is used in turn to synthesize a more random-looking seed (thus, making it work fine for small use cases). The similarity of sequences will only manifest itself if you initialize multiple std::mt19937 instances and compare their output.

Note

std::mt19937::state_size is 624, leading to \(19968\) bits of stored state. The difference of \(31\) bits is unused (horrible waste of memory!).

This article presents three different ways to create a PRNG with a state filled entirely with randomness from a std::random_device (or potentially any other Uniform Random Bit Generator). Ultimately, I just want a one-liner like this that just does the right thing:

auto rng = random_seeded<std::mt19937>();

Using `std::seed_seq`¶

Luckily, C++ Random Number Engines have a nice way to initialize their entire state with randomness. Every pseudo-random number engine provides two constructors: one that accepts a result_type and one that accepts a Seed Sequence (example). The seed sequence is what you should be using when you Really Care^TM.

Unfortunately, while std::seed_seq exists, it is not obvious how one should use it correctly. Furthermore, using it to seed an actual PRNG is awkward and inconvenient.

To use std::seed_seq properly, you must fill it with the proper amount of bits for a random number engine. The obvious choice is to use std::random_device to do this for us. Unfortunately, the question of “required number of bits” is only answered by TRandomNumberEngine::state_size * sizeof(typename TRandomNumberEngine::result_type) * 8, while you can only express these bits to std::seed_seq in std::uint32_t``s. Annoyingly, ``std::seed_seq::result_type is either useless or misleading, as it must be std::uint_least32_t, which might be over 32 bits, but is required to only copy the lower 32 bits.

#include <algorithm>
#include <array>
#include <random>

template <typename TRandomNumberEngine>
TRandomNumberEngine random_seeded()
{
    using engine_result_type = typename TRandomNumberEngine::result_type;
    using result_type = std::uint32_t;
    constexpr auto source_count = TRandomNumberEngine::state_size * sizeof(engine_result_type) / sizeof(result_type);

    std::array<result_type, source_count> source;
    std::random_device rng;
    std::generate(source.begin(), source.end(), [&rng] { return rng(); });

    std::seed_seq seeder(source.begin(), source.end());
    return TRandomNumberEngine(seeder);
}

This works, but it is not the greatest thing in the world. The single biggest problem with this mechanism is the copying from source on the stack to seeder on the heap. Internally, std::seed_seq implementations use an std::vector<std::seed_seq::result_type> to store numbers.

Random Seed Sequence¶

In an ideal world, we could just spit out random values directly into the engine on construction. Luckily enough, someone thought about this. std::seed_seq is merely an implementation of the Standard Library concept of a Seed Sequence.

With the vague hope that this definition changes in future versions of the C++ Standard, here are the requirements of a Seed Sequence.

Expression	Type	Description	Problems?
`S::result_type`	`T`	Member type must be an unsigned integer of at least 32 bits.
`S()`		Create a seed sequence with the same default values as other objects of type `S`.	See 1
`S(ib, ie)`		Create a seed sequence based on the supplied input bits by `[ib, ie)`.	See 1
`S(il)`		The same as `S(il.begin(), il.end())`.	See 1
`s.generate(rb, re)`	`void`	Fill `[rb, re)` with 32-bit quantities depending on the initial supplied values and potential previous calls to generate. If `rb == re`, it does nothing.	See 3
`s.size()`	`size_t`	The amount of 32-bit integers copied by `param`.	See 2
`s.param(ob)`	`void`	Copies 32-bit values to `ob` that would reproduce the current state of the object if passed to a constructor of `S`.	See 2

The goal is to have a truly-random seed sequence, so all of the constructors that set state cannot be implemented.
For the same reasons as 1, the ability to save and restore state cannot be implemented.
The method of extracting randomness from our seed sequence allows for any arbitrary Random Access Iterators to be supplied. Curiously, the iterators’ value_type is not restricted to result_type, which might make you wonder why result_type is a member type at all. Most importantly, they do not have to be Contiguous Iterators, which means it is not safe to assume &rb[0] + 1 == &rb[1]. This prevents easy, efficient use of system RNGs like /dev/urandom or rdseed.

It seems to be impossible to write a class that generates a random seed sequence on the fly that still fulfills the contract of a Seed Sequence. Luckily, since concepts weren’t around when this library was written, we do not actually have to fulfill the whole contract in order to use the class. So here we go:

#include <random>

class random_seed_seq
{
public:
    template <typename TRandomAccessIterator>
    void generate(TRandomAccessIterator first, TRandomAccessIterator last)
    {
        std::random_device rng;
        for ( ; first != last; ++first)
            *first = rng();
    }
};

At the time of writing this article, this simple class works with every PRNG in libstdc++ and libc++. It is possible to write dummy implementations for the rest of the functions in the contract, but there is not an obvious option for how this should be done. We could throw an exception if someone attempted to call an unimplementable function, but that is just pushing the error back to runtime (usually seen as a Bad Thing^TM). Alternatively, we could do nothing and pretend like everything worked. While these options might seem ridiculous or horrifying, someone might be forced to choose if a future version of the standard gets overzealous with poorly-written concepts.

`getrandom`¶

Unfortunately, using std::random_device like random_seed_seq does can be a bit slow if the state requires a lot of numbers. If you are using a version of Linux at or beyond 3.17, you can pull from /dev/urandom via the getrandom system call.

class system_random_seed_seq
{
public:
    using result_type = std::uint32_t;

public:
    void generate(result_type* begin, result_type* end)
    {
        random_fill(reinterpret_cast<char*>(begin), reinterpret_cast<char*>(end));
    }
};

This relies on a function called random_fill to implement the actual random-generation functionality so we can hide some of the implementation details. Despite what the man page might imply, there is not actually a function called getrandom, so let’s write a simple wrapper around syscall:

#include <linux/random.h>
#include <sys/syscall.h>
#include <unistd.h>

static long getrandom(void* buf, std::size_t buf_len, unsigned int flags)
{
    return syscall(SYS_getrandom, buf, buf_len, 0);
}

Now it is easy to implement random_fill:

#include <cerrno>
#include <system_error>

void random_fill(char* begin, char* end)
{
    while (begin < end)
    {
        long bytes_read = getrandom(begin, end - begin, 0);
        if (bytes_read > 0)
        {
            begin += bytes_read;
            continue;
        }
        else if (errno == EINTR)
        {
            continue;
        }
        else
        {
            throw std::system_error(errno, std::system_category());
        }
    }
}

CPU Instructions: `rdrand`/`rdseed`¶

As of Intel’s Ivy Bridge core, there has been a special instruction called rdrand which pulls data from a hardware random number generator. When compiled with target("rdrnd") and cpuid shows rdrand support (that is not a typo – they are slightly inconsistent), the instruction can be used to generate high-quality random numbers.

Note

The hardware generator is theoretically a perfectly random source that pulls randomness from heat noise – a quantum level of unpredictability. It sounds totally cool from a security standpoint. That said, there are some serious and reasonable concerns around relying on a black box chip, given that the NSA has worked with chip manufacturers to insert back doors into security hardware.

According to Cryptography Research, “the most prudent approach is always to combine any other available entropy sources to avoid having a single point of failure.” The Linux kernel follows this philosophy with /dev/random and /dev/urandom by combining rdrand with various other sources of entropy, but that still might be enough if the RNG chip is attacked with the Linux kernel in mind. Taylor Hornby demonstrated a theoretical attack of this nature in Linux versions before 3.12.3 (which has been fixed).

If you’re still wearing your tin-foil hat, check out the paper “Stealthy Dopant-Level Hardware Trojans”.

The class cpu_random_seed_seq about the same as system_random_seed_seq:

class cpu_random_seed_seq
{
public:
    using result_type = std::uint32_t;

public:
    void generate(result_type* begin, result_type* end)
    {
        random_fill(reinterpret_cast<char*>(begin), reinterpret_cast<char*>(end));
    }
};

Here, random_fill actually implements calling the CPU instructions. For performance reasons, we want to use the 64-bit version of rdrand when we generate into quad-aligned memory, the 32-bit version when generating into dword-aligned, and so on. Luckily, this can easily be implemented at_each_aligned:

__attribute__((target("rdrnd")))
void random_fill(char* data_begin, char* data_end)
{
    at_each_aligned<8, 4, 2, 1>
    (
        data_begin, data_end,
        [] (char* p64) __attribute__((target("rdrnd")))
        {
            _rdrand64_step(reinterpret_cast<unsigned long long int*>(p64));
        },
        [] (char* p32) __attribute__((target("rdrnd")))
        {
            _rdrand32_step(reinterpret_cast<unsigned int*>(p32));
        },
        [] (char* p16) __attribute__((target("rdrnd")))
        {
            _rdrand16_step(reinterpret_cast<unsigned short*>(p16));
        },
        [] (char* p8) __attribute__((target("rdrnd")))
        {
            unsigned short x;
            _rdrand16_step(&x);
            *p8 = char(x);
        }
    );
}

Internally, libstdc++‘s implementation of random_device::operator() uses this same instruction (through glibc’s __x86_rdrand). However, this interface allows us to generate up to double the data with the same number of CPU instructions (keep in mind that getrandom is still going to be faster in almost all cases).

The End Result¶

No matter what option the implementation comes from, we can implement random_seeded quite easily:

template <typename TRandomNumberEngine>
TRandomNumberEngine random_seeded()
{
    // Prefer this version -- it is the safest and most secure RNG.
    system_random_seed_seq rss;
    return TRandomNumberEngine(rss);
}

This allows us to get a randomly-seeded Random Number Engine with:

auto rng = random_seeded<std::mt19937>();

Hooray!

Random Seeding¶

Using `std::seed_seq`¶

Random Seed Sequence¶

`getrandom`¶

CPU Instructions: `rdrand`/`rdseed`¶

The End Result¶

Table Of Contents

Previous topic

Next topic

Random Seeding¶

Using std::seed_seq¶

Random Seed Sequence¶

getrandom¶

CPU Instructions: rdrand/rdseed¶

The End Result¶

Using `std::seed_seq`¶

`getrandom`¶

CPU Instructions: `rdrand`/`rdseed`¶