Re:publica 15: Google Promotes Privacy, But Not Too Much

    by: Elliot Williams 

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.

In WW2, the Allied Navies faced two main naval code strategies: Germany's and Japan's. Roughly, the Japanese Navy sent their routing information in plaintext, while the Kriegsmarin sent it in ciphertext. Because the German routing instructions were encrypted, each node had to be able to decrypt universally. Capture one U-boat, and, well, we all saw the movie.

In contrast, the Japanese navy sent the routing information in the clear, so transceiving stations only had to read the routing information and transmit the ciphertext verbatim: capture a Japanese sub and you can only decode messages sent to that sub. However, because the routing information was visible in all transmissions, a lot of sideband avenues were opened up (you may not know what Yamamoto was sending to the Coral Sea fleet, but you're damn sure interested in the fact that he was talking to them at 2am this morning, particularly since you can then watch what they do.)

Anyways, not directly relevant to the article but a cool example of how far back this question goes.