How can the 'randomness' of a finite sample of binary keys from a finite key space be estimated?

Question

Given a set of bit sequences generated by an extractor, what would be a valid setting for estimating the randomness of these generated keys and what resolutions can be drawn for that extractor in general? The extractor will only generate bit sequences of fixed length such as 20 bits. Thus, all possible outcomes span only a finite key space.

Randomness

Though we would like to take the generated sequences as input to a cryptographic protocol (which has strong security properties even in the case of low-entropy input) our requirements for 'randomness' are somewhat less strict than in any well-defined notion of randomness since these typically focus on properties of infinite sequences. We are rather focusing on local randomness, i.e. the properties expressed by finite subsequences of random sequences of infinite length, and we would be even comfortable with results characterizing the peculiarities/bias/inter-bit-dependencies our extractor exhibits.

Currently, we approach this problem from two angles:

1. Empirical: We apply statistical tests on the set of generated sequences such as comparing the number of birthday collisions in the set of sequences with the estimated number of collisions for a typical sub sample of same size. We should point out here that we are aware of suites as dieharder, but don't think they are applicable here as we are only interested in the case of finite sequences.
2. Conceptual: We focus on corner-cases such as the case where our extractor produces the sequence consisting exclusively of ones and reason about the likelihood of this event.

Please Note: We are aware of suites such as dieharder. We also know about different other tests but consider them not applicable here as they do not focus specifically on sets of fixed-length sequences!

Though we think there is no other straight-forward way of solving this question, we would be grateful for any further insights or advices. Meaningful tests would also be much appreciated.

Update: While we know that concatenation of these bit sequences should be possible given they are random, we inherently lack enough data to do so - we depend on specific sensor data for our extractor to work and this is not easy to obtain in large amounts. We might be able to extract only about 1GB. Therefore, we are trying to bypass this lack of data by focusing more on the specific characteristic of our problem.

Also, the term key is probably not applicable here and should be taken as password instead as we do not ever use it to encrypt plain text. This might enable us to use it even if there are some known slight weaknesses in the extractor.

Answer 1

There are a few things to notice here:

1. any tested sequence is finite by definition, we cannot run tests on infinite sequences;
2. the size of the output is interesting, but if it is sufficiently random then the concatenation of the 20 bit sequences should also be random;
3. we cannot say for certain that a sequence is truly random, as many algorithms can generate output that seems random, but isn't - like a part of Pi from a particular offset;
4. peculiarities/bias/inter-bit-dependencies are not acceptable for key generation.

Great, that out of the way, let's advance to the answers:

1. the die-harder tests and any other tests seem fine for your particular problem;
2. the fact that you generate 20 bits at a time is not a particular issue, as long as it is random;
3. you should understand the properties of the random number generator and test to see if it is supposed to be random given those properties - basically you cannot and should not test for randomness without description of the RNG itself;
4. if you are afraid that your results are biased then you should at least whiten the generated stream and / or use it as input to a Deterministic Random Bit Generator (DRBG or CSPRNG).

As for (4), it seems you already assume that your protocol takes care of possible bias ( although you also talk about using the randomness as key data). In that case I would try and prove that the bias does not pose a problem. Furthermore, I'd make sure that then RNG cannot be used for other parts of the application that do require a cryptographically secure random number generator.

Finally, note that die-harder and similar suites work best on (very) large data sets. A few GB is kind of the minimum. I hope your generator is fast enough for that.

---

Caveat: I'm not a super-expert on this area and cannot answer about local properties your stream exhibits. I do think that the idea that the generic test suites won't pick up on this is flawed though. I'm pretty sure that suites like die harder will pick them up - but I'm not sure about the clarity of the returned results.

Answer 2

The answer is that you're simply over thinking the problem :-)

You do not have any special problem class, other than forgetting that randomness is a function of sample size. A bigger sample just means that it becomes easier to disprove randomness, accommodating more tests. A smaller sample just means fewer tests are applicable.

1GB is a whopping, huge amount of data. The perfect size for the NIST SP 800-22 test suite.

One of the definitions of randomness is having stability of frequencies. By definition, a binary sequence is stochastic whenever any suitably chosen subsequence of it has frequency stability. If you have a stationary ergodic entropy source, this requirement is automatically met. A simple matrix or hash based extractor can't really go wrong if your initial raw entropy measurement from the sensor is correct. But that's another question and another can of worms.

If your generator produces IID output, the above definition holds. Therefore it is straight forward. Concatenate and use NIST. This is how it's always done for TRNG validation.

---

A sequence of 20 ones occurs automatically every 128kB (and must by definition) in a long random stream. All randomness test suites know this.