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