How useful is NIST's Randomness Beacon for cryptographic use?

Question

NIST have just launched a new service called the NSANIST Randomness Beacon. It has been met with some initial skepticism. Perhaps the cryptography community would have used it before June 2013 when NIST had a trusted reputation. At first I thought it was a mistimed April Fool's joke, however it actually appears to be an ongoing serious project.

I am intrigued as to the potential uses of this randomness beacon and serious cryptographic applications that this service could legitimately provide, given that this service is potentially hostile and probably under adversarial control. I am assuming that using it for private cryptographic keys is out of the question.

I'll quote a few things from the specification in the Uses section that raised an eyebrow for me:

First, the Beacon-generated numbers cannot be predicted before they are published. Second, the public, time-bound, and authenticated nature of the Beacon allows a user application to prove to anybody that it used truly random numbers not known before a certain point in time.

However this feature can not be true because:

The Beacon will broadcast full-entropy bit-strings in blocks of 512 bits every 60 seconds.

So while normal users won't be able to predict the random numbers, in that 60 second window someone with a privileged access inside the NIST (or NSA) could easily have access to the next random bit-string a full 60 seconds before it has been "published". If this adversary with insider access were to become one of the regular users of an application using this beacon they would have knowledge of random numbers before other users providing a significant advantage depending on the type of application.

Given this information, what actual safe, fair and useful cryptographic uses could this potentially compromised beacon provide?

Answer 1

I would characterize the service as similar to a trusted time-stamping service. Except they do not do the time-stamping, but just provide the "key". This allows a user to decide what do to with it, such as using it as a private key to sign something, or an HMAC key, proving the signature is "not older" than the timestamp. If the signature is published to a verifiable record, it can then be proven to be "not newer" than the date of the record. If the gap is short enough, the applications for a signature or hash with a provable time period of creation are numerous. It can also be used an an additional input to a two factor authentication system (I think this is the most useful).

Other sources of true randomness are available, but having one for free is better if you do not need to use it for a cryptographic purpose. Having a way to prove or audit your random source is beneficial from a business or political perspective, as in the examples for the Unpredictable Sampling application link.

Other non cryptographic uses of random values could be used to prevent bias for things like "random screenings" of airline passengers, jury selection, and collection of census data. I doubt this will be implemented, but one can hope.

Service Security

We can make three types of assumptions from a subterfuge perspective.

1. The numbers are truly random, but are provided to the NSA in advance (or are simply delayed for public view).
2. The historical record can be modified by the NSA or NIST, since they have access to the private key.
3. The numbers are not truly random.

Not being random is something that would need an audit or some kind of analysis to prove. I doubt they are not random, but that does not mean that a non random value could be used for say, a single output.

The 2nd is unlikely to occur, since acceptance of the service would only be likely if you could verify the record from other parties, which one does trust to have been unmodified. Also since the output is based on the prior outputs, the entire chain would need to be tampered with.

The 1st is much more likely, the outputs could be delayed for a substantial amount of time, even days, and you would not know unless the entropy source can be audited by a trusted party. Since the signature is generated using a known future time code plus the current and prior values, it is trivial do to this without detection. Seeds could potentially be chosen at random and tested to give an output with a specific bias, but a massive amount would probably need to be tested to give appropriate output, at significant cost to the attacker (each requires an RSA sign and a hash, and the guarantee that the one specific value will be used by the target).

Given this, one would probably use these numbers only for uses where that would be highly unlikely to occur. Most applications would fall into that category. Anyone who needs these type of numbers for a use that is likely to be manipulated by an intelligence agency would just build their own entropy generator, which is not too difficult. If nobody is using the service for something the NSA would want to tamper with, the NSA wont tamper with it, it is simply too expensive and there would be no gain.

The only concerns I have from a cryptographic perspective are how the numbers are actually generated. The page does say that the output is full entropy and the output is 512-bits. It may be safe to assume that the "Seed Value" is actually the hashed output of the entropy source/DRBG, as the XML schema file says the "Output Value" is the SHA-512 hash of the signature, which I have verified to be the case. This means the output value is computationally infeasible to predict without all the input values AND the private key.

The specifics of the seed number are not listed, one can only assume that the samples are passed through SHA-512 to give this, but the size of the sample is not listed. Since the Beacon page specifically lists compliance with SP800-90, the entropy sample should be at least 888 bits, but there is nothing to confirm that, and no detail on the actual method of output generation, such as the DRBG used (very very important), and the reseeding interval.

Other Security Concerns

