Towards the Perfect Coin Flip: The NIST Randomness Beacon

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

63 22 12 years ago

ckuehl• 12 years ago

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.

In the example, the decision is made based on whether the first digit is odd. Even if you can't directly manipulate the final random number, couldn't "an insider at the NIST" simply generate random numbers until the resulting hash matches the desired pattern, and then publish that number?

DJB wrote an interesting blog post [1] discussing how a rogue entropy source can manipulate the output of a PRNG by emitting only the values that produce a certain pattern in the hash:

Here's an interesting example of an attack that can be carried out by this malicious source:
1. Generate a random r.
2. Try computing H(x,y,r).
3. If H(x,y,r) doesn't start with bits 0000, go back to step 1.
4. Output r as z.
This attack forces H(x,y,z) to start 0000, even if x and y were perfectly random. It's fast, taking just 16 computations of H on average.

[1] http://blog.cr.yp.to/20140205-entropy.html

pjscott• 12 years ago

See also the BADA55 elliptic curves, which were generated by a variety of commonly-used "verifiably random" procedures, but which all contain the hexadecimal string "BADA55" (or, more impressively, "BADA55EC") in their parameters somewhere:

http://safecurves.cr.yp.to/bada55.html

roywiggins2• 12 years ago

This is ameliorated by having more than one beacon that publish simultaneously, and xoring them all together, but a Bad beacon could just delay until it has seen all the Good results and then spin its RNG until the full XOR gives what it wants...

If you have very precise synchronization you could conceivably use the lightspeed limit to guarantee any Bad Beacon(s) can't know the output of the Good beacons before it publishes its own value.

higherpurpose• 12 years ago

NIST shouldn't be trusted anymore. Period.

akallio9000• 12 years ago

You want your own random bits? Tune your AM radio between stations and record the resulting static to your PC. Grab the low bit from every 10'th sample or so and concatenate into a buffer until desired length is reached. You may want to XOR alternate samples to eliminate any voltage bias your sound card has to provide equal numbers of 0's and 1's.

roywiggins2• 12 years ago

The NIST beacon means that two people can decide on a random value without trusting each other.

The NIST beacon just requires you trust NIST, and since you're not making an agreement with NIST, even -if- NIST knows the random values ahead of time, it's no use to either party unless they've hacked NIST's secret precalculated list of random values.

jemfinch• 12 years ago

