Ultra-low-cost True Randomness 201
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 (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!
Re: (Score:3, Insightful)
Re: (Score:2)
You could in theory construct a truly random numbe
Re: (Score:2)
The method of generating random numbers that this article proposes follows the same principle. And the "randomness" that it provides becomes more random as process feature size shrinks. At 45nm, the steady-state bias (if there is one) that a circuit comes to (depending on the circuit design) is truly random in two ways:
1. If, in the case of a CMOS circuit in which the state of a flip-flop depends on charge accumulated during power-up, small
Re: (Score:2)
Re: (Score:2)
Of course, then quantum mechanics and all that jazz has come along, and one of the things it fundamentally says is that some things are entirely based on probability, and as such are not determinis
Re: (Score:2)
Obligatory (Score:2)
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:2)
Re: (Score:2)
and every time, everybody disagrees...
once again... for the record... From My CS classes:
A number sequence can be defined as "Sufficiently Random" if the simplest algorithm to generate said sequence is shorter than the sequence itself.
ergo: 012346567890123465678901234656789012346567890123465678901234656789 Ain't Random
for i=0, i50,i++{
print (i mod 10);
}
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
i++;
Every value of i is equally represented. Must be a perfect random number generator.
Re: (Score:2)
Re: (Score:2)
Just because something is random, doesn't mean you won't be able to assign patterns to it after the fact; it only means you couldn't have predicted the patters beforehand.
Re: (Score:2)
A random number generator would have an equal probability of generating any of these strings of bits,
011010011010
000000000000
111111111111
010101010101
101010101010
Re: (Score:2)
To use your example, a fair RNG would indeed be equally likely to generate all of the above strings. But with equal likelyhood, any other 12-bit sequence can also be generated. Compression works by assigning symbols to recurring sequences, where these symbols can be stored in le
Re: (Score:2)
011010011010
000000000000
111111111111
010101010101
101010101010
Of course, equal probability does not guarantee the randomness of your output: your generator may for example be a simple counter, going 000000, 000001, 000010 and so on. Not random at all, but it satisfies your requirement. So, equiprobability is a must have, but independence is also required
True randomness is really difficult to ascerta
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.)
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)
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)
Keep in mind that there are several 'grades' of randomness. Something that is good enough for your average Monte Carlo analysis is likely sub par for serious cryptographic purposes.
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:2)
You are probably referring the thermodynamical entropy, which is based on continuous state distributions. While in most cases continuous and discrete solutions are closely related (allowing summations to be replaced with integrals and vice versa), it has been shown in this case that these notions of entropy are not comparable (the limit of the discrete entropy as the number of divisions goes to infinity also go
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
Method to measure randomness (Score:2)
I learned a heck of a lot working with dieharder especially considering my lack of mathematical acumen. The author and friends were unbelievably patient and helpful. In my book it's the best tool ever.
Debian package too!
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
Re: (Score:2)
Re: (Score:2)
Oblig. XKCD (Score:5, Funny)
Re: (Score:3, Funny)
Re: (Score:2)
Re: (Score:2)
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)
Re: (Score:2)
Also depends on how the sense/charge refresh circuit is designed.
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)
Re: (Score:2)
Oh, right; Slashdot.
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..
Re: (Score:2)
Do you have any idea how expensive a politician is (Score:2)
Then again, if you paid enough for your politician, he'd be less random on your particular issue. Hmm.....
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.
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]!
Not for PC's - yet (Score:2)
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
OK, first one, retention time... (Score:2)
This shouldn't affect the fingerprinting, because you fingerprint on the highly-biased cells.
But how does this biasing effect interact with the true RNG operation? Have you done retention time experiments?
also, DRAM is worse on the retension time, but is it perhaps still suitable for the fingerprinting? Have you evaluated this yet?
Re:Our research group will answer questions soon.. (Score:2)
http://it.slashdot.org/comments.pl?sid=292837&cid=20543831 [slashdot.org]
I've only looked at one of them:
http://www.patentstorm.us/patents/6738294.html [patentstorm.us]
Second - what can you say about NH as an entropy distiler? Are there any nice provable properties that follow from it being a universal hash function?
Thanks for doing interesting work!
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.
Re: (Score:2)
It's conceivable that at some point in the future there would be some kind of memory that would become popular on general-purpose PC's for which this technique would work. But even then, there are some other reasons why I'm thinking you wouldn't want to use this technique for a PC (as opposed to an RFID):
Fascinating idea, but not always cheep (Score:2)
Easy (Score:2)
and another few ways (Score:2)
1. IRQ's on the system since it started, for one or more more devices.
2. cpu-serial
3. check the number of cpu-cycles that passed since the seed-generator started (a bit like the chaos theory if you have many processes running)
4. uptime of the system
5. local time (do have have a little randomness due to variations op the local clock-circuit)
6. serial of the harddrive
How does this compare to what linux already does? (Score:2)
http://en.wikipedia.org/wiki//dev/random [wikipedia.org]
Another existing method of generating secure random numbers, used by the java VM, is starting and stopping threads and gathering statistics about how the OS allocates time to those threads, which has been shown to be fairly unpredictable.
Given the flaws with the method outlined by other posters... sounds like this really doesn't offer anything
It's all (Score:2)
Random Number (Score:2)
HotBits (Score:3, Informative)
Re: (Score:2, Insightful)
They vary in quality, but it really doesn't matter. With the proper post-processing, they all provide true randomness that is basically as good as randomness is possible to be.
Radioactive decay tends to be the most expensive and the least practical. Shot noise in a reverse-biased zener diode is generally
Iffy. H/W != "true" randomness (Score:2)
TFA did not say just how random it is.
The idea that the data is compromised enough that significant portions of it can be used to fingerprint, which is close to the opposite of the meaning of true randomness since it is based on a pattern, sounds to me like the more random components are in fact not so random.
In other words the jitter down near the threshold of signal discrimination may look real random but actually may look a lot like the sa
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
Questions/requests (Score:2)
(2) if you're not joking, were you some key figure at NE2 encryption, noted by an AC a few posts up?
I've observed this behavior in SRAM... (Score:2)
Metastable flip-flops more appropriate? (Score:2, Insightful)
Re:933245789124398 (Score:5, Funny)
You would expect that, you fucking pervert.
Re: (Score:2, Funny)
Re: (Score:2)
If the startup state of the RAM banks are so predictable that you can base a fingerprint on it, it's not even vaguely random, is it?
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.
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.
Re: (Score:2)
The level of electrical noise in the system at launch is predictable.
In some bits, the electrical noise is predictably higher than the tipping point to count it as "1".
In some bits it is predictably lower than the tipping point to count it as "0".
In some bits, it is predictably proximate to the tipping point to count it as either "1" or "0".
In ALL cases, it is predictable.
If I have a die that is weighted to land on 5 or
Re: (Score:2)
In ALL cases, it is predictable.
If I flip a coin onto my hand, it's predictable that it will land on either heads or tails. That doesn't mean it's not random though.
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...
MOD PARENT DOWN! (Score:2)
Re: (Score:2)
Just i forgot the link, and the actual number, which by a random luck i choose the same....
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:3, Informative)
Re: (Score:2)