very high speed hardware RNG

[Jerry Leichter]

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 majordomo at metzdowd.com