[Cryptography] The ultimate random source
frantz at pwpconsult.com
Fri Feb 21 18:38:23 EST 2014
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
>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
>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
www.pwpconsult.com |ibuted to Andrew Tanenbaum | Los Gatos,
More information about the cryptography