NIST Randomness Beacon | Hacker News Reader

NIST Randomness Beacon

nist.gov

97 pointsdfc63 comments

One possible application of this that NIST didn't discuss is mentioned in a new paper on accountable Bitcoin mixes: http://eprint.iacr.org/2014/077.pdf

They use signed contracts combined with a novel mixing fee mechanism based on public randomness to ensure honest behavior by rational Bitcoin mixes. If you're interested in Bitcoin the full paper is worth a read.

That does not fall under the Secure Multiparty Computation category?[^1] Or are you upset that they did not mention bitcoin mixes explicitly?

[^1]: http://www.nist.gov/itl/csd/ct/beacon-secure-multi-party-com...

I'm one of the authors. It's interesting that you cite our paper as an application of the NIST beacon. Perhaps a better reason to cite our paper is that we actually design a beacon using the Bitcoin blockchain itself (Section 4.4), because the NIST beacon has many problems.

Besides trusting NIST what are the other problem[s]?

The other major one is reliability (but that is encompassed by sufficiently broad interpretations of "trusting NIST.") Also, for our specific application it's not clear how to assign precise timestamps to Bitcoin blocks that everyone can agree on; this is necessary to be able to use a beacon that is external to the block chain.

Thanks for responding. I never thought about bitcoin+time problems. Are there any efforts/research into how to address the bitcoin+timestamp problem?

Ahhh, I forgot about that part of the paper. I read it a few weeks ago, my apologies :)

NIST random beacons can also be used to defend against selfish mining https://eprint.iacr.org/2014/007

Selfish mining requires strategically withholding blocks, the NIST random beacon gives you unforgeable timestamps, thus during block races you can prefer blocks that have newer unforgeable timestamps. Those older withheld blocks will lose blockraces punishing selfish miners.

> you unforgeable timestamps,

Unforgeable except by anyone who's able to order or trick NIST into doing something.

If NIST is unimpeachable, why not just have them run the anti-double-spending database and dispense with this inefficient blockchain stuff? :)

> prefer blocks that that have newer unforgeable timestamps

This general class of solutions often runs into problems with creating incentives for large miners to continue to mine at your current height and ignore a third party block, because you know you'll beat it in a race even though you announced late.

>If NIST is unimpeachable, why not just have them run the anti-double-spending database and dispense with this inefficient blockchain stuff? :)

Because even if NIST helps someone cheat, the cheaters only get a minor advantage and NIST runs a huge risk. Having an additional security measure which doesn't endanger the entire system if it is broken is not that same as trusting NIST.

Furthermore you can also compose the NIST beacon with other random beacons so that they would all have to collude for any party to cheat.

Imagine tomorrow, we find out a small (<33%) pool is selfish mining, what is a fix we can roll out in a few hours that will stop them while we examine longer term solutions (a long term solution might be asking every pool above 33% to provide a beacon and then having miners compose these beacons).

>This general class of solutions often runs into problems with creating incentives for large miners to continue to mine at your current height and ignore a third party block, because you know you'll beat it in a race even though you announced late.

Yes, we run into these problems at 33% of mining power. That being said, a 33% attack is better than the 0.5% attack.

Ahahahaha no. You can only "prove to anybody that [you] used truly random numbers not known before a certain point in time" if this supposed "anybody" trusts that NIST isn't just sending out pre-generated numbers.

You probably shouldn't use it for crypto, but this would be a big help in scientific and industrial contexts where you can just point to NIST instead of having to come up with answers about the quality of your random data source. Say for example you want to showcase some algorithm that you say performs 10% better than chance (in some field where that confers a significant time/$ advantage), this gives you a meaningful benchmark to measure against. And since all the random data is stored, it makes certification of scientific papers much more repeatable since they can just show longs of when the NIST server was accessed in the materials & methods section of a paper. There are many applications of a good random beacon besides crypto.

Forget how random the numbers are if your source of randomness is literally being broadcast publicly, it doesn't matter.

It is only not good for crypto, it remains good for other scientific applications.

Things like Monte Carlo simulations can, and have used public random numbers over the years -- the Rand Corporation's book of one million random digits [1] was used for this purpose. A public entropy source means that in verifying something, you can demonstrate that there was nothing up your sleeve when you used the points you did.

