Slashdot Mirror
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 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.
:)
But in all seriousness, I wonder how this compares to the Mersenne Twister (Java implementation & PDF)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?
My work here is dung.
23423483837223429723432891023478343589435892
You would expect that, you fucking pervert.
Randomness is definable.
Why, take a look at this Wikipedia link. 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!
http://xkcd.com/221/
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.)
Ben Hocking
Need a professional organizer?
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.
Two wrongs don't make a right, but three lefts do.
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.
Test your net with Netalyzr
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.
The society for a thought-free internet welcomes you.
TFA talks about SRAM, rather than DRAM. So there's no capacitor involved for data storage - each cell is a transistor-based state machine.
Any sufficiently advanced bug is indistinguishable from a feature.
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 jiggle until the next drop fell. It was highly nonlinear.
They constructed a phase space where you would look at the time between any two drops. On the other axis was the time between the one previous to that. So on one axis you have the time bewteen drops 1 and 2, and on the other axis between drops 2 and 3.
It turns out that an attractor would emerge. The times did not scatter around the page randomly, they grouped in clusters. There was an underlying order that this method would expose.
So - to answer your question, what you could do would be to take your stream of numbers, and examine them in phase space looking at the differences between each data point. If nothing shows up in a two dimensional plot, go for three. Use n1-n2, n2-n3 and n3-n4 on your axis. Add dimensions if you need to beyond that. See what it takes to make your data cluster, if it ever does. The more complex your data is, the more dimensions it will take to visualize that.
Weaselmancer
rediculous.
You can never be sure.
Gamingmuseum.com: Give your 3D accelerator a rest.
Learn How To Use Capital Letters At The Beginning Of Sentences!
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
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.
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.
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.
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.
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...
Need to type accents and special characters in Windows? Use FrKeys
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/
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 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 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.
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
Hey, I'm a 23423483837223429723432891023478343589435892 you insensitive clod!
First post = troll. Cleverly worded post designed to enrage others = flamebait.
perl -e 'print 1..9,0..9,0..9,0'
The article makes a short note on metastability, but wouldn't this be more appropriately applied to a register array of flip-flops, which are much more susceptible to falling into a metastable state, instead of a ram? If he's using the SRAM (he never clarifies), he's counting on the charge of a single capacitor being randomly dispersed in order to enforce randomness, not the properties of the transistors at all. Using flip-flop circuits by violating their setup/hold times seems like it'd be more effective. It has probably already been explored. The article says so itself. So what's novel here?