At this point I will assume the service is still in beta prototype, as their XML schema file references values that are not given, such as randomValue and previousHashValue, which are most likely supposed to be the seed value and previous output.

The other unknown is how the signature is generated, since there must be someway to verify it, but no public key or any detail at all regarding the type of signature is listed. It is a 2048 bit value, so RSA is quite likely, possibly even generated by the same private key for their SSL traffic. I would hope that is not the case, when the key expires later this year, it may be difficult to verify previous outputs, as the old public key would need to be found.

Also, the page is encrypted using CBC mode using TLS 1.0, which means the connection is potentially vulnerable to tampering by a 3rd party while in transit. This type of service should be as invulnerable to tampering as possible with current technology and standards, and is not. This is not a problem with the service itself, just in how the service is accessed. The page accesses an XML formatted entry using AJAX on the same server, secured with the same protocol and key.

Acceptance is also dependent on public trust in the security of SHA-512, the methods used to measure the unpredictability of quantum behavior, and the methods described in SP800-90A for turning those measurements into random bits. SP800-90A is the publication that describes Dual EC DRBG....

Updates to the service as of March 2018

As mentioned above, the private key for their SSL traffic expired in 2014, at that point they got a new cert, and have since posted the specific certificate used to sign beacon data. That cert (2048-bit RSA, SHA256 hash) was valid for 3 years, and expired May 7th 2017. It is downloadable for verification of prior data, and they list the new public key used to sign current beacon data, but it is not a certificate and thus not signed with a root cert.

The new public key is 2048-bit RSA with 65537 as the exponent, same as in the previous certificate.

Their SSL traffic is now secured with TLS 1.2, the specific ciphersuite used is TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA. That cert has a 1 year validity, and is also 2048-bit RSA.

Their schema has been updated, and no longer references randomValue or previousHashValue. The XML records from the beacon match the schema correctly.

The service is still listed as a prototype, and they note that a new version of the beacon is in development, however there have been no updates since the last page edit on May 13th 2014.

Updates to the service as of October 2019

In June 2018, the service officially left prototype status and entered beta, using the "new version" I referenced earlier, which is now referred to as version 2.0. The new XML Schema file is fairly well documented. It appears the new beacon went online July 23rd 2018.

I was able to determine that the certificate used to sign the beacon output changed on pulse 502025, which occurred on August 16th 2019. The status of the pulse correctly specify a gap in the beacon output occurred (it was 3 minutes), with a code of 6 for certificate change, although this code is not listed in the XML Schema file. The prior certificate actually expired on January 11th 2019 and was used for an additional 7 months 5 days.

The current and prior certificates are easily obtainable from the service interface. Both were issued by DigiCert Global CA G2. The new public key is 4096-bit RSA with 65537 as the exponent.

Their SSL traffic is still secured with TLS 1.2 on my system, the specific ciphersuite used is now TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384. That cert has a 1 year validity (expiring November), and is still 2048-bit RSA. It is also issued by DigiCert, but is a common web server certificate for 14 separate NIST subdomains, including NVD and CSRC.

In May of 2019, they published a draft reference for randomness beacons, of which the version 2.0 service is an implementation of, as Internal Report 8213. This is an extremely detailed report of the design and implementation of the beacon system, and includes a security analysis with multiple threat assessments.

There are a few important changes with version 2.0 that are worth mentioning, the first is that they now have published block diagrams of how the system works, make note that although RNG3 is listed as quantum, the beacon project website specifies "We may soon integrate in the NIST Beacon a PML-developed quantum RNG (identified in the figure as #3) based on photon detection", implying that RNG3 is not currently active:

The next important change is how the hash chains are built, and the addition of the skip list. I have not verified the complete operation of the skip list, but it would appear to use the 1st hour/day/month/year as the anchor point for a hash chain, so it is much faster to audit the current beacon to the start of the chain, which could be years long.

Now instead of going back half a million hashes to go back a year, you simply go back to the start of the hour, then back by hours to the start of the day, and so on until the chain is verified back to the first minute of the first hour of the first day of the year, with a maximum of 124 verifications to go back to the beginning of the current year.

So to verify pulse 502025 (Aug 16th 2019, 14:14 Z) against the start of the month pulse of 479573, you skip back 15 minutes to 502013, then in 14 skips of an hour (60 pulses) back to 501173, then in 15 skips of a day (1440 pulses) to 479573, for a total of 44 verifications, compared to 22453 without the skip list feature.

