3
$\begingroup$

I'm working on trying to make an "entropy pool" that will be fed as input into an RNG (as in, ex, Fortuna). In order to do so, I need to take various collected data and extract as much entropy as possible to turn it into unpredictable bits. I've read many papers about extracting randomness, but I haven't understood how to apply it to real-world data sources.

For example, as one entropy source, I'd like to use the position of the mouse cursor. After some simple experimentation, it seems like using the acceleration of the cursor (resulting in two streams of X acceleration and Y acceleration) is the best representation to use in that it reduces the sample range significantly. Running several min-entropy estimators on the acceleration data (separately for X and Y axis data), I get estimates of at worst 0.75 bits/sample of entropy (ignoring that the two streams are correlated). Beyond that, I'm not sure how to apply any published randomness extractor to this data.

Part of my problem stems from the fact that most entropy extractors talk about entropy rate, which I'm not sure how to calculate in this case. My samples are 8 bits each (signed byte), so that could make the entropy rate 0.75/8 ~= 0.09, which is far too low for most extractors. Another problem is that I have two correlated streams, and I can't remember any extractors that deal with that kind of input.

Any guidance or references on how to extract entropy from this data using any published randomness extractor would be greatly appreciated. I'm very interested in using a "real" randomness extractor and not the common "just hash it" approach.

I have a custom design that I can detail if desired. It essentially computes symbol statistics from the entire test capture (5 million samples) and uses range encoding to encode each symbol using those statistics. It results in about 1.5 bits/sample of output for each stream, and I'm not sure how well founded the idea is.

Edit: One of my end goals is to have a very large state RNG, suitable for being able to shuffle 200 card decks into every possible combination. 200! is ~1246 bits, so (for ex) using a typical PRNG-oriented implementation of AES-256-CTR would not suffice because it has too small a state to store that much entropy.

Also, as for using cryptographic hash functions, some of the early papers on extractors indicate that almost all functions are good extractors for high-entropy data, but I haven't seen any information about using them to reduce low-entropy data to shorter higher-entropy data (keep the entropy level, but reduce the total number of bits). If this is a mathematically valid use, I'd really like to see papers about it.

Improve this question
$\endgroup$
4
  • $\begingroup$ Have you looked at how the Linux kernel feeds its randomness pool? $\endgroup$
    – adrianN
    Dec 20, 2016 at 15:43
  • $\begingroup$ It seems to primarily use timing values when various events happen, and mixes the data in directly to a pool using a twisted Generalized Feedback Shift register. Then, to get entropy from a pool, it uses the hash of the entire pool. In other words, they don't seem to use any kind of randomness extractor besides simple hashing. $\endgroup$
    – Extrarius
    Dec 20, 2016 at 16:29
  • $\begingroup$ Mouse acceleration doesn't sound very random to me: I'd expect acceleration to start at zero, increase more or less smoothly to some maximum value, then decrease more or less smoothly to zero. That means there's pretty high correlation over time. $\endgroup$
    – David Richerby
    Dec 21, 2016 at 16:56
  • $\begingroup$ @David Richerby: Exactly. Not very random, meaning low entropy, which is why I'd want something like an extractor. $\endgroup$
    – Extrarius
    Dec 22, 2016 at 6:55

1 Answer 1

Reset to default
3
$\begingroup$

Start by reading How to extract randomness from a file?.

At a broad level, it seems like you understand pretty well the techniques.

To extract randomness in practice, I recommend you use a cryptographic hash, and use techniques from the cryptographic literature for cryptographic building pseudorandom generators.

You mention "extractors". I know there's some cool theory surrounding them, but I don't recommend you use extractors. They are beautiful but not practical. Cryptographic hash functions are superior in practice.

You talked about estimating the amount of entropy in the data. Unfortunately entropy estimation is an inexact science. It's also easy to over-estimate the amount of entropy (e.g., if there are non-trivial correlations in the data that you didn't think to check for). So, a typical procedure that cryptographers often use is to make some estimate of the entropy rate (typically through a priori calculations), then divide by a factor of 4 or so to provide a safety margin -- and gather random values from many sources, and feed them all into the pool. The hope is that even if one source provides low-entropy data, or even if one of the entropy estimates is too optimistic, maybe some other source will have enough entropy in it to make up for the problem.

Overall, I recommend you spend some quality time in the cryptographic literature reading about the techniques that have been developed there. Cryptographers have spent a lot of time worrying and thinking about this, because cryptography relies upon high-quality random numbers. And, rather than re-inventing the wheel yourself, it's probably better to re-use some existing well-tested cryptographic method.

Here are a few pointers to get you started:

You can look around Crypto.SE and the resources mentioned there, and you'll probably be able to pick up a bunch about this topic. Have fun!

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Thank you for the links, I'm looking over them now. I understand entropy estimation is only estimation, and even with a large suite of estimation algorithms, it only provides a ceiling. Based on some of the early papers I've read, "random functions" are only good for extracting from high-entropy sources, and I haven't seen anything about them being good 'condensors' to maintain entropy but reduce size for low-entropy inputs. $\endgroup$
    – Extrarius
    Dec 21, 2016 at 16:28
  • 1
    $\begingroup$ @Extrarius, well, I'm not sure which papers you read so it's hard for me to respond to that in a specific way. Be careful what papers you rely upon; as I said, there's a gap between the theory community (e.g., extractors) and what's a good idea in practice. Cryptographic hash functions are fine for reducing the size of low-entropy inputs. But really, you should never be using low-entropy inputs; if the total entropy of the entire pool is small, it doesn't matter what function you use -- the output will be bad. $\endgroup$
    – D.W. ♦
    Dec 21, 2016 at 16:48
  • 1
    $\begingroup$ I understand, but if you read the cryptographic literature, you will learn how to deal with that. The wrong way to generate pseudorandom output once a second (say): each second, take the entropy inputs gathered over the past second, and apply some function (hash function, extractor). The right way: build a pool that contains all the entropy inputs ever gathered, and take the hash of that. Read about the Linux /dev/urandom pool to see how we avoid that pool growing indefinitely (e.g., periodically replace the pool with a hash of its data, then append to that) $\endgroup$
    – D.W. ♦
    Dec 21, 2016 at 17:25
  • 1
    $\begingroup$ That technique ensures that, once a little time has passed, the pool will in aggregate have high-entropy, and once it reaches that point, it'll never go back to a low-entropy state. You really want to do everything you can to avoid ever being in a state where you're generating pseudorandom output from a low-entropy input. In other words: there are lots of tricky bits here that have been developed in the cryptographic literature. If you try to roll your own solution, you'll probably overlook some of them and end up with an inferior solution. $\endgroup$
    – D.W. ♦
    Dec 21, 2016 at 17:26
  • 1
    $\begingroup$ I plan on following the model of Fortuna, with multiple pools used at different intervals, so some pools get a long time to accumulate entropy, while others more quickly insert whatever entropy is available. $\endgroup$
    – Extrarius
    Dec 21, 2016 at 17:48

Your Answer

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

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