Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Ultra-low-cost True Randomness

CmdrTaco posted more than 7 years ago | from the and-a-damn-fine-hack dept.

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

Sorry! There are no comments related to the filter you selected.

933245789124398 (1, Funny)

LiquidCoooled (634315) | more than 7 years ago | (#20538979)

234 234838372 234 29723432891023478343589435892?

Re:933245789124398 (5, Funny)

BadAnalogyGuy (945258) | more than 7 years ago | (#20539047)

23423483837223429723432891023478343589435892

You would expect that, you fucking pervert.

Re:933245789124398 (-1)

Anonymous Coward | more than 7 years ago | (#20539087)

You're worse than the goatse troll for even reprinting that.

I think I'm going to be sick.

Four (-1)

leuk_he (194174) | more than 7 years ago | (#20539369)

The post title "4" is generated trowing a reliable dice and is truly a random number.

By this i present you a new random number function:

int RandomDice(){
return 4
}

Re:Four (1)

ShieldW0lf (601553) | more than 7 years ago | (#20539455)

You hit the nail precisely on the head as to why this is a bunch of bollocks.

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 (5, Informative)

ukatoton (999756) | more than 7 years ago | (#20539693)

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 (0)

Anonymous Coward | more than 7 years ago | (#20539721)

You, sir, are an idiot. The article explains that only some of the bits are consistantly predictable while *others* are consistantly random. The predictable bits can be used for fingerprinting, the random ones for... random bits.

Re:Four (1)

ShieldW0lf (601553) | more than 7 years ago | (#20540011)

You don't understand what random means, or the nature of the hardware you're looking at.

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 6 almost every time, it's not random.

If you decide to use 5 as 1 and 6 as 0, and treat them as equal probabilities because you are ignorant to the fact that 5 is weighted higher than 6, you will not see a random result. And if you play against me, you will lose because I am aware of the predictable nature of the results and you are not.

This system is not random, and is subject to gaming of any system that treats it as though it was.

And I'm most definitely not an idiot.

Re:Four (1)

edwdig (47888) | more than 7 years ago | (#20540753)

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 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:Four (2, Informative)

psmears (629712) | more than 7 years ago | (#20541419)

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:Four (1)

Baron Eekman (713784) | more than 7 years ago | (#20539911)

You can at least cite properly:

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

Re:Four (1)

Daimanta (1140543) | more than 7 years ago | (#20540513)

Compiler error! return 4 does not terminate

MOD PARENT DOWN! (1)

Asmor (775910) | more than 7 years ago | (#20541397)

Parent stole his joke from xkcd (posted above) without giving credit. Mod douche-nozzle parent down, please.

A Slightly More Expensive Method (4, Interesting)

eldavojohn (898314) | more than 7 years ago | (#20539003)

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 (4, Funny)

BadAnalogyGuy (945258) | more than 7 years ago | (#20539091)

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:Random karma whore (3, Insightful)

Mc1brew (1135437) | more than 7 years ago | (#20539701)

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, doesn't make it random. The problem with random number programs is that the algorithm is predictable, thus it depends of the variables fed to it for randomness. The algorithm hopes that by smashing all the variables together it will somehow not be predictable. In essence this seems true because unrepeatable values such as time are taking into consideration, but assuming you know all the variables entering the algorithm, you should be able to predict the output and thus not random. Well that was all probably off topic.....

Re:Random karma whore (1)

egyptiankarim (765774) | more than 7 years ago | (#20541537)

Excellent point. Just because a scenerio has reached a level of complexity that it becomes very difficult to predict its outcomes accurately shouldn't qualify it as random.

I always thought it was silly that if people are willing to recognize the predictability (to at least a somewhat reliable degree) of something as complex as global weather patterns, then how could they claim that something like a dice roll was random when it's clearly a MUCH smaller system? The only difference is that the morning news doesn't invest millions of dollars on computers, distributed networks of remote site data collection and trained professionals to figure out if I'm going to get an easy 8 or snake eyes.

Re:A Slightly More Expensive Method (1)

name*censored* (884880) | more than 7 years ago | (#20539107)

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 that a true random number generator would return values to within a tiny margin of what would be expected. The "unit" would probably be "standard deviations" (ie, the bad random number generator has a bias for $SOME_VALUE of 2 standard deviations)

Re:A Slightly More Expensive Method (1, Interesting)

Anonymous Coward | more than 7 years ago | (#20539267)

The best test for randomness is the compressibility of the stream. If the stream is truely random then there will be no coherency and no redundant data, and so be uncompressable.

Re:A Slightly More Expensive Method (2, Insightful)

stranger_to_himself (1132241) | more than 7 years ago | (#20539291)

123456789123456789123456789123456789123456789

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

Re:A Slightly More Expensive Method (2, Insightful)

Matje (183300) | more than 7 years ago | (#20539303)

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 random number.

Re:A Slightly More Expensive Method (0)

Anonymous Coward | more than 7 years ago | (#20540215)

That's a nice definition, but an impossible to use in practice. There probably is no algorithm to generate the shortest Turing Machine which produces output X. (I'd have to think a bit to see if you can show it is equivalent to the Halting Problem.)

Kolmogorov complexity not tractable - compression? (1)

tucuxi (1146347) | more than 7 years ago | (#20540445)

Indeed - Kolmogorov complexity is nice to play with, but can't be calculated.

A useful approximation is to use "compressed size". An ideal, lossless compressor would be readily calculating the kolmogorov complexity. 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.

Indeed, really-good compression is close to AI. To say the same thing in progressively shorter ways, you need to find deeper patterns. Check out this page relating AI to compression: the Hutter prize [hutter1.net]

Re:A Slightly More Expensive Method (1)

GuldKalle (1065310) | more than 7 years ago | (#20539353)

It might be the easiest way, but it's somehow lacking. Consider this example:

//This might seem to return a random integer between 0 and 5, but it doesn't really
while (1 == 1)
{
$i++
return mod($i,6)
}

Re:A Slightly More Expensive Method (1)

WombatDeath (681651) | more than 7 years ago | (#20539387)

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:A Slightly More Expensive Method (1)

MillionthMonkey (240664) | more than 7 years ago | (#20539531)

Compress it and measure the compression ratio (entropy). It can be used to determine a probability distribution with confidence intervals so that there is a 90%, 99% etc. probability that the source is truly random.

Re:A Slightly More Expensive Method (1)

spikedvodka (188722) | more than 7 years ago | (#20540381)

Every time some article mentions "Random numbers" the question is raised: What exactly is a random number?

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:A Slightly More Expensive Method (0)

Anonymous Coward | more than 7 years ago | (#20539113)

here [nsftools.com]

Re:A Slightly More Expensive Method (3, Informative)

NetCow (117556) | more than 7 years ago | (#20539127)

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]

Re:A Slightly More Expensive Method (1)

GuldKalle (1065310) | more than 7 years ago | (#20539155)

I think the Mersenne Twister (and others) are only pseudo-random, meaning that you have to find a random number to start it, and then it starts to spew out random numbers (seemingly). If you have the seed and the number of times it ran, you can "predict" the next number. This method, and others (Geiger counters, clocks and mic inputs) are typically used to make the seed-number for a Mersenne Twister.

How it compares to the Mersenne Twister (3, Informative)

benhocking (724439) | more than 7 years ago | (#20539161)

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 (2, Informative)

jgoemat (565882) | more than 7 years ago | (#20541091)

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 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 (3, Funny)

benhocking (724439) | more than 7 years ago | (#20541613)

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

Re:A Slightly More Expensive Method (3, Insightful)

solafide (845228) | more than 7 years ago | (#20539167)

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:A Slightly More Expensive Method (2)

Cyberax (705495) | more than 7 years ago | (#20539879)

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:A Slightly More Expensive Method (1)

DerekLyons (302214) | more than 7 years ago | (#20541277)

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,

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:A Slightly More Expensive Method (2, Informative)

morgan_greywolf (835522) | more than 7 years ago | (#20539191)

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 through the random number generator to get another random number that is used as a seed, etc. ad finitum. Of course, the system clock has only so much granularity, so based on that granularity there are a finite number of seeds for each 24 hour period. If you knew exactly when the random number was generated, you could, in theory, keep trying the corresponding seed and eventually (due to the fact that random number generators aren't truly random) you'd find out what the random number is.

Not good for cryptography relying on random numbers.

So, if you start with a seed that is more or less already random, you get a more truly random number. That's why programs like GPG rely on random keypresses or mouse movements to generate the random number for your key. More entropy means more truly random.

But this relies on user behavior, so if we grab random bits from a chip by recycling the power...bammo! More random!
   

Re:A Slightly More Expensive Method (1)

wizardforce (1005805) | more than 7 years ago | (#20539225)

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?

Yes, there is a method of quantifying randomness:
Rényi entropy
http://en.wikipedia.org/wiki/R%C3%A9nyi_entropy [wikipedia.org]

Re:A Slightly More Expensive Method (1)

DJ Jones (997846) | more than 7 years ago | (#20539275)

As the PDF article notes, this algorithm passes

"basic statistical tests for randomness."

All these tests conclude is that the generated "random" output is evenly distributed in a given range and is not predictable based upon previous output. It doesn't prove that the results are "truly" random. But what is "truly" random? One could argue that even nature is predictable given advanced formulas that we have not derived yet. What's important is that it's not built on a strict mathematical formula like other PRNG's and if used for cryptographic algorthms, is not vulnerable to collision attacks.

It's also readily available. Brilliant.

Re:A Slightly More Expensive Method (2, Interesting)

kevmatic (1133523) | more than 7 years ago | (#20539319)

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 selected out of 1 through 6, but its still just 1. But random number sets are considered random if, for every number, the chances of a the number after it being, say 4, are 1 in 10. So if you have a random set and come across a 1, the probability the next number is 1 is 1 in 10. The same is true for 2, 3, 4 and so in. By measuring the probabilities, you can measure how random your string of numbers is. But just because its random doesn't mean its unpredictable. Random (as per my definition above),yet predictable numbers are pseudorandom. An example is a book of random numbers (which UNIVAC used to publish). Each individual digit might be unpredictable, but if you get a group of say 8 numbers, you can find that group in the book and find the numbers before and after it. Thus, its useless for cryptographic keys. A pseudo random number generator (/dev/urandom) uses math formulas to make pseudorandom numbers. The math can be reproduced, and therefore what it spits out can be predicted. REAL random generators, such as this, are considered 'practically' unpredictable. But I still may be able to influence the probabilities of this by, say, blasting the RAM with a can of freezer and influence its start up state. Doing this doesn't make it completely predictable, but could reduce the possibilities in my brute force attack. This isn't new, either. Video game consoles use this for randomness all the time.

Re:A Slightly More Expensive Method (2, Interesting)

ThosLives (686517) | more than 7 years ago | (#20540153)

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 "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 be based on probability that the next outcome can be predicted based on the previous measurements. I'd say in this case that "completely nonrandom" would be "the next outcome can always be predicted based on previous measurements" and "completely random" would be "zero probability of predicting the next outcome based on previous measurements."

In that sense, it's probably not possible for anything to be either completely random or completely nonrandom, because there is always a finite probability of getting a correct guess, and it's probably impossible to distinguish a guess from looking at previous measurements.




*from dS = dQ/T where S is entropy, Q is energy, and T is temperature (or, better yet, (Boltzmann's constant)*(multiplicity of the system)). I can't remember from Shannon's paper the exact method he used to compute "entropy", but I'm pretty sure it's not "change in energy per unit temperature". Come to think of it, my guess is Shannon's entropy is simply the multiplicity of the system normalized by Boltzmann's constant so the units dissappear (multiplicity doesn't have units). Those crazy non-physical scientists! *grin*

Re:A Slightly More Expensive Method (1)

jpfed (1095443) | more than 7 years ago | (#20541753)

Physical entropy is not the same as information entropy. The use of term "entropy" in information theory is merely inspired by the use of the term "entropy" in physics.

Information entropy is dimensionless- in bits, it is the sum over all events of -P(event)*log_2(P(event)).

Re:A Slightly More Expensive Method (0)

Anonymous Coward | more than 7 years ago | (#20539413)

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

After checking the video I don't believe that it will be a good source. Too much entropy with "I believe" followed by lots of bits in 0 state.

Re:A Slightly More Expensive Method (0, Offtopic)

snowraver1 (1052510) | more than 7 years ago | (#20539493)

Why people are arguing over an article that is written by someone that doesn't know how to capitalize letters and confuses "lose" and "loose" is boyond me.

Re:A Slightly More Expensive Method (-1, Offtopic)

Anonymous Coward | more than 7 years ago | (#20539865)

I imagine there are lots of things that are beyond you. Believe it or not, good grammar has no direct correllation with knowledge of mathematics.

Now, what's beyond me is why anyone should take a grammar nazi seriously when they can't even type "beyond" correctly.

Method to measure randomness (1)

mpapet (761907) | more than 7 years ago | (#20539515)

Dieharder http://www.phy.duke.edu/~rgb/General/dieharder.php [duke.edu] is what I used.

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 (2, Interesting)

Weaselmancer (533834) | more than 7 years ago | (#20539585)

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.

SUBTLE HINT (0)

Anonymous Coward | more than 7 years ago | (#20539953)

DO NOT ACCEPT SCIENCE FICTION AS FACT. THE "SCIENCE" IN SCIENCE FICTION IS A DEVICE TO MAKE THE STORY MORE BELIEVABLE AND INTERESTING.



            [Reply to This ]

Post Comment
Lameness filter encountered. Post aborted!
Reason: Don't use so many caps. It's like YELLING.

Re:SUBTLE HINT (0)

Anonymous Coward | more than 7 years ago | (#20540125)

DO NOT ACCEPT SCIENCE FICTION AS FACT.

Gleick's Chaos is hardly what I would call SF!

Perhaps you were thinking of some other book?

Re:SUBTLE HINT (0)

Anonymous Coward | more than 7 years ago | (#20540199)

It isn't a textbook. It is a popular retelling of the development of chaos theory. It discusses the people behind the theory, not so much the theory itself.

Gleick is not a scientist. He is a science writer. These are the same people who claim a cure for cancer and/or AIDS at every possible chance.

Gleick's work, all of it, is certainly science fiction. Whatever truth he may stumble upon is wholly coincidental and incidental to weaving a story out of the boring stuff of science.

Re:A Slightly More Expensive Method (1)

Algorithmnast (1105517) | more than 7 years ago | (#20539709)

There are standard tests for the uniformity of a distribution, which any CS major encounters at some point in their education. I took courses in the topic in the late 80's, so I apologize for forgetting the names of the tests.

Keep in mind that each random number generator that is purely a software function is actually a pseudo-random sequence with S values. The (S+1)th value is in fact the same as the 1st value, and you've started iterating over the sequence again. That's why we refer to it as a cycle of S values.

One such test is to iterate through with W successive values, tracking how many values in the window are uniform. Then if we slide this window down the sequence, we can see if there are regions of uniformity and non-uniformity. For a window size of W, we divide the range of the RNG info W regions and attempt to show whether or not the generated W values fall more-or-less one value per sub-range.

For instance, if we have a 32-bit RNG function (2^32 values) and we have a window of size 4k(W=2^12), we've divided our overall range into regions that are 2^20 values wide each. We can use both contiguous ranges and equidistant ranges if we have two sets of "result bins", where the first (contiguous) is tracked by the 'div W' value from the rng, and the second (equidistant) is tracked with the 'mod W' value from the rng. So, for example:

T value = some_rng();
C[ value / W ]++;
E[ value % W ]++;

will generate some pseudo-random value, and will then track the value using both contiguous ranges and equidistant ranges. Each has their own strengths and weaknesses, and for best results both should be used.

After filling up the window, we should expect each 'bin' to have a value of 1. If we put 2W values into the bins, we should expect each 'bin' to have a value of 2. The standard deviation indicates how uniform our RNG is. The best ones are quite close to 1. (As it turns out, the digits of Pi are known to be Very Good for a repeatable uniform distribution, but difficult to store in fast-to-generate form.)

As the window is slid across the range of the RNG, the distribution should remain relatively uniform.

Oh - and you can check out the Wikipedia page: http://en.wikipedia.org/wiki/Random_number_generator [wikipedia.org]

Re:A Slightly More Expensive Method (1)

nick13245 (681899) | more than 7 years ago | (#20539871)

Sure, there are metrics to evaluate randomness. One of the most common methods is entropy (http://en.wikipedia.org/wiki/Information_entropy [wikipedia.org] ). It can be use to calculate the "randomness" of data. It works so well that forensics people use it to carve files on hard disk (used to find a continuous stream of non-random data among random data). http://www.korelogic.com/Resources/Presentations/ceic_2007_advanced_file_carving_with_ftimes_final.pdf [korelogic.com]

There are several mathmatical metrics to evaulate randomness. Hell, there is even a FIPS publication (Federal Information Processing Standards) that covers a set of test that are intended to show a data set is random. http://csrc.nist.gov/cryptval/140-1/1401test.pdf [nist.gov]

Re:A Slightly More Expensive Method (0)

Anonymous Coward | more than 7 years ago | (#20540107)

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

A talking realdoll for fans of Bush speeches? WTF?

Re:A Slightly More Expensive Method (1)

mjsottile77 (867906) | more than 7 years ago | (#20540959)

"Also, this may be a stupid question, but I wonder how one measures the 'randomness' of a generator?" There are lots of places that talk about this. A simplistic explanation of what it means to be a good PRNG is simply to provide a sequence of numbers with no correlations that matches the desired distribution. (http://mathworld.wolfram.com/RandomNumber.html [wolfram.com] ). Books on modeling and simulation often have good explanations of this. This page (http://csrc.nist.gov/rng/ [nist.gov] ) has a good overview, including simple descriptions of 16 statistical tests of interest.

What is wrong with the basics? (1)

The_Fire_Horse (552422) | more than 7 years ago | (#20539123)

- number of milliseconds between keypresses
- rate of mouse movement
- number of nanoseconds between a dupe slashdot posting and the time for people to complain about it

Re:What is wrong with the basics? (1)

shystershep (643874) | more than 7 years ago | (#20539289)

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

Oblig. XKCD (5, Funny)

IcedTeaisgood (1148451) | more than 7 years ago | (#20539133)

Re:Oblig. XKCD (1)

Asmor (775910) | more than 7 years ago | (#20541269)

One of my favorites... The alt-text in particular. For the lazy:

RFC 1149.5 specifies 4 as the standard IEEE-vetted random number.

Curious (1)

Bootle (816136) | more than 7 years ago | (#20539175)

I'm curious how a truly random number can ALSO be a fingerprint...

"Your Honor, this alleged rapist has truly random DNA."
"Dat's right, if da seed don't fit, you must acquit!"

Re:Curious (1)

gzerphey (1006177) | more than 7 years ago | (#20539217)

That might be better then the Chewbacca defense.

Re:Curious (1)

imbaczek (690596) | more than 7 years ago | (#20539265)

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

Re:Curious (0)

Anonymous Coward | more than 7 years ago | (#20539313)

I've RTFA

Cheater!

Re:Curious (1)

Goaway (82658) | more than 7 years ago | (#20539293)

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 of hash function.

Re:Curious (1)

blueg3 (192743) | more than 7 years ago | (#20540483)

Here's trivial example of how a "truly random" output can also be a fingerprint. Imagine the random outputs are real numbers. Machine A produces a truly random output, evenly distributed between 0 and 1. Machine B produces a truly random output, evenly distributed between 7 and 10. Both are equally-good random numbers, but given the output, it's easy to tell which machine generated it.

Re:Curious (2, Informative)

Stripe7 (571267) | more than 7 years ago | (#20541085)

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.

Fatal error: not enought random available (1)

Tribbin (565963) | more than 7 years ago | (#20539215)

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

Re:Fatal error: not enought random available (0)

Anonymous Coward | more than 7 years ago | (#20539299)

You haven't been on the internet long have you?

Re:Fatal error: not enought random available (1)

Cryptocrat (1154331) | more than 7 years ago | (#20539379)

Perhaps this was a troll, but yes, in cryptography we frequently worry about the quality of the randomness that goes into our keys. It is especially difficult to get high quality randomness on something as small as a passively powered RFID transponder.

Natural Ice (1, Funny)

0100010001010011 (652467) | more than 7 years ago | (#20539253)

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 (1, Redundant)

Man On Pink Corner (1089867) | more than 7 years ago | (#20539271)

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:This sounds nuts (1)

imbaczek (690596) | more than 7 years ago | (#20539311)

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

Re:This sounds nuts (2)

AmIAnAi (975049) | more than 7 years ago | (#20539445)

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

Re:This sounds nuts (0)

Anonymous Coward | more than 7 years ago | (#20539553)

That's probably why SRAM is in the title of the paper. RTFA.

P(bit) vs. fabrication variations (2, Interesting)

G4from128k (686170) | more than 7 years ago | (#20539281)

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.

Re:P(bit) vs. fabrication variations (1)

Cryptocrat (1154331) | more than 7 years ago | (#20539435)

I agree, a much larger scale study must be done. I think the authors made some attempt to examine chips from the same wafer, and chips from different wafer. In particular I would be interested to contrast the fingerprints from a large sample of chips from the same location on a number of different wafers.

The quality of randomness.... (1, Insightful)

HotNeedleOfInquiry (598897) | more than 7 years ago | (#20539285)

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 and emission of the source is an almost ideal random number generator. It wouldn't take a source any bigger than we now have in a smoke detector.

Re:The quality of randomness.... (1)

flynns (639641) | more than 7 years ago | (#20539497)

For the fifteenth time: SRAM! RTFA.

Oh, right; Slashdot. :\

Re:The quality of randomness.... (1)

BadAnalogyGuy (945258) | more than 7 years ago | (#20539561)

There's only 15 difference between SRAM and DRAM.

4 bits, if you're counting.

I have a better solution (1)

imstanny (722685) | more than 7 years ago | (#20539305)

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 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... (5, Interesting)

nweaver (113078) | more than 7 years ago | (#20539357)

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 (3, Informative)

gillbates (106458) | more than 7 years ago | (#20539421)

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 (5, Interesting)

tlhIngan (30335) | more than 7 years ago | (#20540781)

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 (3, Insightful)

nickovs (115935) | more than 7 years ago | (#20541137)

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] !

Not for PC's - yet (1)

AmIAnAi (975049) | more than 7 years ago | (#20539595)

This technique is only usefull for deeply embedded systems where you have control of the hardware from power-on and are able to fingerprint your SRAM. PCs don't really have user-accessible SRAM (except for on-chip memory in SCSI or Ethernet controllers). Even if this were applicable to DRAM, by the time your OS loads, your DRAM state is already defined. It's a shame Intel's hardware RNG implemented in their firmware hubs (82802Ax) didn't catch on more.

The problem with random numbers (4, Funny)

operagost (62405) | more than 7 years ago | (#20539605)

You can never be sure [random.org] .

A suggestion for this blogger (3, Informative)

Quila (201335) | more than 7 years ago | (#20539615)

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

YOU FAIl IT (-1, Offtopic)

Anonymous Coward | more than 7 years ago | (#20539631)

It atte8pts to PAllid bodies and

Our research group will answer questions soon... (5, Informative)

fubob (7626) | more than 7 years ago | (#20539633)

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

OK, first one, retention time... (1)

nweaver (113078) | more than 7 years ago | (#20539725)

A couple of other posters mentioned the state storing across power cycles. Being too lazy to read the paper in enough detail to create a slashdot question:

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?

Don't follow the hype. Does not apply to PC's. (5, Interesting)

rpp3po (641313) | more than 7 years ago | (#20539883)

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.

Fascinating idea, but not always cheep (1)

nickovs (115935) | more than 7 years ago | (#20539971)

It's an interesting paper, and as a means of getting randomness for RFID processors it probably works well, but I'm not sure it's that cheap for most purposes. If you're having to build a new circuit to generate randomness then using an op-amp to compare the noise out of a pair of zener diodes is likely to be cheaper. If you already have an audio input you're not using you can keep that really cheap. Of course if you want really good randomness you should use an old smoke detector [slashdot.org] .

"Random" Help me out here (0)

Anonymous Coward | more than 7 years ago | (#20540257)

"Random" == can't predict? Can't predict because we don't understand behind-the-scene how/why. So all things are random until we understand adequately how. Equally, nothing is random, since randomness is not inhererent to the object itself, but subject to our level of knowledge.

Ok, tear the above apart and enlighten me (perhaps others). I've never encountered more rigorous definition of randomness in any math/stat courses.

a half step above myspace (0)

Anonymous Coward | more than 7 years ago | (#20540317)

Nice livejournal page.

Livejournal. Ha.

Easy (1)

PPH (736903) | more than 7 years ago | (#20540389)

Post a question on 'Ask Slashdot'.

and another few ways (1)

pakar (813627) | more than 7 years ago | (#20540619)

If not implemented in hardware i do see some problems like how to get access to the page as a normal user.. In software there are easier ways...

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 harddrives
7. do some quick benchmark on the RAM and use the latency and/or bandwidth
8. do some quick benchmark on the disk of some semi-random blocks and use the latency and/or bandwidth
9. do some benchmark on the gfx-card and use the latency or bandwidth
10. Free ram / used ram / current usage of the buffer-cache
11. Check free or used diskspace on the filesystems.
12. Got a analog tv/radio-card? Tune to a semi-random frequency read some noise..
13. read some static noise from the mic-input (with or without having a mic plugged in, usually you get some noise if you have a 'bad' soundcard)
14. ping a few semi-random addresses on the network and use the latency.

Use one or more depending on how 'random' you wanna get and use something like this:
seed(step 1 + rand())
seed(step 2 + rand())
seed(step 3 + rand())
seed(step 4 + rand())
X = rand()
and then use X as you final seed value...

Or maybe just use the number of hits per second you get when being \.'ed :)

No randomness (1)

herbivore (1154497) | more than 7 years ago | (#20541109)

There is no such thing as random, only patterns too complex to model.

How does this compare to what linux already does? (1)

merreborn (853723) | more than 7 years ago | (#20541255)

Linux already uses hardware entropy sources like hard drive seek times and peripheral input to generate secure random numbers:

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 better than what we already have.

It's all (1)

benow (671946) | more than 7 years ago | (#20541293)

butterflies and artichokes to me.
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?