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.

A Slightly More Expensive Method

A slightly more expensive but somehow even more random method is to seed the generator against the words and phrases that come out of the mouth of South Carolina's Miss Teen USA [youtube.com].

But in all seriousness, I wonder how this compares to the Mersenne Twister [wikipedia.org] (Java implementation [gmu.edu] & PDF [hiroshima-u.ac.jp])that I use at home? I am almost sure this new proposed method is more efficient and faster, when will there be (I know, I'm lazy) a universal implementation of it? :)

Also, this may be a stupid question, but I wonder how one measures the 'randomness' of a generator? Is there a unit that represents randomness? I mean, it would be seemingly impossible to do it using observation of the output so I guess all you can do is discuss how dependent it is on particular prior events and what they are, theoretically. Can you really say that this is 'more random' than another one because you have to know so much more before hand about the particular machine & its fingerprint in order to predict its generated number?

Random karma whore

Randomness is definable.

Why, take a look at this Wikipedia link [wikipedia.org]. You can never tell whether it represents the truth or some crackpot's claim to it or just some troll's malicious vandalism.

Voila! Randomness!

Re:

That link brought me to the conclusion that randomness doesn't exist as much as I thought. It uses the example of rolling dice, random right? Not really... Just too many variables to consider over the given amount of time. *Density of dice *Placement of

Re:

I think the easiest way to measure "randomness" is to (whilst keeping the environment the same) generate a massive number of "random" numbers, and check the number of occurrences of values to their expected number of occurrences. Probability would dictate

Re:

123456789123456789123456789123456789123456789

That's how to test uniformity, but not randomness.

Re:

it is a lot more tricky than that. Test your method against the following string:

12345678901234567890

See? The distribution of digits doesn't tell you a whole lot about the randomness of a stream.

A nice way to define randomness is using Kolmogorov Complexit

Re:Kolmogorov complexity not tractable - compressi

For instance, in the 123456789012345678901234567890 sequence example, any self-respecting compressor such as Zip would create something like "1234567890 times 3", which is pretty close to the shortest program which generates the sequence.

perl -e 'print 1..

Re:

I think you'd also need some means of defining the randomness of distribution in your sequence. For instance, 01010101010101010101010101010101 doesn't look very random.

Re:

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

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.)

Fingerprinting

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

Re:Fingerprinting

Wow, that actually makes sense. I'll bet you cheated and RTFA, didn't you?

Re:

Randomness is measured statistically using multiple tests: see Knuth, Art of Computer Programming Volume 2, Chapter 3 for a thorough discussion of common statistical randomness tests, or here [fourmilab.ch] for a practical testing tool.

I don't expect this to be statisti

Re:

Thermal noise random number generators do not depend on temperature (unless cooled to liquid nitrogen temperatures). Normal room temperature provides quite enough random fluctuations for good generators.

Re:

You can do some stats on the output, for example: http://citeseer.ist.psu.edu/maurer92universal.html [psu.edu]

Re:

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 thr

Re:

Also, this may be a stupid question, but I wonder how one measures the 'randomness' of a generator? Is there a unit that represents randomness? I mean, it would be seemingly impossible to do it using observation of the output so I guess all you can do is d

Re:

Yeah, it can be measured. There is no unit, though, as its a measure of entropy. So things are more or less random than something else. I imagine randomness studying program assign numbers to it. a random number is just a number; '1' might be randomly sel

Re:

There is no unit, though, as its a measure of entropy.

Eh, well, the unit of entropy is actually "energy per temperature"*, so there are physical units associated with it. Of course, that's physical entropy, and I don't know that it's the same as "informa

Re:

Entropy is fascinating. It's proportional to the logarithm of the number of microstates, but until the advent of quantum mechanics, there was not good way to number the microstates of a given physical system. Once you have the uncertainty principle, you ca

Read Gleick's Chaos

Also, this may be a stupid question, but I wonder how one measures the 'randomness' of a generator?

Read James Gleick's Chaos.

There is a method in that book that describes how they extracted attractors from a stream of data. Here's how it works.

A te

Oblig. XKCD

http://xkcd.com/221/ [xkcd.com]

Re:

Oblig Dilbert: http://www.random.org/analysis/dilbert.jpg [random.org]

Fatal error: not enought random available

OK, do we in this world have a problem with not sufficient randomness in our keys or something?

Natural Ice

Is pretty low cost to get some randomness. Some friends like jug wine though. Although I'm extremely cheap, so I just go for 100 proof stuff. $12.00 and you can get a whole bottle of randomness.

This sounds nuts

The contents of a power-cycled DRAM cell are highly correlated to whatever was stored in it before power was lost. Geez, think about how a DRAM works... it's a capacitor (aka an integrator)! That's the last place I'd ever look for randomness.

Re:

Yeah, but the headline of the PDF says: "Initial SRAM state..."

Re:

TFA talks about SRAM, rather than DRAM. So there's no capacitor involved for data storage - each cell is a transistor-based state machine.

P(bit) vs. fabrication variations

