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.

Comments

933245789124398

[LiquidCoooled]

234 234838372 234 29723432891023478343589435892?

Re:933245789124398

[BadAnalogyGuy]

23423483837223429723432891023478343589435892

You would expect that, you fucking pervert.

Re:933245789124398

[Debug0x2a]

Hey, I'm a 23423483837223429723432891023478343589435892 you insensitive clod!

Re:933245789124398

[BlueTrin]

Can someone explain this to me ?

Re:933245789124398

[Anonymous Coward]

You have to rot13 the comment to get the joke. Twice.

Re:933245789124398

[mwvdlee]

Yes, I can explain this to you.

A Slightly More Expensive Method

[eldavojohn]

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?

Re:A Slightly More Expensive Method

[name*censored*]

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

[Anonymous Coward]

here

Re:A Slightly More Expensive Method

[NetCow]

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

Re:A Slightly More Expensive Method

[GuldKalle]

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.

Re:A Slightly More Expensive Method

[solafide]

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

[sholden]

You can do some stats on the output, for example: http://citeseer.ist.psu.edu/maurer92universal.html

Re:A Slightly More Expensive Method

[morgan_greywolf]

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

[wizardforce]

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

Re:A Slightly More Expensive Method

[Anonymous Coward]

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

[DJ Jones]

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

[stranger_to_himself]

123456789123456789123456789123456789123456789

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

Re:A Slightly More Expensive Method

[Matje]

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

[kevmatic]

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

[GuldKalle]

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

[WombatDeath]

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

[Anonymous Coward]

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

[snowraver1]

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

[MillionthMonkey]

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

[Algorithmnast]

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

Re:A Slightly More Expensive Method

[nick13245]

Sure, there are metrics to evaluate randomness. One of the most common methods is entropy (http://en.wikipedia.org/wiki/Information_entropy). 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

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

Re:A Slightly More Expensive Method

[Cyberax]

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

[Anonymous Coward]

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

[ThosLives]

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

[Anonymous Coward]

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

Re:A Slightly More Expensive Method

[spikedvodka]

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

[mjsottile77]

"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). Books on modeling and simulation often have good explanations of this. This page (http://csrc.nist.gov/rng/) has a good overview, including simple descriptions of 16 statistical tests of interest.

Re:A Slightly More Expensive Method

[DerekLyons]

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

[jpfed]

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

[Surt]

The problem everyone has with that definition is that it's unmeasurable, because we don't know how to generate the shortest program for a given sequence.

Re:A Slightly More Expensive Method

[shadow_slicer]

Of course, that's physical entropy, and I don't know that it's the same as "information entropy."

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 goes to infinity, whereas the continuous integral is always finite). They are called the same since when information theory was first introduced (in Claude Shannon's 1948 paper -- which I might suggest you read [also his 1949 paper on cryptography is good too.]).

Of course there is also entropy in Statistical Mechanics (which starts from classical and quantum mechanical principles under a microscopic scale and uses statistical methods to examine what effects these have on a macroscopic scale [in essence explaining classical thermodynamics]). And this entropy is based on the total number of possible microstates a system can have (and since states in quantum mechanics is discrete this is finite), this definition of entropy is compatible with the information theoretical definition of entropy (but whether they are actually the same has not been proven).

In Information Theory entropy is usually measured in bits (minimum expected compressed size of an observation in binary digits) or nats (minimum expected compressed size of an observation in base e digits).

A truly random number would be a number that has no statistical correlation with any other observable quantity (past or future). I'm not sure it is possible to generate a truly random number since any physical method would create the potential for other data to be observed. Of course given the correlations and all possible observation the correlations could be removed, but this will never be practical. Additionally all that is really needed for cryptographic purposes is that the number have no statistical correlations with any quantity observed by any receiver, which is much simpler (and arguably what this article is about).

Re:A Slightly More Expensive Method

[Fweeky]

From the Wikipedia article:

Observing a sufficient number of iterates (624 in the case of MT19937) allows one to predict all future iterates A proper cryptographically secure PRNG like Yarrow shouldn't be guessable like this, and neither should this RNG, though they may not be "more effecient and faster", just "better".

Re:A Slightly More Expensive Method

[Anonymous Coward]

The unit of information entropy is the bit.

Re:A Slightly More Expensive Method

[JesseL]

If it's truly random, there is a very real possibility that the stream will be very compressible. You could even end up randomly generating the complete works of Shakespeare.

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

[JesseL]

To illustrate:
A random number generator would have an equal probability of generating any of these strings of bits,
011010011010
000000000000
111111111111
010101010101
101010101010

Re:A Slightly More Expensive Method

[sdedeo]

Entropy is fascinating. It's proportional to the logarithm of the number of microstates, but until the advent of quantum mechanics, there was not good way to number the microstates of a given physical system. Once you have the uncertainty principle, you can divide the phase space up into little chunks of volume (Planck's constant)^(dimensions) and count it that way.

Another way to put it is that before the advent of quantum mechanics, every measurement of entropy was only meaningful in a relative, differential sense. S is arbitrary up to a constant. You can see that from the definition you use, which when you integrate is ambiguous up to a constant.

Re:A Slightly More Expensive Method

[Anonymous Coward]

Thanks for pointing out the gem that is that video :)

Re:A Slightly More Expensive Method

[MCraigW]

And it is language dependent.

Re:A Slightly More Expensive Method

[Surt]