[1] http://www.rand.org/pubs/monograph_reports/MR1418.html

I remember finding that book in the college library and sitting down to "read" it. I was fascinated that someone would make such a thing.

NIST is explicitly advocating its use in security applications.

I also have no trouble conceiving of a scenario in which the US government may want to make an invalid scientific paper appear valid.

At the bottom of the page:

    WARNING:
    DO NOT USE BEACON GENERATED
    VALUES AS SECRET
    CRYPTOGRAPHIC KEYS.

Can you point to where exactly do they advocate what you say?

I said "security", not "as secret cryptographic keys".

Am I the only one who read the entire page? There are three links prominently featured on the page under the "Uses" header:

http://www.nist.gov/itl/csd/ct/beacon-unpredict-sampling.cfm

http://www.nist.gov/itl/csd/ct/beacon-new-secure-auth-mechan...

http://www.nist.gov/itl/csd/ct/beacon-secure-multi-party-com...

You probably shouldn't use it for crypto

Which the page clearly notes: "WARNING: DO NOT USE BEACON GENERATED VALUES AS SECRET CRYPTOGRAPHIC KEYS."

Using it for crypto and using it as a secret key are different things. You should not use it as a secret key, because it is not, in anyway, secret.

Very neat, though it's a pity that the warning about crypto in the lower-right is so hard to notice.

I mean, people weren't going to trust NIST on this anyways but if you're going to warn about crypto then it should probably be more prominent.

The dearth of documentation is also a pity.

If only they had a web interface as handy as http://www.random.org/integers/?mode=advanced

At least the UI is better than a book from RAND.

At least the beacon interface/api page has a warning about not using it for crypto front and center in red underlined italics: https://beacon.nist.gov/home

If you have an engineer using publicly broadcast random numbers in your cryptography, the problem did not originate in the font size of the "Beware of the Leopard" sign.

$ Very neat, though it's a pity that the warning about crypto in the lower-right is so hard to notice.

After reading your comment I had another peek... I think the background colour is inappropriate considering the surroundings, I had some trouble reading it well.

Who in their right mind would trust anything NIST offers considering Dual DRBG EC? Best bet is to use many entropy sources including local hardware (ie sound card audio input) mixed in a fortuna entropy pool.

The metrology folks at NIST are top notch. I think they have been awarded four Nobels in physics in the last twenty years.

Unfortunately, that attests greatly to their credentials and precisely nil to their trustworthiness. For all we know there are NSL gag orders in effect.

I am not sure what you are talking about. Do you know what metrology is?

If there is a NSL gag order in effect for the work recognized by the 2012 Physics Nobel how did the committee hear about the work? You think the scientific community just took Haroche and Wineland's word and never looked into their results?

Please, allow me to paraphrase 'pg: pedigree is for suckers.

These data points have absolutely nothing to do with practical, trustworthy crypto standard processes or confidence in their ability to due-diligence systems.

Please allow me to paraphrase dfc, "confusing metrology with crypto is for suckers."

To recap; you started this thread with "Who in their right mind would trust anything NIST offers." I responded by pointing out that there is a very talented group of people working on metrology at NIST and that some of these individuals have been awarded Nobels. What is the connection between trustworthy crypto standards and metrology?

Maybe you're not reading the same words...

Nobel snobels, still has nothing to do with crypto.

Thank you for arguing my original position for me.

You did not limit your criticism to the crypto group at NIST. Your comment was about "anything" that came out of NIST. I am not sure how I argued your original position by saying that the metrology work that comes out of NIST is top notch. How did I support your claim by arguing and presenting evidence of the opposite?

You presented my argument in argumentative manner as something different. None of this has nothing to do with NIST's reputation for evaluating crypto systems and guiding standards. So please give up trying to say how great their weighs and standards are, because again, a Nobel in physics has nothing to do with crypto.

I just read the bit in your profile about wanting to get to zero karma in 2014. It never occurred to me I was an unwitting conspirator in your race to the bottom. Had I known this I never would have "presented [your] argument in argumentative manner."

Ad hominem attacks and claims of moral superiority also have nothing to do with NIST allowing Dual EC DRBG to be backdoored and this entropy source being suspicious.

I don't know why you'd accuse a source of public randomness of having a backdoor. It has a front door.

