Randomness

1 Initialize the buffer.

All variables, classes, and functions related to our accumulation of randomness are in a namespace myRandomSeed

On startup, we create a buffer of fifty five uint64_t values, which once it is sufficiently unpredictable to an attacker, will be hashed into the seed value for randombytes_buf_deterministic. Fifty five values, with a lag of twenty four, are the parameters of the additive generator recommended by Knuth, The Art of Computer Programming volume two, section 3.2.2, which is cited by generating numbers unpredictable to an attacker.

At startup we fill the buffer with OS provided randomness from randombytes_buf. If OS provided randomness is good, subsequent measures are merely gilding the lily, but we will gild the lily just in case.

To initialize the stir operation, we set two pointers, I1 will point to start of the buffer, I2 will point to the start of buffer+24

uint64_t CountOfStirEvents{0};

2 MyStir(uint64_t r)

We use this during initialization to get some randomness independent of that provided by the OS

I1 and I2 are preincremented, then if points beyond the end of the buffer reset to the start of the buffer.

void MyStir(uint64_t r){
  if(++I1==end)I1=begin;
  if(++I2==end)I2=begin;
  *I1 = *I1 + *I2 + r*11400714819323199563ull;
  // 11400714819323199563 is a prime number close to (2**64)*golden_ratio, where golden_ratio = (sqrt(5) - 1)/2.
  // to smear the unpredictable bits, which tend to be the low order bits, over all orders of bits.
  CountOfStirEvents++;
  return;
}

After the buffer has been hashed into the seed and freed, MyStir is still called on the same events, and then merely adds r*11400714819323199563ull into the seed, considering the seed as a 256 bit little endian integer.

3 finding initial randomness

At program startup we call MyStir with the high resolution timer (cast from chrono to an unsigned integer) as argument immediately after initializing the buffer, and thereafter after each disk or network operation, after each access to the configuration file, first with the high resolution timer, then with whatever was read from the configuration file, after each wxWidgets construction likely to take a while, on mouse events first with the high resolution time, then with the mouse data, and with the on_idle.

4 Our randomness function

When we want a random value, have a static_assert that

static_assert(randombytes_SEEDBYTES==0x20);

We check that CountOfStirEvents is sufficient, one hundred twenty eight stir events being deemed sufficient to accumulate well over one hundred twenty eight bits unguessable to an attacker without access to the machine, per the estimates in the linked document. If it is sufficient, we proceed. If it is not, we pop up a window asking the user to wave the mouse around to generate sufficient randomness. The window goes away once we have sufficient randomness, or if the user clicks the skip button on the window (he may not necessarily be all that worried about sufficient randomness).

Either way, we then hash the buffer with crypto_generichash, which is BLAKE2b, with a thirty two byte output, and free it, and use the 256 bit, 32 byte, hash as seed for our own randombytes_buf function based on randombytes_buf_deterministic(). The stirring hooks on the mouse, on_idle, and on disk and network operations are left in place, continuing to accumulate randomness into the seed as uncorrelated events arrive.

Our function void myRandomSeed::randombytes_buf(void * const buf, const size_t size); uses our thirty-two byte seed to fill a buffer using libsodium’s void randombytes_buf_deterministic(void * const buf, const size_t size, const unsigned char seed[0x20]); and then adds the high resolution timer into the seed, considering the seed as a 256 bit little endian integer, so that successive calls use fresh and partially unguessable seeds.

5 How much entropy does this really buy?

The OS provided randomness with which the buffer is initialized is the primary defense. If randombytes_buf is sound, all of the above is, as said, gilding the lily.

Against an attacker without access to the machine, each stir event contributes several bits of unguessability, in the low order bits of the high resolution timer sampled at uncorrelated events, per the argument of Kent Borg and the estimate of jrzx in the linked document.

Against a local attacker, or an offline attacker who knows the approximate time at which we generated our keys, the timer bits are worth much less, tens of bits perhaps, not hundreds, as Barney Wolff pointed out in the linked document. Therefore we do not claim thirty two bytes of entropy; we claim a thirty two byte seed with the OS randomness on the bottom, and a healthy margin of unguessability piled on top of it.

 reaction.la gpg key 154588427F2709CD9D7146B01C99BB982002C39F
This work is licensed under the Creative Commons Attribution 4.0 International License.