Subject: Re: [Cfrg] Question about min-entropy

From: David Wagner <[email-masked]>
Date: Thu, 17 Jun 2010 14:49:53 -0700 (PDT)

David Jacobson  wrote:
> 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.

The standard assumption is that the attacker knows the algorithms
you are using.  Kerckhoff's law, no security through obscurity, and
all that.

I would classify this as a PRNG with min-entropy 127 bits.  That said,
this is obviously a purely theoretical example, as there is no reason
to ever use something like you show.

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

Double-check your quick calculation; I think you've got an arithmetic
error in there somewhere.  I suspect you mean that the reduction in
min-entropy should be about lg 40 bits ~= 5.3 bits, not 40 bits.

Why?  Define the function f(S) = SHA1(S) + S mod 2^160, and fix a 160-bit
output y.  Consider the size of the set f^{-1}(y).  We can model this as
a random variable, where the probability that y has k preimages is about
1/e 1/k!  Now if k=40, we find that this probability is in the vicinity
of 1/2^160.  Therefore there is a reasonable chance that there exists
at least one output y with 40 or more preimages.  So the most-probable
value of f(S) has probability around 40/2^160, and thus the min-entropy
is around 160 - lg 40 ~= 154.7 bits.

---

From: DAVID JACOBSON <[email-masked]>
Date: Thu, 17 Jun 2010 16:24:03 -0700 (PDT)

Bottom line, the experts think that the basic definition is correct, and in the two cases (one completely artificial, one real) the probability of some value being higher than the mean probability really does reduce the min-entropy even if the attacker doesn't know what value has the higher probability.

As to the 40 bits, <begin removing egg from my face> you did about the same calculation as I did. I did it in log space because of numerical issues, and then accidentally thought the 40 was the log2 of the number of hits.  Thank you for the correction.

   --David Jacobson

--- On Thu, 6/17/10, David Wagner <[email-masked]> wrote:

> From: David Wagner <[email-masked]>
> Subject: Re: [Cfrg] Question about min-entropy
> To: [email-masked]
> Date: Thursday, June 17, 2010, 2:49 PM
> David Jacobson  wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>