An excellent point. On reflecting on this comment, I realized it would be relatively trivial to design a language for which the shortest program expressing any given sequence was a single character.

Re:A Slightly More Expensive Method

[kryptkpr]

I think you're mixing up "Random" and "Fair". Something can still be random without being fair (casino slot machines come to mind, they have to be made unfair or they wouldn't be profitable but they have to be random to be legal).

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 less space then the actual sequence. All occurences of the sequence are then replaced by the symbol. Since any 12-bit sequence (continuing your example) is just as likely to occur as any other, you would need to assign symbols for all 2^12 possibilities, which gets you right back to where you started since the symbol is no shorter then the sequence.

Now, the output of an unfair or not trully random RNG (which is biased towards a particular output, lets say 1) would indeed compress. Lets say the output of this unfair RNG is a 1 90% of the time, and a 0 for 10% of the time. You can easily compress this stream by converting it into another stream which represents the number of ones in between successive zeros. This kind of compression is only possible because the RNG isn't fair (it's output can be predicted ahead of time to almost always be a 1), and doesn't work when the distribution of 0 and 1 is even.

Re:A Slightly More Expensive Method

[ChatHuant]

A random number generator would have an equal probability of generating any of these strings of bits,
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 ascertain. Knuth has an interesting discussion on generating random numbers (I believe in Vol II)

Re:A Slightly More Expensive Method

[Intron]

int random()
    i++;

Every value of i is equally represented. Must be a perfect random number generator.

Re:A Slightly More Expensive Method

[E 99]

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?

The unit of randomness is the bit of entropy. If you accumulate eight bits of entropy (or more) into an eight-bit register, you have a truly uniformly random eight-bit number. There are various ways of measuring or calculating entropy. I'm more familiar with the ways of directly measuring "randomness." There are math software packages available that will analyze a large series of numbers in with many different statistical algorithms to detect any types of patterns. Generally, if a randomness generator (or PRNG) gives good results for all the tests in the batch, you can be confident that it's close to completely patternless (although no PRNG is completely patternless, as they're all periodic). So in the 8-bit example, the way I would know how to measure 8 bits of entropy is to increase the amount of entropy stored in the register until a block of them (the software I'm familiar with requires at least an 8MB block) passes all the statistical tests.

Re:A Slightly More Expensive Method

[Anonymous Coward]

The most common unit of Shannon entropy is the "bit" (or binary unit) if the logarithm is to base 2. Using log base e (or natural logarithm) the unit is the "nat".

The predictability idea, incidentally, is valid, and the entropy rate of a "random" sequence can be related to its predictability from past outcomes. The details can be found in many books on information theory.

Re:A Slightly More Expensive Method

[maxwell demon]

Would you consider the digit sequence of pi to be a random sequence? AFAIK up to now it has passed every normality test thrown to it. Yet I'm not willing to consider that sequence as random. After all, you can calculate any digit you want (it may take some time and computing power, though). So there's absolutely nothing unpredictable about them.

Re:A Slightly More Expensive Method

[Anonymous Coward]

True, but it is interesting to note that in general you can only improve by an additive constant when switching from one language to another. The reason is that given the shortest program for printing x in one language say lisp we can construct another program in c++ for example by simply writing a lisp interpreter in c++ and appending the original lisp program. Since the lisp interpreter is a fixed length, the length of the new (c++) program will be less than or equal to the length of the lisp program plus an additive costant approximately equal to twice the length of the lisp interpreter written in c++.

Re:A Slightly More Expensive Method

[spikedvodka]

notice I didn't say shortest program. I said shortest algorithm

algorithms can be expressed as programs, but do not have to be. A formula is an example of an algorithm. I could also have written my algorithm as:
N(n) = n mod 10, n>=0
and it would have been equally accurate. It's shorter this way too.

Re:A Slightly More Expensive Method

[Surt]

Algorithm actually has the same issue. Note that you said:
N(n) = n mod 10, n>=0

What's n? What's mod? What's greater than?
All of that requires the backing of a language. And lest you call for the language of mathematics, that's the language with the single largest definition in existence.

In my custom language, I can express the same algorithm as:

Q

Pick any other sequence, and I'll express it as a single character too. It's a very poor definition of the problem.

Random karma whore

[BadAnalogyGuy]

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!

Re:Random karma whore

[Mc1brew]

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

[egyptiankarim]

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:Random karma whore

[abes]

It really depends on whether you are looking from Einstein's world view (God doesn't play dice) or Quantum mechanics world view, in which everything is assigned a probability (and therefore random). IANQM, but my understanding is that the interesting thing is how to scale the very small to the very big -- things which by their nature are ruled almost entirely to probability (particles) to things which have no randomness attached to them (>> particles).

