On Dec 30, 2008, at 2:11 PM, Jerry Leichter wrote:
> 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.
And that is, pretty much, the point. A formal definition that is no
guidance to people trying to build things is mathematics as art. Not
that art is a bad thing -- I adore mathematics as art, and my time as
a mathematician was all in the art department. It's just not useful to
the part of me that's an engineer. Pretty has worth, just different
worth than useful.
>
>
> 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!
Exactly. You've described a chaotic but easily reversible system, and
that makes it unsuitable to be random by my "unguessability" metric.
There exists an algorithm that's faster than guessing, and so
therefore it isn't random.
>
>
>> 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.
Yes. Again, we're in agreement on this.
If I think some system is unguessable to 256 bits, and it's really
unguessable to 10 bits, then someone who knows those ten bits can
easily search for a state that I think is unsearchable. (At least in
principle -- ten bits worth of calculations that take a century each
is a different thing entirely, but that's only because centuries are
longer than nanoseconds.)
Jon
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
