NIST Random Beacon
nist.gov
nist.gov
First, in scientific coding, one of the big challenges is in reproducing the results of a program that uses random numbers. A classic solution is to use a deterministic pseudo-random number generator that can be seeded, such that if it's seeded with the same number on two different runs, it will always generate the same output. This could be a great replacement for that, since you could write a rand() routine that accepts a start point in the chain and traverses forward to output random values on demand.
Second, you could use this as a source of future randomness -- for example, I will award you $x if the next eight bits out of the random generator represent 0-127, and will award the $x to me if they represent 128 or greater. We can both check the value, and we don't have to trust each other.
The caveat with the last example is that we both have to trust that NIST has not been compromised ...
The anti-use would be in any sort of cryptographic implementation, since any "entropy" you'd be gaining by using this data as a source of randomness is completely counteracted by the fact that the source is known. Randomness becomes deterministic once the source of the randomness is disclosed and broadcast ...
I'm not ready to disagree with you (yet) but I was thinking about the possibility of turning a pseudo-random number into a truly random number. If you generate a number using a PRNG and use that as a bit offset (via the timestamp), you might get a better string of random bits as an input to your cryptography system. Of course this relies on there being enough previously generated bits available.
In this design, that's true. But Rabin's hyper-encryption is an example of how a strongly secure encryption system can be built using a very high-bandwidth source of public randomness.
but people will do it anyway, the level of insanity out there is really high https://www.reddit.com/r/btc/comments/68pusp/gavin_andresen_... or even https://arstechnica.com/security/2015/05/crypto-flaws-in-blo...
also why would it be a good idea to use a centralized source of "entropy"....? why is NIST involved at all?
Did you read the explanation on the page? This seems to fall clearly within NIST's mandate.
Actually there's a very good use-case for NIST's Random Beacon in [OpenTimestamps](https://opentimestamps.org/): preventing miners from backdating their blocks undetectably.
Background: The Bitcoin protocol constrains block timestamps to not be >2hrs in the future, by virtue of the (kinda weak) rule that nodes reject forward dated blocks. However, for a timestamp proof that rule is irrelevant: a forward-dated block is a weaker proof, not a stronger proof. Unfortunately the reverse is problematic: a Bitcoin block is valid so long as its timestamp is > the median time of the last 11 blocks; nodes will happily accept backdated blocks, with the only constraint on backdating being that you eventually push the difficulty up.
Now, if you assume it's only a small percentage of miners doing this, the median time past rule helps you a bit, but it's hard to model; if a majority of miners are backdating blocks, there's a risk of backdated timestamps being generated with significant (hours/days) of backdating. While that risk is mostly theoretical because it's easily detected, it'd still be nice to rule it out.
Since the NIST Random Beacon represents a nonce that NIST claims did not exist in the past, we can easily use it to constrain and detect block timestamp backdating, a useful improvement to the security of OpenTimestamps. While not a priority, I'll probably add support for random beacons to OpenTimestamps at some point, and have the calendars do this automatically as part of the timestamping process.
Of course, I wouldn't do this with just NIST: all blockchains act as random beacons, so it'd make sense to use a merkle tree of this NIST random beacon and a few other blockchains at the same time to achieve this.
And finally, yes, you're quite right: using the random beacon as a source of entropy is beyond stupid.
edit: Come to think of it, the simplest possible implementation of this would be a cronjob that just grabbed the latest beacon and timestamped it... All you need to achieve is proof that the block had a dependency on the beacon after all.
edit2: ...and it's live: https://alice.btc.calendar.opentimestamps.org/experimental/i...
Can this at least be used to seed a CSPRNG at boot / device install, ideally with a mix of other entropy available? Is the problem that they’re shared for everyone at some given time?
Something similar was used in the early days of HN: "How I Hacked Hacker News (with arc security advisory)" https://news.ycombinator.com/item?id=639976 (928 points, 2968 days ago, 79 comments) [note that HN was much smaller these days, 928 points was a LOT of points]
Everyone would be able to verify one game's result by checking the public entropy source at toss time.
We announced that we had started including the Beacon in our new proofs at Consensus in May. The first of its kind.
https://tierion.com/blog/chainpoint-innovations-in-blockchai...
Its also featured in our white paper if you'd like to read more about how we're using it.
https://tokensale.tierion.com/whitepaper
Tierion has been collaborating with the leader of the Random Beacon project at NIST and we've been providing feedback on their new release, expected this summer.
Every Chainpoint 3.0 proof has the most current available NIST timestamp and its associated random value merged into the proof directly, allowing easy manual audit and cross-check. This is in addition to server NTP time in the form of a v1 UUID, which contains both a timestamp and randomness.
We also include the NIST Beacon in a new Calendar block every time it is updated so our Calendar blocks can have enhanced temporal anchoring, even in the absence of aggregated Merkle roots being anchored to the Calendar.
We've thought for a while that the NIST Beacon it pretty cool and we're glad to see others coming around to the idea as well.
NIST have a long history of positive work in the security field, so they have that in their favour. They also publish the "hash of the previous value to chain the sequence of values together", so presumably someone could record all of the values and test them for randomness ... but still, if this became the default source for random number generators in operating systems everywhere, it would present a very attractive target.
Imagine you have six sources of entropy and they all suck except the third one, which is independent and works. All the others are actively working together to manipulate your result.
Then xor'ing the bits
a xor b xor c xor d xor e xor f
can be rearranged to
(a xor b xor d xor e xor f) xor c
and it is the exact same expression. (xor is commutative.)
But now it's clear that C acts like a "one time pad" on the whole rest of the expression, making it truly random.
Of course, if it's not independent, for example if A is reading C and set equal to it, then this argument does not apply.
But it is highly unlikely that this beacon could be specifically manipulated to target weakening a single specific user of it. For one thing it couldn't be done with more than one person at a time.
So we can ignore the possibility that it is not independent of your other sources of entropy.
Go ahead, go wild including it.
(I say this even though I place the likelihood that this beacon is backdoored and predictable to the government, at 200:1 in favor.)
Two techniques you can use:
1. Mix with other sources of entropy such as number of milliseconds on the system clock. Doesn't matter if they're weak - do this yourself.
2. Draw from the beacon continuously, discarding values when you don't need thsm. Don't just draw when you need it.
These two techniques will make it almost impossible to reconstruct the random numbers, even if the sequence were predictable by someone.
By contrast, only using this beacon mixed with a backdoored rng, without xoring by some function of the system clock yourself, and only drawing the number of bits you need and doing so every time you need them, will make your solution considerably easier to bruteforce if your rng is backdoored.
First let me explain how prior probability works to you guys.
Imagine that I tell you these two facts: there is a bag (perhaps very large) with both fair coins and exceedingly unfair coins in it - such as coins so heavily weighted that they land "heads" approximately 90% of the time.
You draw a coin at random and flip it a few times, and get the sequence: heads, heads, heads, heads, heads, heads, heads, heads, heads, heads. (10 heads.)
What do you think the likelihood is that you drew a fair coin?
You might think it's exceedingly unlikely.
However, if I then told you there were 2046 fair coins and only two weighted coins in the bag, it turns out you'd be down to 50/50. If there were a billion fair coins and 1 weighted coin, you'd be almost certain to have drawn a fair coin.
The fact that you just threw ten heads pales in comparison with the prior probability.
Now what we're looking at is that you flipped it ten times and it seems totally normal. But the bag is full of ten thousand heavily weighted coins and only one fair coin.
It doesn't matter how great ("fair") the announcement looks, because we know from historical reasons the prior probability that it's actually fair.
Reading through the announcement with these eyes you get:
>However, demonstrably unpredictable values are not possible to obtain in any classical physical context.
Which is pretty absurd. Reading the brownian motion of molecules with a sensor will not allow anyone to predict when the next molecule hit. XOR-ing two classical independent processes so that the second process has no access to the first and vice versa removes any remaining possibility of error. If any source in an independent xor chain is random the rest can be weighted and it's no problem, because xor is a commutative operation, you can rewrite the chain so the random source is last, and it will act as an OTP. So just a couple of low-tech classical noisy sources of entropy are more than enough.
Instead we have a very sophisticated setup that can be backdoored at a very low level, and almost certainly is.
A plausible reason for this announcement is so that writers of backdoored cryptography can use the output of this as a putatively random seed, both claiming an honest mistake for using it in cryptography, and also perhaps writing architecture that seems not to require a truly random source but can in fact be broken by a source whose upcoming values are known to the government.
What you're looking at is almost surely a government program to help other government programmers produce broken cryptography.
When combined with the prior probability, there is almost no chance (perhaps 1 in 200) that the architecture in the write-up has been produced for any other purpose, or cannot be predicted by someone having access to the sequence and special information on the process used to produce it.
-
EDIT: downvoters don't understand the analysis. Sorry.
Given that any sequence of {heads, tails} is equally likely to any other sequence of {heads, tails} for a fair coin, what information does flipping the coin give you? There's no way to disprove that a coin is fair.
Rather than a "proof" you should think about the payoff if you then had to bet about which was which and then it was revealed.
If one landed heads 105 times and tails 3 times in your quick test, there is a conceivable universe in which that was the fair coin. But you would not accept 200:1 payoff to bet that that is the fair coin. You are much more confident than 200:1 that it is the weighted coin.
Even assuming you're right, why would they put in giant red text "DON'T USE THIS FOR CRYPTOGRAPHY" at the top, if their goal was to get you to use it for cryptography?
Nonsense
https://google.com/search?q=nist+backdoor
Further, I reviewed the architecture in the write-up.
If they wanted a random beacon that was not backdoored, they would xor it with samples from a lava lamp or something simple and unpredictable and point a web cam at it that anyone can see. As explained, this cannot reduce the randomness. They would not carefully design an architecture that is possible to backdoor, which is what we are reading about.
As for the reason why they say it should not be used in cryptography, I addressed these in my original comment.
In my estimation the chances that the government can predict the output of this random beacon are 200:1 in favor.
You are free to disagree, that's fine.
It is only viable to use this while constantly querying /last. If network/power/etc. outage lasts more than 60 secs, chains should be considered separate.
Or maybe I'm missing something obvious
The first usecase I could think of would be a warning canary that signs the data of the beacon akin to the plot in movies where someone holds up today's newspaper.
The 2nd would as said on the page as kind of "nothing up my sleeves" random number generator
https://upload.wikimedia.org/wikipedia/en/8/87/Root_of_Merkl...
I suppose it would be interesting to consider how latency of this public resource represents a risk and how it could be mitigated.