Yeah, they've burned almost all of their trust by acquiescing tech leadership to NSA agenda.

Further, weights and crypto are night and day. I'm sure they have the best clocks and reference weights, but everything that comes out of that shop is tainted.

What should we do with UTC? Petition OBSPM to stop including NIST measurements in the calculation of UTC? Should we include USNO in the list of "tainted clocks"? Things are going to start to get crazy when you factor in GPS.

Spurious red herring... the OP topic is crypto / CSPRNGs.

The OP topic is crypto? Is the OP crypto topic your blanket rejection of anything that comes from NIST or the link with:

           WARNING:
  DO NOT USE BEACON GENERATED
       VALUES AS SECRET
      CRYPTOGRAPHIC KEYS.

Or that because it comes from NIST I should trust it because some unrelated persons have won awards. Let's not forget a likely backdoor that was either consented to, or worse, permitted with extreme incompetence. [0]

Do you work for NIST or NSA? Just curious.

[0] http://blog.0xbadc0de.be/archives/155

Gag orders for fucking metrology? Does the NSA really, really want everybody to slightly underestimate how much things weigh? Is it part of a diabolical conspiracy to take over the world by the accumulation of tiny measurement errors?

They explicitly say do not use it for crypto.

A public source of random numbers is useful in almost all the fields mentioned in [1].

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

Regarding other RNG products they comment: "However, demonstrably unpredictable values are not possible to obtain in any classical physical context."

What's wrong with any hardware RNG that produces 0's and 1's straight from physics, if these also pass the relevant statistical tests?

Physics is predictable

To clarify:

What's wrong with any hardware RNG that produces 0's and 1's straight from observing natural phenomena like "thermal noise, the photoelectric effect, and other quantum phenomena", as wikipedia puts it[1].

How can they do better than that; specifically, what do they mean with "demonstrably unpredictable values"?

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

From the quote you already posted: "in any classical physical context". They're not talking about anything quantum.

Got it, thanks!

Why would anyone trust a public random source? It may be truly random, but it can also be completely recorded such that if anyone uses this as a random source and the timestamp is known then the encryption can be broken.

It's really nothing novel [0], there was the Lava Lamp RNG. [1] Except the generation source might be technically interesting, if you at all trust the overarching politics.

[0] http://www.random.org/

[1] http://web.archive.org/web/*/http://lavarand.sgi.com

You cannot use that randomness for private key or private data generation, true. But there are less common usage scenarios that need unpredictable randomness that is guaranteed to be generated only after a certain point in time. For two party protocols you can exchange nonces to prove that both parties are participating in this exact moment, but those don't scale to thousands of mutually distrustful parties. An example for that is the proposed Bitcoin protocol change that is already cited by swordswinger12 which prevents attackers from hoarding Bitcoin blocks.

Mixing it into other sources of randomness could not hurt your crypto. Using it as the only source would be very bad.

What would happen if, just by random chance, the numbers ended up in a pattern that isn't "random". Like it returned 4 a thousand times in a row or something like that. What's the worse case scenario?

Why they say "DO NOT USE BEACON GENERATED VALUES AS SECRET CRYPTOGRAPHIC KEYS"?

Because you can't know for certain that the values are random and thus it's a terrible idea to use them in cryptography.

Yes. Raw entropy values need to be first mixed in an entropy pool first in some way that's not easily predictable. Fortuna's entropy pool is a high-quality algorithm / system that happens to be part of a cryptographically secure psueorandom number generator (CSPRNG). The two can be seperated, just as AES-NI instructions have RdSeed and RdRand.

ASCII:

    entropy sources -> entropy pool -> CSPRNG -> ...

Beyond the randomness thing (which you're right about, although NIST is claiming that they're actually random), the problem is that they're not secret.

Given that you'd probably want to avoid using for any crypto use (not just secret parameters) unless you can be sure that using this randomness for a public parameter doesn't break the cryptosystem (or USG isn't in your threat model). Given that few of us are experts in cryptology it would seem like the safe thing to do is to avoid for crypto use at all.

All the values are broadcast publicly; they're not secret.

can anyone help me understand why the chain of signed/hashed values is important? Is it all about tampering?

Reply on news.ycombinator.com