Quantum random numbers [LWN.net]

By Jake Edge
April 25, 2012

Good sources of random numbers are sometimes hard to come by. Random numbers need to be, well, random, which is something that random number tests can measure, but they also need to be readily available—in enormous quantities if at all possible. The recently announced Quantum Random Number Generator from the Australian National University (ANU) fits that bill nicely. It is, according to ScienceDaily, the fastest random number generator in the world.

The researchers have derived "true" random numbers by measuring the fluctuations in a quantum vacuum and providing them on a web site for anyone to use. True random numbers are those that come from a completely unpredictable physical process, as opposed to the more frequently encountered pseudo-random numbers generated by computer algorithms. The site describes the measurements used as follows:

Traditionally, a vacuum is considered as a space that is empty of matter or photons. Quantum mechanically, however, that same space resembles a sea of virtual particles appearing and disappearing all the time. This results in the fact that the vacuum does not possess a zero-point energy, and consequently the [electro]-magnetic field describing this vacuum possesses random fluctuations in phase and amplitude at all frequencies. By carefully measuring these fluctuations, we are able to generate ultra-high bandwidth random numbers.

The apparatus used is capable of generating 5.7 gigabits of random numbers per second, but the site doesn't stream random bits at that rate due to network bandwidth constraints. As the FAQ points out, there is no actual guarantee that the numbers are truly random, but the statistics (many of which are available on the site) show that the output is "consistent with true randomness". While any measured physical process could have some unexpected bias, the only way to detect such a thing is via statistical measurements of the output. That's true whether you are flipping a coin 5.7 billion times a second or measuring a quantum vacuum.

So what can one do with such a source of (seemingly) true randomness? The ANU researchers have developed a few amusing examples, including a Matrix-like display driven by the random number stream, but there are practical uses as well. While Linux random numbers are generated using an algorithm (thus, pseudo-random), the entropy pool that feeds the algorithm is filled from (hopefully) unpredictable hardware events (e.g. keyboard, mouse, disk, and network). In some cases, especially for servers or embedded devices, many of the sources of entropy are not available. One could conceivably add entropy from a source of true randomness, either locally via a hardware random number generator or by retrieving some bits from afar.

In his "Wielding the ANU Quantum Random Number Generator" blog post, Luke Macken presents some code to use the stream. There are three parts to his quantumrandom project, a command-line tool to retrieve random data, a Python API for use in programs, and a character devices in user space (CUSE) based /dev/qrandom device. The latter will start three threads (by default) to fetch random numbers from the server, which can then be read from the device.

This isn't the first online source of true random numbers, nor will it be the last, presumably. Also, hardware random number generators are becoming more common, though they may not be producing data at anywhere near the rate of the ANU generator. Doing so would likely be serious overkill for a device targeted at a single system anyway.

As Macken points out, though, there is a potential problem lurking in ANU random numbers. Currently, there is no way to get them via an encrypted connection, which means that a man-in-the-middle adversary could gain access to the random bits. Depending on the application, that may not really be a problem. One could certainly take a suitably small random sample from a giant chunk of the random numbers supplied. Of course, choosing the random number for where to take the sample had better not be predictable either. Maybe a simulated lottery draw could help with that.

There is another question that should at least be considered: how trustworthy can random numbers downloaded from a server really be? One hopes that the researchers are on the level, but the security of the server itself may be in question. Since it is difficult to gather a large enough sample to preclude the possibility that some attacker has tampered with the data—by replaying chunks from a big static file of random numbers for example—that possibility exists. The fact that the data "looks" random from the outside is not any kind of guarantee. Caveat "emptor".

(Log in to post comments)

Quantum random numbers

