On Dec 30, 2008, at 4:40 PM, Jon Callas wrote:
We don't have a formal definition of what we mean by random. My
definition is that it needs to be unguessable. If I have a random
number and the work factor for you to guess it is more or less its
randomness. It's a Shannonesque way of looking things, but not
precisely information-theoretic.
I don't think this quite captures the situation. It's easy to give a
formal definition of randomness; it's just not clear that such a thing
can ever be realized.
Here's one definition: A random bitstream generator is an "isolated"
source of an infinite stream of bits, numbered starting at zero, with
the property that a Turing machine, given as input anything about the
universe except the internal state of the "isolated" source, and bits
0 to n generated by the source, has no better than a 50% chance of
correctly guessing bit n+1. The difficulty is entirely in that quoted
"isolated". It's not so much that we can't define it as that given
any definition that captures the intended meaning, there are no known
systems that we can definitely say are "isolated" in that sense.
(Well, there's kind of an exception: Quantum mechanics tells us that
the outcome of certain experiments is "random", and Bell's Theorem
gives us some kind of notion of "isolation" by saying there are no
hidden variables - but this is very technically complex and doesn't
really say anything nearly so simple.)
A while back, I wrote to this list about some work toward a stronger
notion of "computable in principle", based on results in quantum
mechanics that limit the amount of computation - in the very basic
sense of bit flips - that can be done in a given volume of space-
time. The argument is that a computation that needs more than this
many bit flips can't reasonably be defined as possible "in principle"
just because we can describe what such a computation would look like,
if the universe permitted it! One might produce a notion of "strongly
computationally random" based on such a theory. Curiously, as I
remarked i that message, somewhere between 128 and 256 bits of key, a
brute force search transitions from "impractical for the forseeable
future" to "not computable in principle". So at least for brute force
attacks - we're actually at the limits already. Perhaps it might
actually be possible to construct such a "random against any
computation that's possible in principle" source.
A deterministic, but chaotic system that is sufficiently opaque gets
pretty close to random. Let's just suppose that the model they give
of photons bouncing in their laser is Newtonian. If there's enough
going on in there, we can't model it effectively and it can be
considered random because we can't know its outputs.
I don't like the notion of "opaqueness" in the context. That just
means we can't see any order that might be in there. There's a
classic experiment - I think Scientific American had pictures of this
maybe 10 years back - in which you take a pair of concentric
cylinders, fill the gap with a viscous fluid in which you draw a line
with dye parallel to the cylinders' common axis. Now slowly turn the
inner cylinder, dragging the dye along. This is a highly chaotic
process, and after a short time, you see a completely random-looking
dispersion of dye through the liquid. Present this to someone and any
likely test will say this is quite random. But ... if you slow turn
the inner cylinder backwards - "slowly", for both directions of turn,
depending on details of the system - the original line of dye
miraculously reappears.
That's why it's not enough to have chaos, not enough to have
opaqueness. The last thing you want to say is "this system is so
complicated that I can't model it, so my opponent can't model it
either, so it's random". To the contrary, you *want* a model that
tells you something about *why* this system is hard to predict!
However, on top of that, there's a problem that hardware people
(especially physicists) just don't get about useful randomness,
especially cryptographic random variables. Dylan said that to live
outside the law, you must be honest. A cryptographic random variable
has to look a certain way, it has to be honest. It's got to be
squeaky clean in many ways. A true random variable does not. A true
random variable can decide that it'll be evenly distributed today,
normal tomorrow, or perhaps Poisson -- the way we decide what
restaurant to go to. No, no, not Italian; I had Italian for lunch.
That's why we cryptographers always run things through a lot of
software. It's also why we want to see our hardware randomness, so
we can correct for the freedom of the physical process. Imagine a
die that is marked with a 1, four 4s, and a 5. This die is crap to
play craps with, but we can still feed an RNG with it. We just need
to know that it's not what it seems.
This simply says that *known* bias and randomness are completely
separate notions. I can always get rid of any *known* bias. Bias
that's unknown/unmodeled to me as the *user* of the system, on the
other hand, is very dangerous if an attacker might conceivably know
more about the bias than I do.
So yeah -- it's a glib confusion between chaotic and random, but
chaotic enough might be good enough. And the assumption that
hardware can just be used is bad. Hardware that helpfully whitens is
worse.
Jon
-- Jerry
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [email protected]
