Towards the Perfect Coin Flip: The NIST Randomness Beacon
hackaday.com
hackaday.com
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.
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.
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.
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.
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.
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.
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?
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.
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?
An insider can easily cycle through "random" numbers until the hash of the block has a desired characteristic.
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.
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.
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.