5

I would like to do something like this:

boost::random_device rd;
boost::random::mt19937_64 gen(rd());
boost::random::uniform_int_distribution<unsigned long long> dis;
uint64_t value = dis(gen);

But I've read that a mersenne twister is not cryptographically secure. However, I've also read that a random_device could be, if its pulling data from /dev/urandom which is likely on a linux platform (my main platform). So if the random_device is non-deterministically random and its used to seed the mersenne twister (as shown above), doesn't that also make the mersenne twister cryptographically secure (even though by itself, it isn't)?

I'm a bit of a novice in this arena so any advice is appreciated.

So, how can I generate a cryptographically secure 64 bit number that can be stored in a uint64_t?

Thanks,

Ben.

Ben J
  • 1,367
  • 2
  • 15
  • 33
  • Disclaimer - not an expert. Mersenne twister can never be cryptographically secure, regardless of how you seed it, because an attacker can easily determine the next outcome once they learn its internal state. To generate your 64-bit number, you could call `random_device` twice (assuming 32-bit `int`), and append the results. Also, you may not want to use the default `/dev/urandom` source, but pass the argument `"/dev/random"` to the `random_device` constructor. Unlike the former, the latter will block when there are no more random bits available in the entropy pool. – Praetorian Apr 29 '14 at 18:47
  • Thanks for your comment Paetorian -- seems similar to gha.st's answer! Cheers. – Ben J Apr 29 '14 at 20:26
  • @Praetorian I recommend `/dev/urandom` over `/dev/random`. Once sufficiently seeded (with say 200 bits of entropy) a PRNG cannot run out of entropy, no matter how much you read. So `/dev/random` does lots of unnecessary blocking. The only concern with `/dev/urandom` is that it might not be *sufficiently seeded yet*, which is mostly relevant early in the boot process on embedded devices. – CodesInChaos May 02 '14 at 09:30

2 Answers2

8

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();
Community
  • 1
  • 1
danielschemmel
  • 10,885
  • 1
  • 36
  • 58
  • I've learned that MSVC's implementation of `std::random_device` uses a PRNG ([and this is allowed by the standard](http://en.cppreference.com/w/cpp/numeric/random/random_device)). So by all means, stick to boost for `random_device`, I suppose. – sehe Apr 29 '14 at 18:47
  • @sehe: See [this](http://stackoverflow.com/questions/9549357/the-implementation-of-random-device-in-vs2010). – kec Apr 29 '14 at 18:50
  • @user3521733 Thanks. That just leaves the in-principle point of _check your implementation_ before relying on it. – sehe Apr 29 '14 at 18:51
  • 1
    @sehe Your comment did make me go digging around MSDN, and it seems the MSVC implementation [ignores the constructor argument](http://msdn.microsoft.com/en-us/library/bb982210.aspx). So you cannot change the entropy source even if you wanted to. – Praetorian Apr 29 '14 at 18:54
  • Thanks gha.st. I will use your latter example I think :-) – Ben J Apr 29 '14 at 20:27
-1

Using the random device just for seeding isn't really cryptographically secure. The problem is then reduced to figuring out the initial seed, which is a greatly reduced problem. Instead, directly use the random device.

val = dis(rd);

For greater security, initialize the random device with /dev/random rather than /dev/urandom. /dev/random will block if there isn't enough "entropy", until some random things have happened. However, it may be much, much slower.

BTW, assuming that you have a high-quality C++11 implementation that doesn't return bogus values for the entropy function, using C++11 might be a better idea if you are trying to remove dependencies.

EDIT: Apparently there is some debate about whether or not /dev/random is any better than /dev/urandom. I refer you to this.

Community
  • 1
  • 1
kec
  • 2,099
  • 11
  • 17
  • 3
    What. [`urandom` is more appropriate for secure random than `random`, period](http://security.stackexchange.com/a/3939/22242). And [it appears better to use boost than c++11](http://stackoverflow.com/questions/9549357/the-implementation-of-random-device-in-vs2010) at least when the latter has only PRNG – sehe Apr 29 '14 at 21:01
  • I would argue that VS2010's C++11 implementation is broken. But I'll edit the answer to make clear the trade-off. – kec Apr 29 '14 at 21:32