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

[eldavojohn (898314)]

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

[BadAnalogyGuy (945258)]

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:

[Mc1brew (1135437)]

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 dice in hand *Distance of hand from table *Number of dice *Potential values of dice *Density of table *etc..... By the time you write down all the variables a value has been generated. Just because you didn't have enough time to evaluate the scenario, doe

Re:

[NetCow (117556)]

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 (724439)]

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

[benhocking (724439)]

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

Re:

[solafide (845228)]

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 statistically random: they claim it's based on thermal noise. But the startup temperature of a computer does not have that much entropy, so the thermal noise isn't reliable. Just because something's garbage doesn't mean it's statistically random.

Re:

[Cyberax (705495)]

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.

Read Gleick's Chaos

[Weaselmancer (533834)]

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 team of researchers had a bathtub with a dripping faucet. They tuned the dripping until the drips fell at random intervals. Nothing rhythmic about it. As the drop broke away from the faucet, it was setting up a vibration in the remaining water that would

Re:

[Matje (183300)]

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 Complexity. A random number then is a number that cannot be represented by a program (in some code language) that is shorter than the random number itself. In other words: if the smallest program that outputs number X is the program "print X" then X is considered a

Oblig. XKCD

[IcedTeaisgood (1148451)]

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

P(bit) vs. fabrication variations

[G4from128k (686170)]

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.

A VERY interesting idea...

[nweaver (113078)]

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.

This is hardly random

[gillbates (106458)]

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

[tlhIngan (30335)]

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

[nickovs (115935)]

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

[operagost (62405)]

You can never be sure [random.org].

A suggestion for this blogger

[Quila (201335)]

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

Our research group will answer questions soon...

[fubob (7626)]

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.

[rpp3po (641313)]

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.

Old news - I have already been granted patents

[ironring (598705)]

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

[BadAnalogyGuy (945258)]

23423483837223429723432891023478343589435892

You would expect that, you fucking pervert.

Re:Four

[ukatoton (999756)]

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

[ajs (35943)]

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:

[AmIAnAi (975049)]

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