You could in theory construct a truly random number generator based on some property of a particle. I think this has been done already, but for reasons unknown to me (either building the detectors is expensive, or there isn't a large demand for it), you can't get these things commericially. It might be a decent DYI project.

However, the truth of it is, for most things you don't actually need truly random numbers. Another way to look at random, is how much information does an outside observer have? Suppose I have a string of digits which are stored on my computer and I give them out. To someone who didn't previously have access to those digits, then it would most likely appear that they are random. The person receiving the digits might even might plot the numbers and see if they fit a particular distribution. However, even if they (for example) fit a Guassian distribution, doesn't guarantee they are truly random. Only they appear that way.

For getting a good compromise for getting psuedo-random numbers, some people have sample physical phenomena. For example, because of issues related to Chaos theory, taking local temperature readings might provide a good stream of numbers that are difficult for someone not in your immediate vicinity to know (provided you subtract of general trends like the mean 'global' temperature). Such detectors are cheap to produce and can provide large streams of data relatively fast. I want to make one of these for a while, as I run large simulations that require a lot of random numbers. As it turns out, a large part of the simulation time comes from generating those random numbers.

Re:Random karma whore

[Surt]

Indeed, there is very little to possibly zero actual randomness in the universe. Many scientists think there may be no actual randomness (just stuff for which we don't know how to examine the internal state yet).

Re:Random karma whore

[cowscows]

That's basically the deterministic view of the universe, where given all the rules and the initial state of the universe, you'd theoretically be able to run a simulation and predict the entire future of the whole universe (of course, to simulate the entire universe, you'd need a computer the size of the universe).

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 deterministic. At the scale of things like elementary particles, you just plain cannot predict where some things are going to be at a given point in time. Hence we have Heisenberg's uncertainty principle. It's not an intuitive or easy concept, but one way of describing it is that some of those tiny particles don't actually have a location until they need to.

Re:Random karma whore

[Anonymous Coward]

Well, there's an obvious solution... make a random selection of which variables will be used for any given generation :D

Re:Random karma whore

[Surt]

Indeed, and the open question is whether quantum mechanics is the bottom, and there is no more we can know that would allow us to predict quantum mechanical outcomes, or if at some deeper level, it all becomes fixed again.

Re:Random karma whore

[Anonymous Coward]

If that's the case, _nothing_ is truly random, ever. Assuming you have omniscience, you would get pretty bored knowing precisely what would happen at all times at a quantum level and up.

Re:Random karma whore

[JoelKatz]

Something can be both random on a micro scale and predictable on a macro scale. The weather is like millions of dice being rolled. You can't say much about each individual die, but you can say an awful lot about the million in aggregate.

This technique is similar. The power on patterns of memory bits display both randomness and predictability. You can either mine the randomness, and get a source of truly random numbers, or you can mine the predictability, and get a fingerprint.

An interesting question is precisely on what the random outputs depend. If it's quantum effects in the individual electrons as the power comes on, then it should be truly random.

Re:Random karma whore

[imgod2u]

See http://en.wikipedia.org/wiki/Hardware_random_number_generator

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 variations in electron leakage (due to quantum effects, since an electron's wave function becomes larger than the dielectric material's thickness (hafnium-based in 45nm I think, silicon-dioxide in 65nm and above) can make the difference between a logical 1 and 0.
2. Process variations. As each chip is "grown", the process generally (and this area is definitely outside of my knowledge) involves highly charged plasmas to etch the material at each layer. Again, the wave function of these charged particles (or their specific charge depending on the wave function of the electrons in their out layers), will cause differences in the thickness/shape/size of the subsequent footprint. This essentially means that each individual chip made has a slightly different, and random, "pattern" associated with it.

Re:Random karma whore

[X0563511]

http://en.wikipedia.org/wiki/Chaos_theory

Re:Random karma whore

[marcosdumay]

"That link brought me to the conclusion that randomness doesn't exist as much as I thought."

There is a lot of randomness at quantum mechanics. Of course, we can't be sure it is really random, but everybody that tried a non-random explanation of it so far failed.

Oblig. XKCD

[IcedTeaisgood]

http://xkcd.com/221/

Re:Oblig. XKCD

[KJE]

Oblig Dilbert: http://www.random.org/analysis/dilbert.jpg

Re:Oblig. XKCD

[Asmor]

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

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

Re:Oblig. XKCD

[ricky-road-flats]

Just wanted to say thanks - never heard of xkcd before, but am enoying it a lot!

How it compares to the Mersenne Twister

[benhocking]

The Mersenne Twister is a pseudo-random number generator. For many uses, this is preferable to a true random number generator as it is easily repeatable. (One can also repeat the results of a true random number generator by storing the output, but depending on how many random numbers you're generating, this might be space intensive.)

That said, although this might be "true" randomness, what kind of randomness it is? Uniform over a range? Gaussian? Weibull? Most likely, none of the above if it can be used for fingerprinting systems. (No, I did not RTFA.)

Re:How it compares to the Mersenne Twister

[E 99]

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

Though I also did not RTFA, all such random sources are a combination of pattern and randomness. The way you would presumably use it for both is to either A) extract the randomness from the raw memory bits, or B) identify the patterns of the non-randomness in the raw memory bits.

The former is very easy to do mathematically. The latter depends on what kind of pattern you have to look for.

Curious

[Bootle]

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

[gzerphey]

That might be better then the Chewbacca defense.

Re:Curious

[imbaczek]

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

Re:Curious

[Goaway]

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

[Anonymous Coward]

I've RTFA

Cheater!

Re:Curious

[blueg3]

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

[Stripe7]

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.

Re:Curious

[Anonymous Coward]

I'm curious how you could comment on the article without actually reading it. Because if you did, you would know that your question is invalid, and you would also know that they don't use the randomness to fingerprint.

Fatal error: not enought random available

[Tribbin]

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

[Anonymous Coward]

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

Re:Fatal error: not enought random available

[Cryptocrat]

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

[0100010001010011]

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

[Man On Pink Corner]

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

[imbaczek]

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

Re:This sounds nuts

[AmIAnAi]

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

[Anonymous Coward]

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

Re:This sounds nuts

[imgod2u]

That actually depends on how long you power it off for....

Also depends on how the sense/charge refresh circuit is designed.

P(bit) vs. fabrication variations

[G4from128k]

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

[Cryptocrat]

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.

Re:P(bit) vs. fabrication variations

[Anonymous Coward]

This is a very interesting phenomenon, but a lot more data is needed to show that it provides consistent behavior.

More like inconsistent behavior.

Re:P(bit) vs. fabrication variations

[dan e holcomb]

You are correct to suspect that the temperature has an effect on the fingerprints, but not by increasing the probability of a 1 as you suggest. Instead, temperature impacts how random the SRAM fingerprint is. In fact, the two states of an SRAM (1 and 0) are symmetric, so there is no reason that changing temperature should favor one state over the other.

Experiments performed since we published this paper have in fact confirmed that the amount of randomness (measured in terms of min-entropy) increases with higher temperatures (and decreases with lower temps), due to the fact that thermal noise (the source of randomness) is temperature dependent. This temperature dependence is used to support our claim that the source of the randomness is physically random thermal noise (and thus TRUEly random).

-dan

Re:P(bit) vs. fabrication variations

[imgod2u]

That actually depends on your process. Not all logic is symmetrical. In fact, I would venture to say none of them are. A p-mos and an n-mos in standard CMOS are built differently. I believe you start out with a lightly doped p substrate and implant N-wells to construct an n-mos. A p-mos starts out the same with a p substrate but is then implanted with a large N-well, then subsequent p-wells inside the n-well.

Wiki has a good article on mosfets:

http://en.wikipedia.org/wiki/Field_effect_transistor

Because of things like the body effect, substrate bias, and just plain differences in p and n doping methods, I wouldn't expect both types of transistors to have the exact same behavior scaling (or even Vt/vd/vs points to start with) with temperature.

This is why CMOS designs should generally allow for differences in behavior and try to prevent latch-ups.

Re:P(bit) vs. fabrication variations

[imgod2u]

The point isn't that they are patternless. They certainly might, if approximated, have some pattern. For instance, if, given the long run, there is a 60/40 distribution between RAM bits with 1's and 0's respectively. But as long as there's some kind of local randomness, the numbers can be "massaged" to produce truly random numbers. Let's say that, if you only restricted yourself to picking 10 bits instead of the some-odd-billions you would need to get to 60/40 consistently. If the physical process means that there is no deterministic way to determine where on the billions-of-bits-wide distribution curve you picked that 10 (as there isn't when you power up a chip), then you have a truly random 10 bits. The beauty of randomness is that only the tiniest amount has to exist to make the whole thing random by nature.

Re:P(bit) vs. fabrication variations

[dan e holcomb]

I am aware of the difference between a PMOS and an NMOS device.

The symmetry that I refer to is not meant to imply that the NMOS and PMOS are symmetric, but instead meant to imply that the two cross-coupled inverters that make up each SRAM cell are the same. When power is applied to the cell, these two identical inverters fight against each other until stabilizing in either a 1-0 or 0-1 configuration.

I was contrasting this behavior against DRAM. In DRAM there is no fighting between such identical devices. Thus in DRAM, some influence (ie a temperature change) could cause all of the cells to change in the same way. In SRAM, such a change would have a similar common-mode impact on each of the two cross coupled inverters that make up each cell, and would thus be less likely to impact the initial state.

The quality of randomness....

[HotNeedleOfInquiry]

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

[flynns]

For the fifteenth time: SRAM! RTFA.

Oh, right; Slashdot. :\

Re:The quality of randomness....

[BadAnalogyGuy]

There's only 15 difference between SRAM and DRAM.

4 bits, if you're counting.

Re:The quality of randomness....

[Anonymous Coward]

BAH! TOURING!? You call yourself a geek? The dude's name was TURING. Don't forget again or we will revoke your geek license.

Re:What is wrong with the basics?

[shystershep]

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

I have a better solution

[imstanny]

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

Re:I have a better solution

[mr_mischief]

Nah. All you proved is that career politicians are devoid of information, and you can't transmit the static they produce in any meaningful way.

A VERY interesting idea...

[nweaver]

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.

Re:A VERY interesting idea...

[Dirtside]

Kevin Fu has some SMART grad students.

I wonder how often they go around saying to people, "Whoa. I know Kevin Fu."

This is hardly random

[gillbates]

As an embedded engineer, I've encountered numerous cases where power cycling RAM did not alter the contents.

In fact, I've seen systems boot and run even after the power was cut for several seconds. Some types of SRAM and SDRAM have the ability to retain an (imperfect) memory image even at very low voltage levels. Sure, it's not guaranteed to be accurate by the manufacturer, but RAM "images" are a pretty well known phenomenon. In some cases, the contents of memory can be reconstructed even after the computer has been powered off and removed to a forensic laboratory.

This is not random at all. In fact, it's more likely to produce an easily exploitable RNG than anything else; I would not be at all surprised if the standard UNIX random number generator provided better security.

Re:This is hardly random

[tlhIngan]

As an embedded engineer, I've encountered numerous cases where power cycling RAM did not alter the contents.

In fact, I've seen systems boot and run even after the power was cut for several seconds. Some types of SRAM and SDRAM have the ability to retain an (imperfect) memory image even at very low voltage levels. Sure, it's not guaranteed to be accurate by the manufacturer, but RAM "images" are a pretty well known phenomenon. In some cases, the contents of memory can be reconstructed even after the computer has been powered off and removed to a forensic laboratory.

This is not random at all. In fact, it's more likely to produce an easily exploitable RNG than anything else; I would not be at all surprised if the standard UNIX random number generator provided better security.

I've had this bite me, and exploited it.

It bit me when booting into Windows CE - you'd power cycle the thing, and the OS would boot with the old RAM disk you had - we'd gotten to the point where we'd have the bootloader wipe the kernel memory so the data structures were all corrupted by the time the OS was trying to decide between mounting the RAM disk (object store) and starting fresh. It turns out that the longer an image is unchanged in RAM, the more likely the cells woudl be biased such that if you cycle the power on them, they're more likely to lean towards the way they were before power was cut.

The time I exploited it, I didn't have any way of logging. Logging to serial port caused issues (timing-sensitive code), so I logged to memory (and no, I had no filesystem running, so I couldn't log to file). My trick was to simply log to a circular RAM buffer. When it crashed, I would just power cycle and dump the RAM buffer. Even though the data was fresh, it was enough to make out what my debug message was trying to say (almost always perfect). This was readable after a brief power cycle, and was still readable after turning power off for nearly a minute. The characters got corrupted, but since it was regular ASCII, you could still make out the words.

Re:This is hardly random

[nickovs]

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. 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()!

Re:This is hardly random

[dan e holcomb]

As you suggest, it has been shown that state can be burned into SRAM (ie by Ross Anderson @ Cambridge). However, other work has shown that this is only a problem with older SRAM. Modern SRAM typically loses state within a second (ie by Skorobogatov @ Cambridge), although there is some temperature dependence to this.

In our experiments, the only longer term correlation seen was an anti-correlation between a given SRAM state and the SRAM state at the next initialization, due apparently to NBTI.

You are correct that SRAM can hold state through low voltages, our method requires a complete power down between successive fingerprints. SDRAM is a whole different story. Our methods apply only to SRAM, because SRAM has two symmetric states which compete at startup, leading to the fingerprint.

Re:This is hardly random

[Twylite]

Someone who knows what they are talking about :)

