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

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...

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.

• Okay, so they are actually referring to the quality (entropy) of the underlying source of randomness. That makes sense. – maya Jun 14 '15 at 15:12

"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.

• I wouldn't say that "statistics do not capture the level of knowledge of the attacker". If a RBG is biased, for instance, the attacker can develop an optimized guessing strategy. – maya Jun 14 '15 at 15:14
• What I mean is that while statistics can detect things that attackers also know, attackers may know things that statistics do not detect. E.g. for a purportedly "strong" PRNG, if a statistical test detects a bias, then the PRNG is weak; but if the test detects nothing, then one must not conclude that the PRNG is strong. In practice, even bad PRNG are "perfect" from a statistical point of view. – Thomas Pornin Jun 14 '15 at 15:18
• That's interesting. So you meant that for a RBG, unpredictability is stronger than passing all statistical tests. Do you know a reference for this (a published paper e.g.)? – maya Jun 14 '15 at 15:32
• If passing tests was enough, competitions like eSTREAM would be meaningless. Anyone can run some statistical tests on a PRNG; but it takes years and many cryptographers to assess the actual security. – Thomas Pornin Jun 14 '15 at 15:44
• I wonder if this is just because in practice, statistical tests are hard to conduct, up to a certain level. I just searched the Handbook of Applied Cryptography, and in Chapter 5 it says 5.7 Fact (universality of the next-bit test) A pseudorandom bit generator passes the next-bit test [unpredictability] if and only if it passes all polynomial-time statistical tests. So now I doubt that statistical tests are insufficient, probably they are just impractical...? – maya Jun 14 '15 at 16:00