Meaning of entropy of a bitstring in NIST SP 800 - 90A

Question

From NIST SP 800 - 90A from January 2012 (see http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf), page 6:

For the purposes of this Recommendation, an n-bit string is said to have full entropy if that bit string is estimated to contain at least $(1-\epsilon) n$ bits of entropy, where $0 <= \epsilon <= 2^{-64}$.

My understanding of entropy is that entropy is a property of the probability distribution of a source of bit strings, and not a property of a single bit string.

So what is NIST specifying here? Is there a way to estimate the entropy of the underlying source, given a bit string produced by that source? Maybe statistical tests, like Maurer's universal test? This could only be probabilistic since in principle, a true source of randomness can create any bit string...

Answer 1

By using the definition of $n$ bits of full entropy, NIST is abstracting away from the definition of a NRBG (or TRNG). They are basically trying to establish a minimum requirement for the quality of the random number generator, without going into the specifics on how this can be achieved. Basically this is NIST's way of saying: if we specify $n$ bits of full entropy, you'd better be darn sure that the entropy is there. Note that this definition is used for the seed or entropy source of the DRBG, rather than the output.

You are using this definition as a starting point for a discussion on how this can be achieved, so your thoughts take you in the exact opposite direction.

How the entropy can be gathered is specified in "8.6.5 Source of Entropy Input" in the document. That section in turn references the NIST SP 800-90B and -90C specifications.

Answer 2

"Entropy" is more accurately defined, in cryptography, as "that which the attacker does not know". For instance, suppose that every day you take all rates at the closure of the New York stock exchange, and hash them with SHA-256. The resulting value is very unpredictable (otherwise you could become very rich), so, from a "physics" point of view, there is a lot of entropy here. However, once the rates are published, everybody knows them: thus, from a cryptographic point of view, the entropy is nil.

To estimate the entropy, you have to analyze the process that generates the purportedly random value, and imagine an attacker trying to guess that value: the attacker has access to a validation box that returns "true" if the attacker found exactly the value, and "false" otherwise. You may say that the process yields "$n$ bits of entropy" if, on average, the attacker must invoke the validation box $2^{n-1}$ times before hitting the right value.

The important point here is that the estimate can come only from an analysis of the generation process. It cannot be tested with statistics, because statistics do not capture the level of knowledge of the attacker.