.png)
2 hours ago
1
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.
This 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 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.
To put it another way: It’s virtually impossible to manipulate the Output Value, and even if your adversary could, they’d have to tailor a publicly-announced value to target you specifically. The cost of doing so would be astronomical, and the cost of altering the algorithm that you use to post-process the output value is trivial. When you start believing that a government standards organization has people on the inside who are doing the impossible in order to make you eat Thai food, it’s time to get back on your meds.
The one way that we can think of that the NIST could cheat in making the beacon is in the generation and timing of the random Seed Values themselves. Imagine that the Seed Values are generated randomly as stated but that they were generated a year ago instead of just a few seconds ago. Insiders at the NIST could then know the values ahead of their publication date, and even if they are not able to influence the values, they could possibly profit from knowing what decisions other parties are going to take in the future. One could even structure the agreement to take advantage of a known future outcome. Say using the value at 7:01 pm for our dinner selection instead of 7:00 pm.
We have no reason to believe this is happening, and it’s hard to imagine that the institution in charge of running the nation’s most accurate clocks would also be putting fake timestamps on the Beacon data. But it is the one hole in the system that we can think of, and if the outcomes of the Beacon end up moving stock markets, for instance, the incentive to cheat will be there.
Anyway, if nothing less than twelve layers of tinfoil will suffice for your hat, some researchers at NIST suggested that other organizations should also run their own Beacons so that users can combine outputs from institutionally different sources of entropy. One can imagine a future world where there are multiple beacon sources available to choose from. As long as you trust that the conspiracy doesn’t extend to the NIST and your other source, you can be sure that you’re getting non-manipulable values. Problem solved.
A Bell Test
This leaves us with the issue of true randomness. Sure, the values that come out of the hardware RNGs look random, but is there maybe some underlying deterministic physical rule that we could discover to predict the future evolution of the system? Our guess is no, but wouldn’t it be cool if you could issue a guarantee that the hardware generates actual randomness?
[Chua’s] Double-scroll attractor hardware for random number generation we saw in a recent feature.
Two entangled photons are generated and sent off in opposite directions. Measurements are chosen and made on each photon in locations that are far enough away from each other that there is not enough time for light from one measuring station to reach the other until after both measurements are finalized. This means that there’s no way that the result of one measurement could affect the other, and high correlation between the two measurements demonstrates that (random) quantum mechanics is deciding the outcome rather than normal deterministic physics. And as a bonus, the final outcome couldn’t possibly be known until the time that it takes light to reach one measurement station from the other. We have a guarantee of randomness and an earliest-knowable time in one apparatus.
A really solid test of the Bell Inequality and photon entanglement is interesting from a fundamental physics perspective, but it’s also a source of physically undeniable random numbers. It’s also ridiculously difficult to construct such an apparatus, but they’re working on it. The NIST plans to plug the output from the Bell experiment into the Randomness Beacon described above and then make the results available to everyone. You said you wanted random numbers, right?
Conclusion
So in short, the NIST Randomness Beacon is designed to be the perfect coin flip. It’s a public source of random values that’s totally unpredictable, but also ex-post verifiable and extremely difficult to manipulate. They’ve been running the service for over a year now in public beta, and we think it’s time that folks started thinking up interesting new applications. You’re invited to post up your new ideas, conspiracy theories, or anything else related to public random numbers in the comments below.
And before we leave the subject of random numbers, we can’t help recommending looking at Hackaday’s own One-Time Pad pictured earlier in the post (0x0f 0x000 NUEM FAEUD POMEZRH BNRBRG) or RAND’s 1955 page-turner “A Million Random Digits with 100,000 Normal Deviates“, two other sources of Grade A random numbers. Just don’t use these resources, or the NIST Randomness Beacon values, to encrypt any important secret data. Because they’re not secret.
I’d also like to thank the folks at NIST who helped with numerous clarifications and ideas for this article. Thanks in particular to [Rene Peralta] and [John Kelsey] for interesting usage ideas. [Lawrence Bassham] explained the entire Beacon procedure in great detail, and provided the code that makes verification of the chaining and signatures a breeze. Any mistakes or misapprehensions that remain, despite their help, are mine.
