Re: Wild Idea for RNG

[Herb Sutter <herbs@interlog.com>]

Warning: I'm no expert, my response is just a semi-informed opinion
(emphasis on "semi-").

At 02:19 1995.09.27 -0400, Ray Cromwell wrote:
>So, why not construct a turing machine with a large state transition
>table, input a random program, and get a 1 or 0 bit depending on
                ^^^^^^
>whether it halts in X number of cycles. You could even get more
>than 1 bit out of it by measuring how many cycles it takes to halt
>(if it halts before X) and use the LSB. Is it as secure as
>the halting problem? (intractable to devise an algorithm used
>to predict a bit with more than 50% confidence if you knew the
>state table?) 

Your randomness will depend on the prior randomness of your original
input... and if you already have that, the TM won't give you any additional
randomness (rather, this approach will just take all the randomness you give
it and reduce it to 1 bit of randomness, losing all the rest).

On the other hand, if the 'random' program is not already truly random, then
you may well have patterns in the bits generated by the halting observation.
For instance, if you use a known PRNG to get your "random" programs, then
given the same seed you will end up with the same programs (and therefore
the same resulting 'random' bits from the TM halting output)... which, in
other words, gains you nothing AFAICS over simply using the PRNG's output
directly, except of course that it exercises your CPU. :-)  The attacker
still only needs to figure out the seed.

>Grab a picture of the current bitmap on your screen. Run it through
>a good compression algorithm (say, an arithmetic/Q-coder or
>one of the LZ schemes). Grab the LSB of every 4th byte or so.
>If the screen is size 1024*768*8, that's 786432 bytes. Let's assume
>a 10 to 1 compression ratio = 78643 bytes. Let's assume you take
>1 bit from every 10 byte, that's 983 bits of entropy.
>
>The screen will often contain data like:
>
>random placement of icons and windows

Not on my machine (or most others, I'd wager)!  I thought about this, and
whenever I'm running Netscape (for instance) my screen is probably identical
over 50% of the time because I tend to have the same things open when I run
a given program.

Even in the general case, consider that most people have a preferred desktop
layout (in Windows, they have ProgMan sitting in one place on the screen
with usually the same groups visible/open)... not only will that piece of
the screen bitmap not give you any randomness from one run to the next, but
unless you go looking for "things that haven't changed since last time" your
program won't even know what's reducing your randomness.

>current time

Better, but be careful how you use it; that's what Netscape thought too. :-)

>current applications running, and the data in their windows
>
>
>If Netscape was running for instance, part of the random bits
>would come from the bitmap representation of the data in Netscape's
>window which would depend on the URL being displayed.

This sounds a bit better... except, of course, that when you initiate a
secure session in Netscape with a specific party/server, your screen has a
very good chance of looking the same each time you connect with that entity
because it is the same URL. :-)

Would someone who's more informed please correct my analysis?  Thanks in
advance,

Herb

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Herb Sutter                 2228 Urwin, Suite 102       voice (416) 618-0184
Connected Object Solutions  Oakville ON Canada L6L 2T2    fax (905) 847-6019