1
$\begingroup$

I'm writing a tool for manually collecting entropy from sources like coins and dice, and I'm wondering how to best deal with the case where the desired number of bits of entropy is not representable with a whole number of inputs. For example, when collecting 256 bits of entropy with a D6; log6(2^256) = 99.034318652.

The number of bits being collected, and the base, are arbitrary. Power-of-two bases are special cased to work directly with bits, as well as offering Von Neumann skew correction. Non-power-of-two bases are collected with a big integer: aggregate = aggregate * base + input where input is a value inclusively from 0 to base-1.

The simple solution which springs to mind is rounding (ceil, floor or true rounding) the number of inputs, but I'm not sure which strategy would be best, or whether there is some better option to minimize at least the predictability of biased bits in the result (my instinct is 'doing something with a CHF', but I've no idea what).

Cheers!

Improve this question
$\endgroup$
4
  • $\begingroup$ Are you correct at the entropy of singe dice? math.stackexchange.com/q/2916887/338051 and datasciencecentral.com/entropy-of-rolling-dice $\endgroup$
    – kelalaka
    Commented Sep 11, 2023 at 19:34
  • $\begingroup$ Hi Isaac, and welcome. I don't quite get what you're asking. Why not simply round up the inputs to the next whole number? What have "bases" to do with anything please? What's the purpose of bringing up von Neumann? Plus von Neumann is unrelated to any base. $\endgroup$
    – Paul Uszak
    Commented Sep 11, 2023 at 21:34
  • $\begingroup$ @PaulUszak sorry if I wasn't clear; I refer to 'bases' as the problem of building a large random number from coinflips/dice rolls, to my mind, is just building a base-X number with N digits where X is the number of possible values from each round, and N is the number of rounds. Rounding the number of rounds up does seem like the best option for a simple implementation, but given the output is a fixed size (Y number of bits) selected by the user, you get a predictable bias in your output: X^N % 2^Y values occur once more in the possible output than the other 2^Y - (X^N % 2^Y) values. $\endgroup$
    – Isaac
    Commented Sep 12, 2023 at 10:52
  • $\begingroup$ The question is basically: how might I do better than that? Using a CHF as the existing answer suggests should I think at least reduce the predictability of the bias, and salting I think would improve things further, but maybe there's more which can be done. $\endgroup$
    – Isaac
    Commented Sep 12, 2023 at 10:58

1 Answer 1

Reset to default
0
$\begingroup$

my instinct is 'doing something with a CHF', but I've no idea what

Your instinct to use a cryptographic hash function is line with what I'd recommend.

Using SHA3 as a re-seedable PRNG for entropy collection is a modern approach with various benefits(0)(1)(2). I've written about considerations when initializing & extracting from a SHA3 object in this context before. However, my recommendation these days would be to use the SHAKE256 XOF from the SHA3 standard instead of SHA3-512 for improved convenience (& other technical reasons).

The simple solution which springs to mind is rounding (ceil, floor or true rounding) the number of inputs

If you're dealing with float representations of events, you don't want to round them. You'd be cutting off the least significant bits, which is the section of a float where the most variation can typically be found. If you don't have to deal with float representations, then I'd recommend you don't — they can be imprecise & cause information loss.

Aside from that, finding a representation for the random events is mostly a consideration of efficiency, since the hashing object can be relied on to produce uniform outputs. For instance, a coin flip can optimally be represented by a single bit. A single D6 event can be represented in 3 bits. If you collect the events as a concatenation of their bit-wise representations, then you can efficiently feed those bits/bytes into a SHAKE256 object without extraneous conversions.

NIST SP 800-90 parts (A)(B)(C) may also contain useful recommendations for you.

Improve this answer
$\endgroup$
2
  • $\begingroup$ "since the hashing object can be relied on to produce uniform outputs." is incorrect. H(D6) is not the best RNG... $\endgroup$
    – Paul Uszak
    Commented Sep 13, 2023 at 4:08
  • $\begingroup$ Unbroken CHFs produce uniformly distributed pseudo-random bits. If you can make H a SHA3 object whose internal state is persistent, like entropy_pool = H(initial_entropy), then every time entropy_pool.update(pad_to_blocksize(random_event)) is run, the entropy is efficiently mixed into the internal state. entropy_pool.digest(output_size) can then be used as a uniform output producing RNG with an included 200-byte entropy pool. The biggest problems with this method are incorporating enough initial entropy, & making sure unique outputs are handed out across all concurrent threads & processes. $\endgroup$
    – aiootp
    Commented Sep 13, 2023 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.