The final point of note is that this is not the only implementation of the version 2.0 beacon technology, there are services run by the University of Chile and government of Brazil. In addition to a hardware RNG, the Chilean beacon uses entropy sources gathered from seismic measurements in Chile, a stream from a local radio station, a selection of Twitter posts, and data from the Ethereum blockchain. Brazil actually runs multiple beacons, including their primary which uses a photonic quantum TRNG, as well as a combination beacon which also includes the outputs of the Chilean and NIST beacons as sources of entropy. The output of the Chilean beacon is also one of several inputs to Cloudflare's own beacon, which is not based on the NIST design or API.

At this point, the design seems sound, and if they fix the cert issues and get RNG3 active (maybe it already is), this and others like it do appear to have many uses, although cryptographic use may not be one of them, except as an additional source of entropy and not as a primary source.

Answer 2

First up: Don't believe the hype! Especially if things can easily be proven wrong. What I mean is that your NIST have just launched a new service… is incorrect, as the NIST Randomness Beacon project is known to me (and others) since 2011. Furthermore, this project was awarded a multi-year grant from NIST's Innovations in Measurement Science (IMS) Program in August 2012. So, it's not as if they've just launched the project or website… that's simply a false claim! Just look at the project infos.

Anyway…

I don't know why you would even consider using a prototype implementation for security purposes.

In its current state, the NIST's Randomness Beacon is not yet fit for cryptographic use and the project itself describes itself being a “prototype implementation – work in progress” which is in “research status” under the lead of ITL. End date of the research status is still set to “ongoing” with no further indications of any project progress.

Also, quoting my own answer to a similar question about random.org, where I also explicitly mention the NIST Randomness Beacon project:

…

If you check the project homepage at https://beacon.nist.gov/home you'll notice that even that project clearly states:

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

And there's a good reason for that: they are still researching potential implementation options as well as potential security strengths and weaknesses of such a solution.

…

In terms of security, I therefore would personally recommend to distrust data from services like random.org even more than the beacon data generated by the NIST Randomness Beacon project in its current research phase… and until further notice, you aren't supposed to trust the Beacon data either.

Wrapping it up: it would not be secure to use random numbers from services like random.org in a cryptographic solution. This is underlined by the individual services' statements.

There are ample well-vetted and cryptographically secure alternatives to the need of falling back on using such services. It would be smarter to use those than to trust a 3rd party that puts emphasis on the fact that you should not trust its data for crypto purposes…

My closing words there are almost the same in this case: “Sites like that may have their place, but not in the realms of cryptography.”

When it comes to the NIST's Randomness Beacon, this practically means you should not (yet) be using it for anything related to cryptography, or even expect it to be useful to you. That is, unless you are a researcher and know how to use the data the prototype implementation of NIST's Randomness Beacon offers and what to expect from that data in the first place.

tl;dr?

Long story short: if you meet someone who expects anything cryptographically useful from the NIST Randomness Beacon project in its current state, simply tell them to look up the words “prototype” and “research”, as well as the terms “work in progress” and “end date: ongoing”… as that's what currently describes the status of the NIST Randomness Beacon.

That should provide ample reason to not consider the prototype to be cryptographically useful.

Answer 3

I wonder why anyone would choose to rely on a source of true random numbers fraught with questions that will ultimately have no provable – or perhaps even satisfactory – answer. There are at least a couple of companies that sell generators that provide high quality true random numbers. Having a generator on-site and available in real-time allows the necessary security for any cryptographic application. Or, at least, it puts security in the hands of the user of the random numbers.

Answer 4

The previous poster got voted down for pointing out that the service freezes, but I think that's unfair: the original question asked if the NIST beacon is useful; prototype or not, it does in fact freeze (recently for an entire weekend). So currently, it's simply not reliable and has limited usefulness. It's been running for quite some time now and it's still freezing; it's fair to think that maybe the reliability of the site is going to be low for the foreseeable future. Factor that in to discussions of usefulness.

That said, the OP asked about cryptographic value. It has none. It never will, and it's not because it's experimental. As it clearly states on the tin, you cannot use this for cryptographic keys because your key must be secret and this site gives the same thing to everyone. Someone can just record them all - at once a minute you could easily do that for thousands of years with a small disk - and try them all when decoding something. But that's only the beginning of the issues.

You can use it as a timestamp to prove something wasn't created at an earlier date (a fact that can have value in some cryptographic systems) - if and only if you trust that they haven't generated all these numbers years in advance, and there's no proof they did not. That's where any cryptographic use falls down - you don't really know where these numbers came from, how old they really are, who saw them well before you did, or if there's a man in the middle messing with what you see.

You can trust the numbers, once published, haven't been changed after the fact- if you trust their scheme for hashing previous values is unbroken. I think that's probably a safe belief, but why trust it?