There are far more efficient (and cheap) ways to extract thermal noise from a circuit, and SRAM in particular decays slowly (which is why you have to actively erase it if you are developing FIPS-compliant secure hardware). The technique described on the blog sounds suspicious and too likely to be predictable - statistically figure out which bits are likely to change on a power cycle, then use those bits as your RNG. Hmm!

Seriously, if you are after a RNG for a real security application then you're looking at something that conforms to some sort of security specification, like FIPS 140. FIPS doesn't allow RNGs because even statistical testing can't guarantee their randomness, so you always use an RNG as entropy to seed a PRNG and use the output of the PRNG as your random stream.

Re:Four

[ShieldW0lf]

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?

Method to measure randomness

[mpapet]

Dieharder http://www.phy.duke.edu/~rgb/General/dieharder.php 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

[Weaselmancer]

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.

Not for PC's - yet

[AmIAnAi]

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.

Re:Not for PC's - yet

[imgod2u]

Processor cache....

You're right that we'd need a _rand instruction though as the current x86 model doesn't (erm, isn't supposed to) allow raw access to processor cache.

Re:Not for PC's - yet

[AmIAnAi]

Processor cache....
True. But most, if not all, of the cache lines will have been written to by the time the OS starts to boot. It is not uncommon for the BIOS to have the cache policy set to write-through during memory zeroing - then every cache line will get hit. You would need to know what area of the cache had not been touched by the BIOS (or by CPU self test).

