http://hackaday.com/2014/12/19/nist-randomness-beacon/

Towards the Perfect Coin Flip: The NIST Randomness Beacon
72 Comments

by: Elliot Williams

December 19, 2014

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.

But first, before those of you who’ve got crypto on the brain start thinking crazy thoughts, note that the NIST has a banner stating the obvious in all caps: “WARNING: DO NOT USE BEACON GENERATED VALUES AS SECRET CRYPTOGRAPHIC KEYS.” Why not? Cryptographically speaking, they’re phenomenal random numbers; they’re just not secret at all! In contrast, they’re publicly available to everyone and archived for all time. The aim of the Randomness Beacon is to provide a random number standard, not to generate secrets. This distinction between secrecy and randomness is important in order to realize what the NIST is up to, so put your secrecy on the shelf for now. We’re talking randomness here.
The Perfect Coin Flip

A random variable, says the statistician, is a function that produces a value that is unknown before a given point in time, but is constant thereafter. This instant when the value is realized is crucial to understanding randomness. It’s the instant that separates the past, a period of time when the outcome has a probability distribution around its possible values, from the present in which the outcome is a simple constant number.

Before you roll that twenty-sided die, any number from one to twenty could come up. After the die comes to a stop, it’s absolutely certain that you just rolled a seventeen, and that fact is never going to change. You just rolled a seventeen, and only a seventeen, with certainty and forevermore. The probability distribution has collapsed to a point, which is exactly why we roll dice or flip coins if you think about it. Keep these concepts of uncertainty and timing in your mind as I tell you a brief, entirely fictional, story.

My wife and I are going out to a restaurant, but we can’t decide whether to get Italian or Thai. For the past year, we’ve been deciding restaurants with a coin flip, but that hasn’t worked since she got suspicious and discovered that the “random” coin flip isn’t random at all, and that I’d been using a two-headed coin. She’s not going to accept a dice roll either, for the same reason that we don’t play craps together anymore. What we need is a perfect coin flip: some future random event with an outcome that’s currently totally unpredictable, impossible for either of us to influence, but then easily verifiable after the event so there’s no room for argument.

Note what’s going on here. If either of us knew what the future random value would be, it wouldn’t be random. But we require something even stronger, that we can’t even make useful predictions about the outcome — that the coin is a fair coin. And since she doesn’t trust me anymore, the only way we’re going to go out to dinner is if neither of us can possibly influence the future value. Burned by a year of eating Thai food, she’s not going to trust me to read the result out to her either, she’ll need to see the results herself.

nist-randomness-beacon-screenshotThis is exactly what is provided by the NIST Randomness Beacon. To pick a restaurant, we agree to look at the NIST’s webpage at 7:00 pm and if the first digit is even, we go Thai. If it’s odd, we go Italian. We both agree that this is fair because the 7:00 pm result isn’t published until 7:00 pm. As late as 6:59 pm, the outcome is entirely unknowable, and after 7:00 pm it’s publicly available to anyone and hashed and signed with the NIST Beacon’s secret key, so it’s easily verifiable. Because the Beacon’s Output Value is the product of a few hashing steps, it’s also almost impossible that I could influence the value ahead of time even if I had an insider at the NIST. Even if I’ve hacked into the NIST’s servers and tried to change that one value, the way that the values are chained will eventually make this tampering obvious.

While it’s overkill for picking restaurants, there are a lot of similar agreements that a publicly available source of randomness will facilitate. One similar example from the NIST’s website is that of random inspections. If a saboteur knew ahead of time which box of mangoes was going to be “randomly” inspected, he could fill it with contraband, and the whole shipment would get impounded. Or if a pharmaceutical company knew ahead of time which patients were going to receive the real drug and which the placebo, they could assign healthier patients to the test group. By using a neutral source of randomness, the saboteur is left guessing and the pharma firm can demonstrate that it didn’t cheat on its science. Or the Beacon could be used in an election in a scheme to randomly sample precincts and re-count votes, immune to influence from any political parties.

More esoterically, one could use the Randomness Beacon to prove that something is newer than a certain date by including a recent Beacon entry. As of this writing, the values for December 31, 2014 are all still up in the air, so I can’t possibly write one of them down yet. But from Jan 1, 2015 and on, it’s trivial to do so. So if I get a bunch of t-shirts made with the midnight value from December 31, it’s absolutely verifiable that I got them made in the new year. In short, you could use the Beacon as a not-older-than dating scheme.
How Does It Work?

So to see how the NIST pulls this off, let’s take a quick look behind the curtains at how the Randomness Beacon achieves its goals of providing a random string of bits that’s completely unpredictable, stupendously difficult to influence, and publicly verifiable. See Figure 1 for the overview.

It all begins, naturally, with the random number generators. Two independent hardware random number generators provide 512 bits of randomness, and these two values are XOR’ed together to yield the Seed Value. Taken on its own, this is an extremely good 512-bit random number.

The Seed Value is then collected together with the rest of the relevant descriptive data: version number, frequency of output, the time stamp, a code for the chaining status, and the value of the previous output. This collection ties the random outcome together with the time that it was created and links this value with the previous one. The collection of data is then hashed with SHA-512 and signed with the Beacon’s private key, yielding the Signature. Given the Beacon’s public key, one can easily verify that the signature corresponds to the relevant data and is signed by the Beacon. You can use the UNIX shell script at the bottom of this article to run a verification for you.

Finally, the signature is hashed with SHA-512 again to create the final Output Value. This is the value that you’ll want to use as your random number. It incorporates all the relevant information about this minute’s value because it’s a hash of the signature, which is in turn a hash of the data. All of this hashing preserves the original entropy from the Seed Value but additionally makes the Output Value depend on the Beacon’s secret key and all the relevant background data in a verifiable way.
Devil’s Advocacy

Now let’s say that you don’t trust the NIST. That’s OK, because by design you don’t need to. What you would care about, for the purpose of deciding on dinner, is that the value isn’t manipulable in a way that could affect whether we go out for Thai or Italian. If someone inside the NIST wants to change the Output Value by picking a particular Seed Value, there are two rounds of SHA-512 hashing standing between the Seed Value and the Output Value even if they know the Beacon’s secret key. SHA-512 is not known to be broken at present, and so even working backwards through one of the SHA-512 stages is essentially impossible; two rounds is impossible squared.
Combining NIST with your own hashes (like our One TIme Pad) creates an even more secure system than using a single one.
Combining NIST with your own hashes (like our One TIme Pad) creates an even more secure system than using just one source.

If you want to make the outcome even more difficult to manipulate, you could use two values from the Beacon and XOR or hash them together to create the final random value. Because the outputs are chained, changing any value in the past introduces a changed Previous Output value which would have to be propagated forward to the current observation. So if you’d like to make your adversary’s work super-duper difficult, combine the Output Values from today at 7:00 pm and yesterday at 7:00 pm. Your adversary will have to work backwards through 2 * 24 * 60 = 2,880 SHA-512 stages to make the chain verify, still assuming that he knows the NIST’s secret key.

But suppose SHA-512 were broken and working it backwards were easy instead of being ridiculously difficult. Nothing prevents you from writing your contract to take the Output Value, add one to it, and run this value through a better hash of your choosing. Now the bad actor inside the NIST has to reverse your chosen hash function as well.