The site talks about using it as a random number generator. But what if it's not random? Answer: you'll never know if it is or isn't, because you can collect only one sample a minute, so in your lifetime you won't have enough samples to form a guess. You many as well assume it's random or close enough, because even if they are cheating they'll make sure it looks random, even over years. 512 bits is more than enough space to hide non-random behaviour if you only get to see 52 million samples in your lifetime.

I use occasional samples from the site - when it's up - as part of a larger random number generation scheme. It's not the only source I use, the code that uses it is custom, and the resulting random numbers are not of interest to the NSA because I use them to simulate dice in a game with friends. The site is useful to me because I need numbers that aren't predictable in advance to my friends, so what they offer is good enough. But for commercial purposes, let alone secure ones, this site will only ever be useful if you trust NIST. NIST has proven there are reasons not the trust it. If you're doing something worth enough millions of dollars, or has significant political import, the question must ALWAYS be "who do you trust?" And there is no reason to trust a government agency that violated trust in a major way not all that long ago.

Having said all that, if NIST is doing what they claim, it's quite a neat experiment. What they describe is truly random and truly unpredictable. There's just no way to tell if they website has anything to do with a quantum generator.

If you need random numbers you can trust, buy hardware generators - several of them, from different manufacturers. Add one you built yourself, however bad. Write a custom algorithm to rotate the values they all generate, in some undocumented pseudorandom way, and then reorder them in some other undocumented pseudorandom way, and xor them all together. Then take handfuls of those and xor them down to one byte. Change the pseudorandom parts periodically. Unless someone can get to your hardware, that's as secure as you can hope for. Nothing else really is.

Addendum: Perhaps amusingly, the NIST beacon has a secondary use. Whenever the US Congress gets into a major debt and budget fight, they freeze budgets for a time, which shuts down a lot of inessential US government services - including the NIST beacon. So whatever else it's intended for, it's tolerably useful for revealing certain political issues in the US.

Addendum: it's 2022 and the blasted thing STILL freezes for entire weekends. No idea if, or when, this will be reliable.

Answer 5

To express it mathematically, $ usefulness(NIST Randomness Beacon) \approx 0 $.

This is a screen shot as of 14/4/2018 00:19 UTC+0100. Sorry it's rather large, but that's necessary.

I don't know how long it's been frozen as I can't tell what timezone the server's on, but it's at least the 30 minutes I've been typing this. It's actually yesterday for me. That's >30 beacon bongs, pings or whatever they call it. Taken in combination with the certificate debacle, I would be very hesitant to build a legal time stamping service based around this. I wouldn't want my business credibility to be dependent on a duck's plaything.

I fully appreciate the work in progress status, but Google's Gmail was in beta for half a decade and pretty usable for most of that time. This service relies on continuity. Randomness and reliability cannot be separated here. This reliability issue is clearly in addition to those cryptographic ones in the other answers.

To further undermine credibility, it's down again as of this edit. This time the entire block chain has disappeared so nothing can be verified.

---

More serious but offish topicish stuff:-

NIST has no control over cryptography. That's not their bag:-

From 800-90b:-

This publication has been developed by NIST in accordance with its statutory responsibilities under the Federal Information Security Modernization Act (FISMA) of 2014, 44 U.S.C. § 3551 et seq., Public Law (P.L.) 113-283. NIST is responsible for developing information security standards and guidelines, including minimum requirements for federal information systems, but such standards and guidelines shall not apply to national security systems without the express approval of appropriate federal officials exercising policy authority over such systems.

Which says:-

§ 3553. Authority and functions of the Director and the Secretary:-

‘‘(d) NATIONAL SECURITY SYSTEMS.—Except for the authorities and functions described in subsection (a)(5) and subsection (c), the authorities and functions of the Director and the Secretary under this section shall not apply to national security systems.

‘‘(e) DEPARTMENT OF DEFENSE AND INTELLIGENCE COMMUNITY SYSTEMS.—(1) The authorities of the Director described in para-graphs (1) and (2) of subsection (a) shall be delegated to the Secretary of Defense in the case of systems described in paragraph (2) and to the Director of National Intelligence in the case of systems described in paragraph (3).

It's a bit more nuanced than that Diffie–Hellman maths stuff. Governments do not want the people to have access to true randomness as that would allow private conversations, and that's a threat. Then throw in Patriot and Cloud acts which means that all NIST beacon output is tightly regulated ( to keep us safe).

Don't believe any of this answer. Research it yourselves.

---

We should get a tag for politics and ethics. This a deeper stuff than simple mathematics. NOBUS?