One of the standout talks at the 33rd Chaos Communications Congress concerned pseudo-random-number generators (PRNGs). [Vladimir Klebanov] (right) and [Felix Dörre] (left) provided a framework for making sure that PRNGs are doing what they should. Along the way, they discovered a flaw in Libgcrypt/GNUPG, which they got fixed. Woot.
Cryptographically secure random numbers actually matter, a lot. If you’re old enough to remember the Debian OpenSSL debacle of 2008, essentially every Internet service was backdoorable due to bad random numbers. So they matter. [Vladimir] makes the case that writing good random number generators is very, very hard. Consequently, it’s very important that their output be tested very, very well.
So how can we test them? [Vladimir] warns against our first instinct, running a statistical test suite like DIEHARD. He points out (correctly) that running any algorithm through a good enough hash function will pass statistical tests, but that doesn’t mean it’s good for cryptography.
Continue reading “33C3: How Can You Trust Your Random Numbers?”
In this article, I’ll take you on a trip through the math of randomness, through to pseudo-randomness, and then loop back around and cover the history of the bad PRNG and its replacements. If you’ve been waiting for an excuse to get into PRNGs, you can use this bizarre fail and its fix as your excuse.
But first, some words of wisdom:
Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. For, as has been pointed out several times, there is no such thing as a random number — there are only methods to produce random numbers, and a strict arithmetic procedure of course is not such a method.
John von Neumann
John von Neumann was a very smart man — that goes without saying. But in two sentences, he conveys something tremendously deep and tremendously important about random variables and their mathematical definition. Indeed, when you really understand these two sentences, you’ll understand more about randomness than most everyone you’ll meet.
Since early evening on September 5th, 2013 the US National Institute of Standards and Technology (NIST) has been publishing a 512-bit, full-entropy random number every minute of every day. What’s more, each number is cryptographically signed so that you can easily verify that it was generated by the NIST. A date stamp is included in the process, so that you can tell when the random values were created. And finally, all of the values are linked to the previous value in a chain so that you can detect if any of the past numbers in the series have been altered after the next number is published. This is quite an extensive list of features for a list of random values, and we’ll get into the rationale, methods, and uses behind this scheme in the next section, so stick around.
Continue reading “Towards the Perfect Coin Flip: The NIST Randomness Beacon”
Even though rand() may be a good enough random number generator for making a video game, the patterns of random bits it spits out may not be sufficient for applications requiring truly random data. [Giorgio] built his own random number generator, and after many statistical tests it ended up being random enough for a few very complex calculations.
Previously, we saw [Giorgio] generate random numbers with a Chua circuit, but for all the complexity of building an electronic strange attractor there’s actually a much simpler source of random data: a white noise generator.
[Giorgio]’s random number generator for this project is just a pair of resistors, with an op-amp buffer, amplifier, and current switch to turn analog data into a digital output of random 1s and 0s. [Giorgio] sampled this data by plugging the digital out into one of the GPIO pins of a Raspberry Pi and recording the data with s small script.
To verify his sequence of bits was actually random, [Giorgio] performed a few tests on the data, some more reliable in determining randomness than others.
Because every project needs a few awesome visualizations, [Giorgio] plotted each sequence of bits as either a black or white pixel in a bitmap. The resulting image certainly looks like television static, so there are no obvious problems with the data.
[Giorgio] also performed an interesting Monte Carlo simulation with his megabytes of random data: By plotting points on a plane (with a range from 0,0 to 1,1), [Giorgio] can approximate the value of π by testing if a point is inside a circle with a radius of 1. The best approximation of pi using 10,000 points of random data came out to be 3.1436
Of course [Giorgio] put his random data through a few proper statistical tests such as rngtest and dieharder, passing all the tests of randomness with flying colors. An interesting build that shows a small glimpse of how hard generating really random numbers actually is.