The problem with random numbers

[operagost]

You can never be sure.

A suggestion for this blogger

[Quila]

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

Re:A suggestion for this blogger

[Anonymous Coward]

why should he do that? its a waste of a keystroke.

Our research group will answer questions soon...

[fubob]

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

Re:Four

[ukatoton]

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

[Anonymous Coward]

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.

OK, first one, retention time...

[nweaver]

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?

Re:OK, first one, retention time...

[dan e holcomb]

Data retention is a potential issue if the chip is not powered down for a sufficient period of time. In our work, data retention was not found to be a significant problem (ie no data remanence after cycling power off for half a second). We need to think about how to prevent/detect this at the system level.

SRAM retention can last a few seconds, as shown in "Low temperature data remanence in static RAM" by Skorobogatov at Cambridge.

However, we did see an interesting related phenomenon across a longer duration. If we store all 0s into an SRAM for a long time, and then turn off for ~20 seconds and turn back on, we see that the initial state contains more 1's than usual. This indicates a second type of remanence (likely caused by NBTI), showing as an anti-correlation.

DRAM should not work for our method, because the fingerprint in SRAM is due to the circuit symmetry of SRAM. Each of the states (0 and 1) is physically identical. The same is not true for DRAM.

Don't follow the hype. Does not apply to PC's.

[rpp3po]

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.

Re:Don't follow the hype. Does not apply to PC's.

[bcrowell]

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

1. Users don't want to power-cycle their machines several times, and modify their BIOSes, so that they can install someone's crypto software.
2. The code to use this technique would either work or not work for various users at various times in the future, depending on what types of memory were being used at those times.
3. Part of purpose of the technique is to fingerprint your machine, but on a general-purpose PC (as opposed to an RFID chip), people often upgrade their memory, in which case all your fingerprints would change.

Re:Don't follow the hype. Does not apply to PC's.

[maxwell demon]

Slashdot stories get worse by the day.

That's why I read Slashdot only at night.

Re:Don't follow the hype. Does not apply to PC's.

[Cryptocrat]

I disagree, it applies to some PCs: It is not unusual for TCMs to contain some SRAM. It is precisely in that context that these sorts of techniques are the most useful.

Re:Four

[Baron Eekman]

You can at least cite properly:

http://xkcd.com/221/

SUBTLE HINT

[Anonymous Coward]

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

[Anonymous Coward]

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

[Anonymous Coward]

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.

Fascinating idea, but not always cheep

[nickovs]

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.

Re:Four

[ShieldW0lf]

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.

"Random" Help me out here

[Anonymous Coward]

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

Re:"Random" Help me out here

[JoelKatz]

While anything random can't be predicted to the extent that it's random, and all things seem random until we can predict them, some things are fundamentally random and will never be predictable.

For example, consider a single atom of a radioactive isotope with a half-life of 12 hours. Whether or not that atom will decay in the next 12 hours (assuming it is not molested) is truly random. It doesn't depend on anything else. It is, we believe, fundamentally unpredictable.

The same is true of an electron that might tunnel. As far as we know, nothing external or internal effects its behavior. It simply might or might not tunnel.

Note that random events might be predictable in mass. If you have 12 kilos of that radioactive substance, after 12 hours you will have pretty darn close to 6 kilos left. However, they can also be unpredictable in mass, google "Scroedinger's cat".

Re:"Random" Help me out here

[Anonymous Coward]

While anything random can't be predicted to the extent that it's random, and all things seem random until we can predict them, some things are fundamentally random and will never be predictable.

For example, consider a single atom of a radioactive isotope with a half-life of 12 hours. Whether or not that atom will decay in the next 12 hours (assuming it is not molested) is truly random. It doesn't depend on anything else. It is, we believe, fundamentally unpredictable.

This still seems a circular self-referential description/definition, and provides no objective distinction between (subjective) unpredictability and (objective) randomness.

In the example of a single atom decaying, since we cannot rule out the possibility, one day, of being able to predict decay rate, I don't see how we can assert that the process is inherently random in some objective sense. Saying it's random is equivalent to saying we don't know...

Re:"Random" Help me out here

[JoelKatz]

"In the example of a single atom decaying, since we cannot rule out the possibility, one day, of being able to predict decay rate, I don't see how we can assert that the process is inherently random in some objective sense. Saying it's random is equivalent to saying we don't know..."

No, saying it's random is *not* equivalent to saying we don't know. Saying it's random is equivalent to saying that we *cannot* know.

There are situations where "not knowing" and "it being impossible to know" have differences with testable consequences. See, for example, Bell's Inequality.

Not only can we not predict whether or not a particular atom can decay, we have good reasons to believe that we will never be able to predict atomic decay because it is random. You can hypothesize that we are wrong about this, of course, but you can respond to *any* scientific conclusion by saying "perhaps it's wrong".

Re:"Random" Help me out here

[Anonymous Coward]

No, saying it's random is *not* equivalent to saying we don't know. Saying it's random is equivalent to saying that we *cannot* know.

There are situations where "not knowing" and "it being impossible to know" have differences with testable consequences. See, for example, Bell's Inequality.

Thanks - that's a good distinction. I had a feeling that it'd lead to Heisenberg somehow. I'm reminded of Einstein's discomfort with randomness/hidden variables now.

Re:"Random" Help me out here

[JoelKatz]

Unfortunately, Einstein didn't quite live long enough to respond to Bell's Inequality. I wonder whether he would have accepted that, yes, it seems God does play dice with the universe. He could also have chosen to reject locality, which leads to the kind of strange conclusion that everything is predictable, but could depend on something that happened on Alpha Centauri a millisecond ago.

a half step above myspace

[Anonymous Coward]

Nice livejournal page.

Livejournal. Ha.

Easy

[PPH]

Post a question on 'Ask Slashdot'.

Kolmogorov complexity not tractable - compression?

[tucuxi]

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

Re:Four

[Daimanta]

Compiler error! return 4 does not terminate

and another few ways

[pakar]

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

Re:Four

[edwdig]

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.

Fingerprinting

[jgoemat]

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

[benhocking]

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

No randomness

[herbivore]

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

Re:No randomness

[Anonymous Coward]

Yeah, about that. You should really look into quantum physics before you say something so thoroughly and completely wrong again.

How does this compare to what linux already does?

[merreborn]

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

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

[benow]

butterflies and artichokes to me.

MOD PARENT DOWN!

[Asmor]

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

Re:Four

[psmears]

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

Nice job

[p3d0]

Score 4, Interesting without even reading or understanding the article. The Mersenne twister is a pseudorandom number generator, which is totally unrelated.

It's Been Tried Before

[Anonymous Coward]

I worked for a company (NE2 Encryption) that tried to do this back in 2001. I recall that their end results were that they could fingerprint a pc about 70% of the time - not good enough for commercial use, and definitely not random enough to call it a pseudo-random number generator. It also took a long time to generate the unique key, ie the computer had to be running the software in the background for about four hours. Needless to say, the technology never went anywhere. I think they did try to take out a patent on it, which may still exist, but the copmany is no longer in business.

Then I have the solution for you!

[p3d0]

RTFA.

Another approach

[Tablizer]

I'm patenting a random number generator that involves the use of toddlers. They make a random mess around the house, so we might as well harnass this random energy.

Random Number

[kEnder242]

http://xkcd.com/221/

HotBits

[The -e**(i*pi)]

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/

Re:HotBits

[JoelKatz]

There are quite a few ways of generating truly random numbers. They all basically boil down to three basic mechanisms. One is radioactive decay. Another is thermal noise. The last is direct quantum effects.

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 the cheapest if you're going to build hardware to produce it. In a traditional computer such as the one on your desk, there are often several usable sources of true randomness.

Thermal noise in the lowest bits of your sound card work fairly well. You simple digitize the unconnected audio input.

Another good source is microscopic zone temperature variations in two independent crystal oscillators. You can usually find this by grabbing the TSC (instruction cycle counter) when a packet is received. Your network card has a crystal oscillator that is independent of the oscillator that generates your processor's core clock. (Obviously, only the lowest bits are useful.)

Re:HotBits

[Anonymous Coward]

Technically, radioactive decay is a consequence of quantum mechanics.

Re:HotBits

[JoelKatz]

Yes. So is thermal and shot noise. I believe all known sources of true randomness ultimately reduce to quantum uncertainty.

Iffy. H/W != "true" randomness

[mattr]

Just because it is hardware does not mean it is "true" randomness.
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 same jitter on another machine after you take away the fingerprint. Not a new idea of dialing in how much randomness you want but they will have to prove it.

Re:Four

[ajs]

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.

Re:Four

[leuk_he]

right....

Just i forgot the link, and the actual number, which by a random luck i choose the same....

Old news - I have already been granted patents

[ironring]

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

Hrm

[Anonymous Coward]

So again I'll explain the cheapest method of true randomness: a transistor run "backwards" to produce plain analog white noise, a sample-and-hold circuit to capture the voltage output of the transistor, and an A/D converter to get this voltage to digital form. It's not new or revolutionary (though I am certain some bstrd will eventually re-invent it, claim fame, and call it "new technology"), it's not complex, but it works, it is true random, it costs nothing, and - lo and behold - I've found that it has been used many a times before to create random number generator devices for computers.

I too came up with the idea myself many years ago as a way of achieving a step-less, frequency-tunable noise generator for an analog synthesizer project of mine.

- JRL

I've observed this behavior in SRAM...

[The Master Control P]

I've assembled a small SRAM memory circuit as part of a computer and I've observed at least part of the behaviors he describes. In the circuit, both my address counters always initialize to zero. The first byte of the ram chip is always 11111111, the second always 00000000, and after that they are apparently random. But if you're going to *powercycle your ram* to get randomness, wouldn't it be simpler to just use a hardware stream generator?

Obligatory

[Zenaku]

Wait! My cheating unit malfunctioned! You gotta give me a do-over!

Do you have any idea how expensive a politician is

[Overzeetop]

If you knew how much it cost to buy one, you'd realize why a low cost solution is so necessary.

Then again, if you paid enough for your politician, he'd be less random on your particular issue. Hmm.....

Questions/requests

[Overzeetop]

(1) please tell me that you're joking, I don't have time to look up patent numbers right now.

(2) if you're not joking, were you some key figure at NE2 encryption, noted by an AC a few posts up?

Re:Questions/requests

[ironring]

Not joking as related to using random data from a SRAM. Please read the last patent

Re:What is wrong with the basics?

[ironring]

Most bits are constant, but it is a function of the component matching capability of the manufacturing process. The better the matching, the better the process. This is especially true when the process is used for analog circuits, where matching is an important feature/assumption. Fortunately, the better the matching, the more bits that will be random. Paul

Re:Four

[E 99]

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

All random sources are of a similar nature. It is a random system. You just have to process it to get the randomness into the results you want, such as equally likely 1's and 0's.

True Randomness for $10-20

[Anonymous Coward]

If you want cheap true randomness, the answer is simple, grab a microphone, take the input signal, mod 1 it (or mod 255 for random bytes, etc. etc.)

True randomness based on atmospheric conditions. Even if the microphone doesn't work too well, there still tends to be some form of static generated from the motherboard itself.

-JW

Re:Our research group will answer questions soon..

[Paul Crowley]

First, I'm sorry to bring this comment to your attention:

http://it.slashdot.org/comments.pl?sid=292837&cid=20543831

I've only looked at one of them:

http://www.patentstorm.us/patents/6738294.html

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!

Measuring DRAM refresh times

[Anonymous Coward]

While it's already been pointed out that this paper only applies to SRAM (which requires a constant power input), not DRAM (which only requires a periodic power input), it reminds me of an interesting electronics lab I performed in my undergraduate years.

We took SDRAM chips (the original plain old SDR technology), coded up an FPGA circuit to write its contents and then check for errors, then experimented with increasing the refresh interval. We then experimented with different parameters to see how they affected the retention time. Interestingly (if a bit obviously), SDRAM at room temperature would hold data just fine for at least several seconds, and if you chilled it only slightly, it would last much, much longer. Heating the chips naturally had the opposite effect.

I always thought it was pretty cool how long the state remained in memory just at room temperature, though, without a single bit error. SDRAM refreshes its contents every tens of ms, probably just to be conservative, but it doesn't really need to.

Re:Kolmogorov complexity not tractable - compressi