But this can be done without trusting anyone at all (e.g., http://users.cis.fiu.edu/~carbunar/teaching/cis5374.F.2014/s...; cf. pages 90-91 of Applied Cryptography).

tyho2• 12 years ago

All you need is a commitment scheme. This is more secure than having to trust NIST and does not rely on being able to receive their beacon.

Alice and bob want to decide between Italian or Thai food using a coin flip, but do not trust each other to perform a fair flip. They devise a solution to their dilemma:

1. Alice generates a 512b random number A.

2. Alice performs SHA512(A) and shows the result to Bob who stores this as A_1.

3. Bob generates his own 512b random number B and sends it to Alice.

4. Alice sends A to Bob who stores it as A_2.

5. Bob verifies that A_1 = SHA512(A_2)

6. Both Alice and Bob perform XOR(A, B) and use the least significant bit to determine if they eat Thai or Italian.

Alice is satisfied that XOR(A, B) cannot be predicted by Bob because he sent her B before she revealed A to him.

Bob is satisfied that XOR(A, B) cannot be predicted by Alice because she `committed` to her value of A before he sent his B by sending him the cryptographic hash of it. If Alice tried to change her value of A in response to Bob's B, then Bob would detect it in step 5.

tyho2• 12 years ago

That works until somebody either sets up an antenna close to you and starts being able to gather the same random data as you or worse they transmit on the frequency that you are listening and actively manipulate the random data you are receiving.

caf• 12 years ago

XORing samples does not whiten the output. If we consider as an example the biased source producing independent & identically distributed (iid) bits, where each bit has a 0.7 probability of being 1 and 0.3 probability of being 0.

Your suggested whitener would produce 1-bits with probability 0.42 and 0-bits with probability 0.58 - still biased.

An example of a correct whitening algorithm for a source producing iid bits is this: Take two adjacent samples. If they are the same, throw them away; otherwise, take the first sample as the next output.

logicallee• 12 years ago

Don't xor things that are obviously dependent on each other in any way - such as two samples of radio noise - since you risk eliminating a source of entropy.

on the other hand, you can only increase entropy by xoring things that are obviously independent, such as a software RNG that doesn't know anything about your radio setup, and obviously your radio setup doesn't depend on your software RNG (but make sure of this - it's imaginable, though unlikely, that your radio setup somehow is actually picking up the low bit from your CPU right as you're doing all this xor'ing.)

if you can be guaranteed that sources are independent, you can xor with anything (all zeros if you like, whatever) and it cannot possibly decrease entropy. set up a chain of xor's.

why? Because recall: 1) XOR'ing is commutative, so if a good source of entropy is anywhere in the xor list you can rewrite it to be the last element and the value of the expression will be unchanged. 2) a good source of entropy is an OTP, so applying an OTP from a random source as the last step cannot possibly retain any information from previous steps. even if all the other steps add up to "all zeros" a single good source of entropy xor'd anywhere in the expression will make it perfectly random.

So, as long as you can be assured they're independent, xor all of the sources you want. If they're not independent, though, be careful.

A source of radio entropy is not bad in your 'stack'. But there is no cost to adding half a dozen pseudo RNG's either, the low-bit of the time in milliseconds, and any other source you can think of.

as a tip to increase entropy, draw from your RNG continuously, not only when you need the next value. then the exact timing of which output you use will be end up increasing entropy. Again this is true if your sources are independent and nothing can play with this entropy by viewing and selectively massaging the final output.

kerkeslager• 12 years ago

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.

This is hopelessly naive. We don't need to imagine that the NIST has been compromised: this has already happened. The NIST collaborated with the NSA to put a backdoor in the Dual_EC_DRBG standard[1]. Given this, I think we have to view the NIST as a compromised, untrusted entity.

As such, we must assume that an attacker has both the seed values and the NIST's private key. Given an attacker with this power, none of the approaches mentioned in the article provide security:

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.

The proposed attacker knows all the inputs to the SHA-512 hash and therefore does not need to reverse the hash.

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 x 24 x 60 = 2,880 SHA-512 stages to make the chain verify, still assuming that he knows the NIST’s secret key.

The proposed attacker knows all the inputs to the two SHA-512 hashes and therefore does not need to reverse the hash.

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.

The proposed attacker knows all the inputs to whatever hash function you choose, and therefore does not need to reverse the hash. Adding one does effectively nothing, and I'm not sure how to prove what it doesn't do, because I'm not sure what the author thinks adding one does.

A better try might be to use an adequately-sized random secret key with a unique, incrementing nonce to generate the random numbers via a pseudo-random function. However, you shouldn't trust that this works without seeing a mathematical proof--something sorely lacking in the original article. And even if it does work, it's counter-productive to use the NIST random numbers as input for your function. There are plenty of other sources of inadequate randomness, and at least if you're using your own inadequately-random numbers you can determine how inadequate the input randomness is and act accordingly.

In short, the first step toward the perfect coin flip is to stop trusting the NIST.

[1] http://en.wikipedia.org/wiki/Dual_EC_DRBG

ghshephard• 12 years ago

"The proposed attacker knows all the inputs to the SHA-512 hash and therefore does not need to reverse the hash."

Knowing the inputs to the SHA-512 hash does not give you the ability to influence the outputs. So, you won't be able to influence the results (greatly - exceptions can be made for small things like changing the odd/even of the next digit - but that ability disappears further down the chain), but, presumably, you will know what they are. I think the presumption should be that there is some agency that knows all the values in the NIST chain for the forseeable future, and no important system should be designed in the belief that those values aren't known.

What does make sense though, is taking a third-party trusted system (as suggested by the NIST), and adding that to the hash string. Something as simple as the latest block for a particular day from blockchain would be sufficient. In fact, all it really needs to be is something numeric - like the closing price of the S&P 500 would do the trick. That would prevent the NIST from calculating any further than one day in advance, and even then - They could only target you.

rwallace• 12 years ago

The NIST collaborated with the NSA to put a backdoor in the Dual_EC_DRBG standard

The version reported in the news at the time was that the NIST didn't know about the back door, and was quite pissed off with the NSA when it was discovered. The Wikipedia article seems consistent with this?

As for the rest, if you XOR multiple sources together, an adversary would have to compromise all of the sources in order to compromise the result.

cubano• 12 years ago

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.

I sure don't claim to be a QM expert, but isn't this almost the exact definition of the wave function collapse when "observed", and so then are the two related in some mathematical way?

tmslnz• 12 years ago

And from the 2009 class of critical design, the (mechanical) Coin Flipper: http://www.dotmancando.info/index.php?/projects/coin-flipper...

deckar01• 12 years ago

There is no guarantee in this scheme that the data was actually generated at the time they state.

An insider can easily cycle through "random" numbers until the hash of the block has a desired characteristic.

Zikes3• 12 years ago

That assumes the insider has a target in mind, though. How would NIST know that I am about to use the first bit of the number in a particular heads/tails scenario? How would they know I intend to use the upcoming 3:31pm number as opposed to the upcoming 4:59pm?

tlrobinson• 12 years ago

If the "contract" is between private parties not affiliated with NIST then they don't, however some interesting use-cases require the parameters be publicly known ahead of time, e.x. lotteries, elections, etc.

Zikes3• 12 years ago

A fair amount of discussion on the trustworthiness of NIST's beacon in particular, or how someone in control of a single beacon could influence the results in some way, but what about the author's suggestion for using multiple beacons run and controlled by competing interests?

Would there be any value in having companies like Microsoft, Google, Amazon, and Yahoo each running their own such beacon?

Edit: A bit of a tangent: if one were to create their own beacon service as a toy project, what would be the expected guarantees? Would a typical webserver's built-in randomness suffice for creating the seed values? What about interruptions in service/availability? Are timestamp gaps acceptable, or should they be backfilled after a server downtime?

tripzilch• 12 years ago

Um, those are all basically American companies.

You need a Russian one, a Chinese one, North Korea, Somewhere Middle-East, and one datastream you bought off the dark markets via Tor, produced by a rogue group of renegade hacker cypherpunks.

If they turn out to be all colluding, you're living the wrong novel.

Towards the Perfect Coin Flip: The NIST Randomness Beacon

Related Stories