Subject: [Cfrg] Question about min-entropy

From: David Jacobson <[email-masked]>
Date: Thu, 17 Jun 2010 10:21:22 -0700

NIST advocates min-entropy as the measure of security of random bit 
generators.

Assume a block-oriented random bit generator.  The usual definition of 
min-entropy is -lg2(Prob(most_probable_block)).

The motivation is a definition of security that is 
-lg2(Prob(attacker_can_succeed_on_first_try)).

However, for the attacker to succeed with that probability on the first 
try, the attacker must know the most probable value.

Let us assume that there is a hypothetical random bit generator that 
works like this, given 2 distinct _secret_ values A and B:

	R = 128 bit random value (real random)
	if R == A return B else return R.

Now by the usual definition of min-entropy, this generator's entropy is 
127 bits, since B is produced with probability 1/2^127.  However, this 
fact is of no use to the attacker since he doesn't know B.  There is 
another "rule" in cryptography that says that entropy is always relative 
to an observer (i.e. takes into account the knowledge of the observer). 
  So if the attacker doesn't know B, does this source have 128 bits of 
min-entropy?

Consider the RNG in FIPS 186-2 Appendix 3.  That is the one that 
basically works like this where R and S are 160-bit bit vectors and S is 
the internal state:

		R = SHA1(S);
		S += R;
		return R;

(Technically it is not SHA1, since FIPS 186.2 Appendix 3 says the 
compression function is applied to S padded with zeros, rather than the 
SHA1 padding, which would include the bit count.)

The input to SHA1 is just 160 bits, which is also size of the output. 
If we model SHA1 as a random oracle, then, considering just 160-bit 
inputs, there will be some collisions and some missed values.  By the 
usual definition, the collisions reduce the min-entropy.

I did a quick calculation that the reduction should be around 40 bits, 
i.e. the min-entropy of this generator is expected to be 120 bits rather 
than 160.  (Where "expected" is over the possible outcomes of a random 
oracle defining a 160 bit hash function.  Obviously real SHA1 has some 
exact number of collisions over a 160 bit input space; we just don't 
know what it is.)

   -- David Jacobson

---

From: Greg Rose <[email-masked]>
Date: Thu, 17 Jun 2010 13:59:01 -0700

> exact number of collisions over a 160 bit input space; we just don't

40 bits of reduction seems wayyy too much to me. The (Shannon) entropy  
only goes down by about half a bit. I studied this a bit in another  
context (I can tell you more some time, but not on this list) and the  
biggest collision I expected was of the order of 10. For SHA-1, the  
biggest bucket might be, say, 32, which is only 5 bits reduction in  
min-entropy. There's a well-known distribution for the behavior of  
stuff like this, but I don't have it to hand at the moment.

Greg.