I wouldn't assume that these fingerprints are as unique or pattern-less as one might hope (a fact discussed in the pdf). All of the RAM chips from a given wafer or given mask may share tendencies toward some patterns of the probability of a 0 or 1. These patterns may appear as correlations between rows and columns of a given chip. Location on the wafer (in the context of nonuniformities of exposure to fab chemicals) might also systematically affect the aggregate probabilities of 0 or 1 or the repeatability of the fingerprint. The quality of these fingerprints to be consistent or random might change from run to run and from manufacturer to manufacturer. Finally, I'd bet that the probabilities vary systematically with temperature -- e.g., the probability of a 1 increases for all bits as the chip's temperature increases.

This is a very interesting phenomenon, but a lot more data is needed to show that it provides consistent behavior.

The quality of randomness....

Will vary with the length of time the computer has been off. There is a suprising amount of non-volatileness in DRAM. I liked Alan Touring's suggestion that all computers come equiped with a small radioactive source and detector. The random breakdown an

I have a better solution

Pick a question. Then keep asking that question to a politician. You should get truly randomized results. If you doubt me, just take a politician with an opposite stance, and repeat the process. The answers will not be polar opposites.
And consequently no i

A VERY interesting idea...

the true RNG properties rely on the fact that:

a: Many of the bits are sorta random, but physically random. So very biased coins, but true randomness.

b: With the right reduction function, you can turn a LOT (eg, 512 Kb) of cruddy random data to a small amount (128b-512b) of very high quality, well distributed random.

And the fingerprinting relies on the fact that:

a: Many other of the bits are physically random, but VERY VERY biased. So map where those are and record them and it is a very good fingerprint. And since it is all silicon process randomness going into that, it is pretty much a physically unclonable function.

Kevin Fu has some SMART grad students.

Re:

Kevin Fu has some SMART grad students.

I wonder how often they go around saying to people, "Whoa. I know Kevin Fu."

This is hardly random

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.

Re:This is hardly random

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.

I've had this bite me, and exploited it.

It bit me when booting into Windows CE - you'd power cycle the thing, and the OS would boot with the old RAM disk you had - we'd gotten to the point where we'd have the bootloader wipe the kernel memory so the data structures were all corrupted by the time the OS was trying to decide between mounting the RAM disk (object store) and starting fresh. It turns out that the longer an image is unchanged in RAM, the more likely the cells woudl be biased such that if you cycle the power on them, they're more likely to lean towards the way they were before power was cut.

The time I exploited it, I didn't have any way of logging. Logging to serial port caused issues (timing-sensitive code), so I logged to memory (and no, I had no filesystem running, so I couldn't log to file). My trick was to simply log to a circular RAM buffer. When it crashed, I would just power cycle and dump the RAM buffer. Even though the data was fresh, it was enough to make out what my debug message was trying to say (almost always perfect). This was readable after a brief power cycle, and was still readable after turning power off for nearly a minute. The characters got corrupted, but since it was regular ASCII, you could still make out the words.

Re:This is hardly random

There are a couple of things to note here. Firstly, SDRAM and SRAM behave very differently. Synchronous dynamic RAM can retain charge in the capacitors for quite some time after being powered down and there is very little one can do about it, but the paper discusses static RAM. With static RAM there is a difference between being "powered off" and having the Vcc rail clamped to ground. Active clamping of the power line is much more effective at clearing the RAM than even just disconnecting it from the power supply, for reasons which become obvious when you look at a classic six transistor CMOS RAM circuit [wikipedia.org]. Without clamping, bias will remain for exactly the same reason that SRAM doesn't consume much power; current only flows when the data changes.

As for it being a good RNG; the state of RAM on power-up is probably a lousy "random number generator", but the statistics in the paper suggest it is a fairly good "source of randomness". There's a big difference between bias and unpredictability (think about dice with '1' on five of the sides and '0' on the remaining side). You wouldn't want to use the state without putting it through a compression function first, but it's a much better seed than using clock() [berkeley.edu]!

The problem with random numbers

You can never be sure [random.org].

A suggestion for this blogger

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

Our research group will answer questions soon...

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

Don't follow the hype. Does not apply to PC's.

The original paper is much better than CmdrTaco's quick conclusions.
The described method is ONLY for SRAM (statical RAM), no DRAM, no SDRAM. You can find this on RFID chips and in a CPU'S cache, not in RAM. As there is no way to access a CPU's cache uninitialized, I can't see why this should be useful.
If you have to modify a CPU first, to allow access to it's unitialized caches (think about all the unwanted implications), it's much cheaper to just give it a thermal diode and register to poll (as most modern CPU's already have).
After all the described method is just another way of collecting thermal noise. As RFID's are custom designs most of the time, also there it would be cheaper to just use a thermal diode.
The only application for this would be if you had to develop strong crypto for legacy RFID chips.
Slashdot stories get worse by the day.

HotBits

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]

Old news - I have already been granted patents

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

Re:933245789124398

23423483837223429723432891023478343589435892

You would expect that, you fucking pervert.

Re:Four

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:Four

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.

Re:

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

Re:

I think I know the answer, but I've RTFA, so it doesn't count.

Re:

Because the output of the method is not a truly random number. It is a number with some amount of randomness and some amount of regularity. To fingerprint, you look for the regularity, and to make random numbers, you refine the randomness through some kind

Re:

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.

Re:

The problem with the last is that it's a constant, not random at all.