Hacker News new | comments | show | ask | jobs | submit login
NIST Random Beacon (nist.gov)
123 points by relyio 12 months ago | hide | past | web | favorite | 59 comments



There are two clear uses for this, and one anti-use.

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 ...


Nice explanation of uses and how entropy is converted into a constant. Reminds me of an old post I did on types of randomness http://www.statisticsblog.com/2012/02/a-classification-schem...


"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 ... "

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.


Part of hyper encryption strength is derived from assuming that the public randomness cannot be recorded due to cost. This beacon only emits 512 bits every 60s, so that is easily recordable.


"The anti-use would be in any sort of cryptographic implementation"

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.


That is pure security by obscurity. If I know the output of the PRNG, and that this method is being used, I also know the random number. So attacking it is no harder than attacking the PRNG itself.


Wouldn't the weak point in that system then be the PRNG? If so, doesn't that require the use of a crytographically secure PRNG in the first place?


Yes ... the PRNG is the weak point (just as it always is). And if you're only using enough bits from the PRNG to generate a timestamp, you also have to worry about whether the distribution is flat.


Part of the idea behind this is that you can run your own randomness beacon in the same manner, and if you and another person want to make a bet like that, you can each use your own beacon and xor the values together to get a new, previously unknowable, random value.


The second use is pretty much exactly how bitcoin blockchain betting systems work. It'd be interesting to know if this could be (or has been?) done in etherium or similar to lower the trust required even more.


Could we use it as a source of "reproducable randomness"? For instance, use this as an RNG during game development?


Yes, exactly. If you want to run a regression test on your game, you could compare results by feeding the string in place of your rand() function, starting from the same offset.


Given what we know now about the nsa, isn't it fairly safe to assume they _have_ been comprised?


I'm not sure what you are implying. If you're asking if the NSA can read NIST's mail -- maybe? If you are saying that the NSA can hack/compromise this particular device in a way that would benefit national security - I think you'll have to sketch that out a little more for me to go along.


"DO NOT USE BEACON GENERATED VALUES AS SECRET CRYPTOGRAPHIC KEYS"

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?


> also why would it be a good idea to use a centralized source of "entropy"....? why is NIST involved at all?

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...


In re: why is NIST?

Did you read the explanation on the page? This seems to fall clearly within NIST's mandate.


“DO NOT USE BEACON GENERATED VALUES AS SECRET CRYPTOGRAPHIC KEYS.”

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?


You need a TLS connection to get the NIST beacon, which requires a seeded rng. That seems like a chicken and egg problem.


As long as this data was signed by NIST, and we trusted NIST, there should be no need for TLS.


except that you would need to download the _entire_ random number sequence blockchain history instead of, say, specific parts. Otherwise, the specific parts you download would be known and therefore part of your randomness would be known.


This might be used as a public and neutral source for games based on random I guess (lotteries, etc.).

Everyone would be able to verify one game's result by checking the public entropy source at toss time.


If you already have good entropy source to mix with, how would NIST data help you? And if by CSPRNG you mean /dev/urandom, that is being used in crypto, too.


Anyone who knows the time you retrieved the seed can determine what the seed was.


Yes. I don't get this. If the 512 bits that are generated every minute are publicly known then they certainly aren't useful for any function where the seed is meant to be some sort of secret.


If someone know that you are using only this, they can try to guess when you get your numbers and use brute force with all the options. For example if they know the day, they must only try the 1440 possible minutes.

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]


Exactly, which is why NIST is soliciting feedback on novel uses (because lots of existing uses of random seeds are intended for use as secrets).


If you mix enough real entropy together, adding this but beacon won't making things any worse, but it won't help at all.


A clock for transactions. Since this produces verifiable data every minute, you can use that data as to sign any transaction and be able to verify that the transaction did not occur prior to the publication. However you can not verify that the signed data was not modified or even created after the publication of the data. Any thoughts on how this concept can be useful then?


It's mostly not. The block chain is much better suited for this case, because you can insert a hash of your data into a particular block and prove that you were in possession of it at the time the block was mined.


My hero, John Walker, built this thing in 1996: https://www.fourmilab.ch/hotbits/


At Tierion, we think the inclusion of the NIST Beacon in every Chainpoint 3.0 proof we generate is a powerful feature.

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.


How susceptible would this be to government influence?

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.


How much would it matter if you used this as one source of entropy for your rng?


The fact that it might be non-random is a much smaller concern than the fact that it's known by the world. The whole point of seeding a RNG with entropy (at least for cryprographic purposes) is to attempt to prevent someone else from duplicating/predicting the state of the RNG.


Ahhh ... yeah, that makes total sense. So it would literally be the worst thing you could do.


None at all! Unless it were actively and carefully manipulated to undo your specific RNG (i.e. were not independent) which is absurd, you can use it as one source no problem.

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.


At a guess, it is 18000% susceptible to government interference, meaning you'd have to read 180 announcements like this before you got to one that wasn't actively created by the government. (Not just "interfered with" after the fact, but actively created for the express purpose of being predictable by them.)

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.


You can't assign probability to human motivations. You're making this enormous assumption about human motivation in the last three paragraphs that has nothing to do with your "probability proof".

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


I based the prior probability on NIST's past behavior with respect to backdoors.

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.


Sorry - somehow I missed that.


> 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?

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.


My question was about likelihood. If I present you with exactly two coins, visually indistinguishable, but you know that one is very heavily weighted and one is unweighted coin. Then by repeatedly flipping them, you could reach incredible confidence (99.9999%) within a few minutes regarding which is which.

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.


If I read the announcement correctly, the hash is computed on the last value and is distributed separately. Either I miss something or they can change ANY value in the chain and the last hash would still check out.

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


I read "Each... value includes the hash of the previous value... chaining the sequence of values together" which is how immutability is ensured. (Amending a prior value would invalidate the hashes of every subsequent value.)


What would be the typical usecase for this beacon?

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


Financial Times was already doing something like this years ago (still is?):

https://upload.wikimedia.org/wikipedia/en/8/87/Root_of_Merkl...


Compare to the Dice-O-Matic [0] just recently featured here.

[0] https://news.ycombinator.com/item?id=14806986



Gambling seems like an interesting use case. Having a public seed and a public algorithm would mean that results should be verifiable but not predictable.

I suppose it would be interesting to consider how latency of this public resource represents a risk and how it could be mitigated.


One would assume that all bets would close X units of time before generation time.


For those interested, here's a Haskell interface to the Beacon I put together some time ago [1].

[1] https://github.com/bstamour/haskell-nist-beacon


I remember using ANU's one as the random source for a first year CS assignment once haha

https://qrng.anu.edu.au/


Hmm, what if a government agency with warrant / hacker can force a specific consumer of this service to be fed with known "random" values?


/dev/random seeding on bootup from NIST will be implemented in systemd in 3..2..1..


...and probably the computer will hang for ten minutes if the NIST server is not reachable...


That would be a terrible idea. Seeding a (C)PRNG from a publicly known value is one of the worst ways to shoot yourself in the foot.


I'm pretty sure that's the joke.


I think NIST implemented the random beacon when they announced the WTC towers report?

https://www.youtube.com/watch?v=GvAv-114bwM




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: