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.

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 [fourmilab.ch] for a practical testing tool.

I don't expect this to be statistically random: they claim it's based on thermal noise. But the startup temperature of a computer does not have that much entropy, so the thermal noise isn't reliable. Just because something's garbage doesn't mean it's statistically random.

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: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: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: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 [wikipedia.org]. Without clamping, bias will remain for exactly the same reason that SRAM doesn't consume much power; current only flows when the data changes.

As for it being a good RNG; the state of RAM on power-up is probably a lousy "random number generator", but the statistics in the paper suggest it is a fairly good "source of randomness". There's a big difference between bias and unpredictability (think about dice with '1' on five of the sides and '0' on the remaining side). You wouldn't want to use the state without putting it through a compression function first, but it's a much better seed than using clock() [berkeley.edu]!

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

Metastable flip-flops more appropriate?

[keithjr]

The article makes a short note on metastability [wikipedia.org], 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?