Re: [Cfrg] (no subject) (Randomness recommendations)

["John Kelsey" <john.kelsey at nist.gov>]

...
> As has been said before, a simple measure of a bit stream calculating
> Shannon entropy is not good.  Min-entropy is difficult to compute for a
> bit stream.  (What block size do you use?  And if you pick one large
> enough to find many problems that might occur, it requires too much
> space and time.)

I don't see why it's any harder to compute than Shannon entropy.  Entropy
as we're discussing is defined for a probability distribution.  For
Shannon entropy, you need to know the probabilities of all the symbols to
compute it; for Min-entropy, you need only know the highest probability.

Now, you *do* need to take into account any correlation between outputs,
but that's true for both Shannon entropy and min-entropy.  (The usual
estimate of bits of Shannon entropy per letter in English text is based on
conditional probabilities given previous letters seen, not just on the
letter frequencies!)

> And the purpose of min-entropy does not apply to a bit
> stream that is going to be "mixed" or "accumulated".

What do you mean?

Look, what we really want to know is "how hard is it for the attacker to
attack our PRNG by guessing our seed?"  So, if we know the most probable
value for the seed, that gives us a nice worst-case estimate of how hard
it is: if the most likely seed has probability 2^{-100}, then we know that
there's no way for an attacker to try N guesses and have better than a
probability of N*2^{-100} of success.

Suppose you send in a sequence of 256-bit blocks to be accumulated, where
each block has a maximum probability, conditioned on all previous blocks,
of P[i].  After we send in 100 such blocks, what's the maximum probability
of the whole input sequence?  p[0]*p[1]*p[2]*...*p[99].  Since the
min-entropy of block i is ME[i] = -lg(p[i]), we can add those logs to
multiply the probabilities, so we get ME[whole sequence] =
ME[0]+ME[1]+...+ME[99].

Now, why is that important?  Because assuming the accumulator isn't losing
any entropy (it will start losing a lot, once the amount of entropy gets
close to the size of the memory of the accumulator), that tells us the
maximum probability of the accumulated state.

Let's make this concrete.  Suppose I have a ring oscillator source which
buffers 32 bits at a time.  Based on a lot of statistical analysis, I am
convinced that conditioned on all previous bits of output, the next 32-bit
block of output never has probability higher than 1/8=2^{-3}, so it has 3
bits of min-entropy.  Now, I need to accumulate enough to make a 128 bit
AES key for my PRNG.  So I know that I need to accumulate ceiling(128/3) =
43 samples.  When I've done that, I know that my sequence of samples has
maximum probability of less than 2^{-128}, meaning that an attacker who's
trying to attack my seed by guessing what samples I got from my ring
oscillator source is worse off than if he just tried to guess my AES key
from the start.

...
>    -- David Jacobson

--John Kelsey, NIST, September 2004

_______________________________________________
Cfrg mailing list
Cfrg at ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg