Extracting Randomness from Mouse Acceleration
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. 655
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. 655