Ultra-low-cost True Randomness

Cryptocrat writes "Today I blogged about a new method for secure random sequence generation that is based on physical properties of hardware, but requires only hardware found on most computer systems: from standard PCs to RFID tags." Basically he's powercycling memory and looking at the default state of the bits, which surprisingly (to me anyway) is able to both to fingerprint systems, as well as generate a true random number. There also is a PDF Paper on the subject if you're interested in the concept.

Re:A Slightly More Expensive Method

[NetCow]

Mersenne Twister is not a random number generator, it's a pseudo-random number generator.

Randomness is measured as entropy. See here for details: http://mathworld.wolfram.com/Entropy.html [wolfram.com]

How it compares to the Mersenne Twister

[benhocking]

The Mersenne Twister is a pseudo-random number generator. For many uses, this is preferable to a true random number generator as it is easily repeatable. (One can also repeat the results of a true random number generator by storing the output, but depending on how many random numbers you're generating, this might be space intensive.)

That said, although this might be "true" randomness, what kind of randomness it is? Uniform over a range? Gaussian? Weibull? Most likely, none of the above if it can be used for fingerprinting systems. (No, I did not RTFA.)

Re:A Slightly More Expensive Method

[morgan_greywolf]

Well, the theory goes something like this: the more wide and varied the seeds you feed to a random number generator, the more truly random your results. Many programs use a timestamp from the system clock as a seed, or even a timestamp as seed to put through the random number generator to get another random number that is used as a seed, etc. ad finitum. Of course, the system clock has only so much granularity, so based on that granularity there are a finite number of seeds for each 24 hour period. If you knew exactly when the random number was generated, you could, in theory, keep trying the corresponding seed and eventually (due to the fact that random number generators aren't truly random) you'd find out what the random number is.

Not good for cryptography relying on random numbers.

So, if you start with a seed that is more or less already random, you get a more truly random number. That's why programs like GPG rely on random keypresses or mouse movements to generate the random number for your key. More entropy means more truly random.

But this relies on user behavior, so if we grab random bits from a chip by recycling the power...bammo! More random!
   

This is hardly random

[gillbates]

As an embedded engineer, I've encountered numerous cases where power cycling RAM did not alter the contents.

In fact, I've seen systems boot and run even after the power was cut for several seconds. Some types of SRAM and SDRAM have the ability to retain an (imperfect) memory image even at very low voltage levels. Sure, it's not guaranteed to be accurate by the manufacturer, but RAM "images" are a pretty well known phenomenon. In some cases, the contents of memory can be reconstructed even after the computer has been powered off and removed to a forensic laboratory.

This is not random at all. In fact, it's more likely to produce an easily exploitable RNG than anything else; I would not be at all surprised if the standard UNIX random number generator provided better security.

A suggestion for this blogger

[Quila]

Learn How To Use Capital Letters At The Beginning Of Sentences!

Our research group will answer questions soon...

[fubob]

We were surprised to suddenly get attention to this paper, but apparently Slashdot readers are watching the security seminar at UMass Amhest.

Anyhow, we will be answering questions in this thread. So if you have any questions, post them here and Dan Holcomb will get back to you as soon as he can.

Cheers,
-Kevin Fu

Re:Four

[ukatoton]

RTFA
There are 3 states the bits can fall into:

1. initially (almost) always 0
2. initially 0 or 1 with somewhat even probability
3. initially (almost) always 1

Using the bits that fall into category 2 to generate the number will result in a random number, as these are known to change randomly

since it is now known which bits will change with each power cycle, those bits can be used as a source of true randomness

Bits falling into the other two states are ignored for the random function and are used for the identification function.

Re:Curious

[Stripe7]

Read the article, there are 3 states for bits of RAM at power up. 1. Always 0 2. 50/50 flipping between 0 and 1 3. Always 1 For fingerprint use 1 and 3 and mask out the flipping bits, for Randomness mask out the consistent bits.

Fingerprinting

[jgoemat]

Most likely, none of the above if it can be used for fingerprinting systems. (No, I did not RTFA.)

Basically some bits are more likely to be 0, some are more likely to be 1 and some are apparently random. Many cycles are done to identify which bits fall into which category. The ones more likely to be 0 or 1 are used to determine the fingerprint. The ones that appear to be totally random are used to generate random data.

Re:Four

[psmears]

If I have a die that is weighted to land on 5 or 6 almost every time, it's not random.

It is random, it just isn't fair.

What's more, you can use it to generate fair, random 0s and 1s: throw it twice, and if you get 5-6, that's a 0; if you get 6-5, that's a 1. If you get two of the same number (5-5/6-6), repeat from the start. Assuming the throws are independent (i.e. it has no memory), and the probabilities of 5&6 are both greater than zero, you'll get a 0 or 1 with equal probability.

The article plays a similar trick, but it uses a hash function to even out the probabilities...

HotBits

[The -e**(i*pi)]

The only way I know of generating truly random numbers (not psudorandom) is hot bits which works on the principle of single radioactive atoms decaying after a perfectly random, in every sense of the word, time. http://www.fourmilab.ch/hotbits/ [fourmilab.ch]

Re:Four

[ajs]

I'm not entirely clear on why this is more interesting than just using timing like most of the rest of the world does. Perl has, for example, long used a setjmp/longjmp-based timing test for its Math::TrulyRandom [cpan.org] package by Matt Blaze and Don Mitchell of AT&T and of course most modern Unix-like systems implement /dev/random and /dev/urandom again based on timing. RFC1750 [ietf.org] has given useful directions on how to generate random numbers on generic hardware for well over a decade. I recall first reading this RFC, not long after it came out. It really changed my understanding of random numbers on computer hardware.

This just doesn't seem all that newsworthy, though it's cool enough as yet another random number generation technique, I suppose.

Old news - I have already been granted patents

[ironring]

This is a bit of old news. I have already authored and been granted several patents in this area.
6,906,962 Method for defining the initial state of static random access memory
6,828,561 Apparatus and method for detecting alpha particles
6,738,294 Electronic fingerprinting of semiconductor integrated circuits
I have several other ideas for application of this technology and would be happy to discuss if someone is interested.
Paul