Slashdot Log In
Ultra-low-cost True Randomness
Posted by
CmdrTaco
on Mon Sep 10, 2007 10:04 AM
from the and-a-damn-fine-hack dept.
from the and-a-damn-fine-hack dept.
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.
Related Stories
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
A Slightly More Expensive Method (Score:5, Interesting)
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 (Score:4, Funny)
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!
Parent
Re: (Score:3, Insightful)
Re: (Score:2)
Re: (Score:2, Insightful)
123456789123456789123456789123456789123456789
That's how to test uniformity, but not randomness.
Re: (Score:3, Insightful)
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
Re:Kolmogorov complexity not tractable - compressi (Score:3, Funny)
perl -e 'print 1..9,0..9,0..9,0'
Re: (Score:2)
Re: (Score:3, Informative)
Randomness is measured as entropy. See here for details: http://mathworld.wolfram.com/Entropy.html [wolfram.com]
How it compares to the Mersenne Twister (Score:4, Informative)
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.)
Parent
Fingerprinting (Score:3, Informative)
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:Fingerprinting (Score:4, Funny)
Parent
Re: (Score:3, Insightful)
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: (Score:3)
Re: (Score:2)
Re: (Score:2, Informative)
Re: (Score:2)
Re: (Score:2, Interesting)
Re: (Score:3, Interesting)
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 "information entropy." If they're different, then I blame the folks that overload technical words.
That said, I always thought "random" simply meant "the next outcome is not predictable based on all previous measurements." Therefore the measure of "random" would b
Re: (Score:3, Interesting)
Another way to put it is that before the advent of quantum mechanics, every measurement of entropy was only meaningful in a relative, differe
Read Gleick's Chaos (Score:3, Interesting)
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
Oblig. XKCD (Score:5, Funny)
Re: (Score:3, Funny)
Fatal error: not enought random available (Score:2)
Natural Ice (Score:2, Funny)
This sounds nuts (Score:2, Redundant)
Re: (Score:2)
Re: (Score:3)
P(bit) vs. fabrication variations (Score:3, Interesting)
This is a very interesting phenomenon, but a lot more data is needed to show that it provides consistent behavior.
The quality of randomness.... (Score:2, Insightful)
I have a better solution (Score:2)
And consequently no information could be extracted that scenerio -- wow, I think I just proved that you can't transmit information across a quantum entanglement..
A VERY interesting idea... (Score:5, Interesting)
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: (Score:3, Funny)
I wonder how often they go around saying to people, "Whoa. I know Kevin Fu."
This is hardly random (Score:3, Informative)
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 (Score:5, Interesting)
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.
Parent
Re:This is hardly random (Score:4, Insightful)
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]!
Parent
The problem with random numbers (Score:5, Funny)
A suggestion for this blogger (Score:4, Informative)
Our research group will answer questions soon... (Score:5, Informative)
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. (Score:5, Interesting)
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 (Score:3, Informative)
Old news - I have already been granted patents (Score:5, Informative)
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 (Score:5, Funny)
You would expect that, you fucking pervert.
Parent
Re:Four (Score:5, Informative)
There are 3 states the bits can fall into:
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
Bits falling into the other two states are ignored for the random function and are used for the identification function.
Parent
Re:Four (Score:4, Informative)
This just doesn't seem all that newsworthy, though it's cool enough as yet another random number generation technique, I suppose.
Parent
Re: (Score:3, Informative)
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...
Re: (Score:2)
Re: (Score:2)
Re: (Score:3, Informative)
Re: (Score:2)