Entropy Pool

% Remco Bloemen % 2015-08-26

Random number generation is an underestimate challenge in any cryptographic system. You need it for generating keys and nonces, and often the security of the entire system depends on it.

For example, Blockchain.info’s late 2014 security breach is caused by using non-random nonces. Even though the breach was fixed in two and a half hours, it still led to the bitcoins of hunderds of addresses being stolen. Similarly a lot of Mobile wallets got robbed and the Sony Playstation 3 root key got stolen because non-random nonces.

Whenever possible, it’s best to avoid using random numbers altogether. For example in the digital signature algorithm, instead of using a random nonce, you can use a hash of the message. This won’t loose you any security and has been promoted by RFC 6979. If Blockchain and Sony had implemented this recommendation, there would have never been a breach.

Overall design

Entropy sources

Some program accessible sources of entropy are:

So we have a lot of sources that can provide us with a tiny bit of security. We would like to combine those into one source that can provide us with a lot of security. We don’t want to design a system like a chain, where if one link breaks, the load falls. We want to design the system like braided rope, all strands need to break before the load is lost.

Luckily, for random number generators we can create the braided rope.

Pseudo random number generators

void seed(const Bytes bytes); Bytes extract(uint length);

Entropy accumulator

How to Eat Your Entropy and Have it Too Optimal Recovery Strategies for Compromised RNGs http://eprint.iacr.org/2014/167.pdf Random number generators (RNGs) play a crucial role in many cryptographic schemes and protocols, but their security proof usually assumes that their internal state is initialized with truly random seeds and remains secret at all times. However, in many practical situations these are unrealistic assumptions: …

Remco Bloemen
Math & Engineering