[Cryptography] The ultimate random source

[Bill Frantz]

John, Thanks for emphasizing the need for careful analysis. Your 
points (originally at the end of your post) are quire valid:

>To summarize the main points:
>a) Cryptography requires attention to detail.
>b) There are a lot of things that can make the entropy less 
>than you guessed it was.
>c) The security of a RNG depends on having a reliable lower 
>bound on the entropy.  Guesses, estimates, and upper bounds do 
>not get
>the job done.
>d) Entropy is super-important, but it does not tell you everything
>you need to know.  It does not by itself solve all the world's
>problems.  Much depends on how the entropy is used.

I would quibble with point (c). If you have much more entropy 
than you need, the need for precision in estimating the lower 
bound is reduced. Having more than you need can make analysis 
tractable where analysis of a quantum source, such as radiation, 
Johnson noise -- pick your real source -- that only gave you 
just what you need is intractable because of the real-world 
engineering issues, such as hardware limits prevent achieving 
the precision you need.

I played with the M&Ns because the exact color and position is 
something that a camera has to do fairly well in order to pass 
muster as a camera. I don't have to worry about post-processing 
getting rid of all the noise, because any noise that comes thru 
is gravy and can only help a process that is already quite acceptable.

On 2/21/14 at 2:03 AM, jsd at av8n.com (John Denker) wrote:

>On Thu, 20 Feb 2014, Bill Frantz wrote:
>Now log(6^600) would not be a bad guess, and it serves as an 
>upper bound to this component of the entropy, but as a matter 
>of principle it's not the right thing.  It assumes that the 
>occupation of each
>site is independent, which surely isn't the case.  Look at it 
>this way:  The color of the final M&M is completely determined 
>by the state of the previous 599 M&Ms, so it contributes 
>exactly zero entropy.

It is more complex than that, and actually somewhat better. I 
used 18 3/8 ounces of M&Ms out of a 42 ounce bag. The color of 
the final M&M is not completely determined. (Computing this 
probability is where my statistics ran out.) However I have no 
reason to believe the M&Ms are evenly distributed between the 
colors, but the MK1A eyeball says it isn't too bad. (Actually 
counting them is above my pay scale.) Also we have the problem 
that we didn't really start with 42 ounces of M&Ms because some 
had been eaten. :-)


>A better estimate of the multiplicity is 600! / 100!^6 and upon
>taking the logarithm we find the entropy is approximately 1529 bits
>... about 22 bits less than the original guess.
>
>So this particularly obvious type of correlation makes only a 
>1.4% correction to the entropy.

Again, why we include a margin.


>On the third hand, if all you needed was 150 bits for seeding a
>CSPRNG, then 1529 is plenty, even if there are a few nonidealities

Seeding was my application. Also Phil was seeding. It is fairly 
obvious from the situation that whitening of the photo will be 
needed and seeding is a good way to whiten.


>On the fourth hand, there will be other types of correlation as 
>well, depending on as-yet unspecified details of the mixing 
>process.  You
>need to get a handle on this, to demonstrate that the fundamental
>front-end physics really is giving you some entropy.

If you want to do it right, put them in a lottery barrel and 
turn the crank for 5 minutes. :-) Even reaching into the bag 
with a hand and stirring them is "good enough" given the margin 
above the 128-512 bits needed for seeding.

I'm not sure there is any quantum physics based entropy here. 
What we do have is massive unguessability, unless an attacker 
can get a copy of the photo. At least we know what we have to 
guard, and how to check the full chain from M&Ms to CSPRNG for 
errors/failures etc. I have not seen how you check hardware 
sources, e.g the Intel one, for hardware failures.

Cheers - Bill


-----------------------------------------------------------------------
Bill Frantz        |Security, like correctness, is| Periwinkle
(408)356-8506      |not an add-on feature. - Attr-| 16345 
Englewood Ave
www.pwpconsult.com |ibuted to Andrew Tanenbaum    | Los Gatos, 
CA 95032