Posted Apr 27, 2012 4:39 UTC (Fri) by nowster (subscriber, #67) [Link]

A "home accessible via USB" quantum random number generator is available. It uses two quantum bandgap effect (avalanche noise) sources, checks for correlation between them, whether the entropy generated passes randomness tests, and shuts down if there is a failure to be random enough. At the start of its life, it generates a little over 32 kilobits of entropy per second, which slowly degrades as the doping ions in the semiconductor migrate into the PN junction. It's also a little more portable, being about the size of a USB memory stick.

Quantum random numbers

Posted Apr 27, 2012 15:44 UTC (Fri) by nix (subscriber, #2304) [Link]

And, to crosslink to another thread, the daemon that reads from the USB key has all the code that reads data from external sources written in Lua, on the grounds that it's both more customizable and more secure than doing it in C. (Also on the grounds that the author of the daemon is extremely fond of Lua.)

Hardware RNGs are overrated

Posted Apr 26, 2012 19:21 UTC (Thu) by intgr (subscriber, #39733) [Link]

TL;DR: Pointless excercise in practice, already solved by cryptographers. I have a cheaper, faster and more secure random number generator under my desk.

Hardware RNGs are overrated. When used for security-sensitive purposes (e.g. cryptography), they always have the fundamental problem that it's hard to tell a malfunctioning RNG from well-functioning one -- unlike most other perihperals. Or the device may be outputting seemingly random numbers, but have a deliberate built-in bias, with the "key" for detecting/predicting this bias only known to the device manufacturer.

To prevent the above problems, random numbers used in cryptography should always be fed through a cryptographic PRNG, to generate another set of random numbers which have well-known security properties. One of these properties is that it's computationally infeasible to distinguish a cryptographic PRNG from true randomness -- a guarantee that this device's authors explicitly disclaim!

The amount of true randomness needed to seed a PRNG securely is rather low -- a mere 256 bits of unpredictable data is more than enough to prevent any Earth-bound attacker from guessing or predicting the output. You get that amount of entropy from the rounding error in 256 stochastic timer measurements -- such as interrupt timings. Since every output bit of a PRNG is functionally dependent on every input bit, you don't even need to know which input bits are random. It may well be 256 random bits amoung 10MB of zeroes, and you would be no less secure because of it.

What about speed? Well, AES is a popular component in cryptographic PRNGs. My aging quad-core Phenom II CPU -- without hardware AES support -- gives these results to openssl speed aes -multi 4:

type             16 bytes     64 bytes    256 bytes   1024 bytes   8192 bytes
aes-128 cbc     515754.42k   802637.25k   948130.05k  1009894.06k  1023385.60k
aes-192 cbc     404566.60k   700272.79k   791805.87k   840740.18k   710834.04k
aes-256 cbc     388939.03k   611864.38k   631131.22k   714418.52k   713521.83k

Yes, that's 713 MByte/s or 5.7 Gbit/s of random numbers at the 256-bit security level (quite a coincidence).

Hardware RNGs are overrated

Posted Apr 27, 2012 6:54 UTC (Fri) by kleptog (subscriber, #1183) [Link]

A cryptographic PRNG would indeed be better than hardware generators, but to be fair we haven't actually proved that the PRNGs we're using are actually cryptographically secure. We're just really sure, though probably more sure than we are that the hardware RNGs haven't screwed up somewhere in the implementation.

Since we need to seed cryptographic PRNGs with something we should try to use something reasonably random and in that sense a hardware RNG is helpful. But I'll agree you don't need megabits of random data to produce secure output and sampling a few timing interrupts will do. Or just use /dev/urandom.

Hardware RNGs are overrated

Posted Apr 28, 2012 6:52 UTC (Sat) by devkev (subscriber, #74096) [Link]

I remember being at a major computer science conference about 10 years ago, where one of the keynotes was a luminary describing his current favourite theoretical encryption system. I don't remember any of the details, but the take-home message was that with the only (or main) assumption of a publicly broadcast stream of high quality random numbers (and lots of them), the system was provably secure - even in the face of adversaries who are assumed to have perfect eavesdropping and infinite cpu, infinite memory, and even infinite time (ie. willing to wait as long as it takes, even millenia). I should really try to dig out the details, since this scheme seems relevant to the original article...

Hardware RNGs are overrated

Posted Apr 28, 2012 7:34 UTC (Sat) by devkev (subscriber, #74096) [Link]

Okay, here we go, it was Michael Rabin at the 2003 FCRC (the only one without slides, typical): http://www.acm.org/fcrc/plenary.htm

Looks like the scheme is called Hyper-encryption (http://en.wikipedia.org/wiki/Hyper-encryption), and my memory of it is faulty: it's no good against an infinite storage adversary, and it still has the key-exchange problem. Nevertheless, it does have some other interesting properties.

Einstein's dice and casino attacks in practice

Posted May 2, 2012 15:15 UTC (Wed) by copsewood (subscriber, #199) [Link]

I read an article a few years ago in "New Scientist" which claimed that randomness, as to whether this is an inbuilt property or an emergent property of the universe is a matter of faith. Einstein's famous quote about dice suggests something similar. Randomness as an emergent property of a inherently deterministic system (e.g. dice if the mechanical simulation of movement and rebounds etc. is precisely calculated) is good enough for security applications if the calculation can't be precise enough in practice, and more importantly the generation of numbers or system determining state transitions isn't visible to an attacker.

To illustrate this idea, we can imagine various casino attacks, e.g. by the casino owner who programs a dice throwing robot based on the bets placed to minimise payouts on these, or even by a gambler with an invisible cam who is able to capture and predict the future states of moving dice early enough still to be able to place a bet, but with a better chance of winning.

So what's important here for security purposes probably isn't whether the system being used is inherently random but whether the range of states capable of being generated is sufficiently large and probabilities of such states well enough distributed, and the state transition mechanism between system states is effectively invisible and unknowable to any likely attacker.