[arth1]

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.

perl -e 'print 1..9,0..9,0..9,0'

Metastable flip-flops more appropriate?

[keithjr]

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?

Re:Metastable flip-flops more appropriate?

[JoelKatz]

You have it backwards. SRAM uses transistors to store the data, DRAM uses a capacitor. Basically, SRAM has one switch that's closed if the data is a one and one that's closed if it's a zero. Each switch being on keeps the other one off. On power up, the transistors race and whether you get a zero or one depends largely on variation in gain and leakage in the transistors themselves.

See this. Basically M1/M2 races M3/M4, each one turning on turns the other off. The only stable states are M2/M3 on or M1/M4 on. Theoretically, there is no particular reason the circuit should prefer one state over the other.

DS

There is no such thing as randomness

[Chemisor]

There is no such thing as "true randomness". When an event is random, it does not mean that it is impossible to predict, but rather that it is impractical to predict. When you toss a coin, it is entirely possible to remove external disturbances and make absolute predictions on the outcome of each toss. The reason we call tossing a coin random is that we don't know the outcome, not because nature doesn't know the outcome. This confusion between a state of nature is so common, it has a name: mind projection fallacy.

Re:There is no such thing as randomness

[Anonymous Coward]

This is false. The quantum noise from a reverse biased Zener diode is truely random and cannot be predicted.

Re:There is no such thing as randomness

[JoelKatz]

Umm, no. When we talk about "true randomness" we literally mean that it is impossible to predict. When something is impractical to predict, we call it "pseudo randomness". A coin toss may actually be truly random, depending upon quantum interactions between the coin and the air (how precisely molecules bump into the coin while it's in the air), it might also be pseudo-random, I don't think the answer is known and may depend upon precisely how the coin is flipped.

There are many things that we have good reason to think are truly random. Radioactive decay is a good example. Which slit an electron will pass through in a double-slit experiment is another.

There is an even simpler way

[John Sokol]

Back in 1996 I figure out that ping times are an excellent source for Random number, especially if your connected to the internet which usually thats where you'd want them.
Just start pinging several of your favorite sites, like Google etc.
Then take the least significant digits, scramble them a bit and presto, good random number.
It's almost impossible to attack the system to De-randomize the ping times.

Of the the things I don't see people mention about random numbers is, how many can you generate per second.
If you just need one ever now and then, there are may ways, but if you build a large system that relies on long random number heavily,
then it really comes down to how many random bits per second can you generate.

I was using this for some online gambling sites, and it was critical that the card shuffles an dice rolls didn't have any possible patterns someone could exploit, since where would be a lot of money at stake.

Re:There is an even simpler way

[JoelKatz]

You don't need to be connected to the Internet. A local machine or your router/gateway will work just as well.

The randomness you get comes from the phase noise between the crystal oscillator on your network card and the crystal oscillator that produces your CPU's internal clock. This noise is in turn due to unpredictable microscopic zone temperature variations in the two quartz crystals.

You need to use your highest-precision timer (the TSC in a typical PC) to measure the arrival times. This is one of the best ways to mine thermal noise for true randomness on a conventional PC.

A Really Hot Cup of Tea?

[Anonymous Coward]

Wouldn't a Really Hot Cup of Tea be cheaper?

I guess Brownian Motion Analyzers must be too expensive to make it a practical alternative...

Re:What is wrong with the basics?

[Anonymous Coward]

not all systems have user input.
not all systems are connected to the 'net.

Re:Four

[OrangeTide]

finger prints themselves are measured with probability. If you gather the state of all bits of a system and ignore the minority "noise" that changes too often you have a fingerprint. If you take those noisy bits you ignored, you have fodder for random numbers. And you don't have to do categorization explicitly if you don't want to, if you combine all the data one way you have a random number. If you interpret it differently you have a statistical probability of a fingerprint.

At least that's what I gleaned from that article, rather than rejecting it outright.

True Randomness

[Anonymous Coward]

Bah. I keep a jar of dice in my desk. 2 6-sided die, 36 combinations, 10 digits + 26 letters. 2d6 >> 1 character. Hardest to remember passwords, but most random.

ObQuote

[Khelder]

The generation of random numbers is too important to be left to chance.
- Robert R. Coveyou

Re:How does this compare to what linux already doe

[JoelKatz]

Linux has an entropy pool that allows you to turn low-quality randomness into high-quality random numbers. If you were to use this with Linux, you would likely use it as an input into that entropy pool. But it doesn't seem that this is practical or useful on typical PCs.

New sources of entropy are always at least academically interesting.

The Quantum Error

[Chemisor]

> truly random, depending upon quantum interactions

Misguided quantum mechanics who persist in thinking that their theory is in any way logical, are invited to read this paper, which clearly describes the error of their ways.

What is a random sequence?

[rotenberry]

If a sequence was random is there a way to prove it? Apparently not:

Sergio B. Volchan
"What Is a Random Sequence,"
The American Mathematical Monthly, Vol. 109, 2002, pp. 46-63.

http://links.jstor.org/sici?sici=0002-9890(200201)109%3A1%3C46%3AWIARS%3E2.0.CO%3B2-L

This article won a Lester R. Ford Award in 2003 for "expository excellence".

Validity of your PDF paper.

[Anonymous Coward]

The validity of your PDF is considerably lowered by the grammatical errors. Perhaps you should study a few English grammar rules --especially capitalization.