How useful is NIST's Randomness Beacon for cryptographic use? 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?
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.


The numbers are truly random, but are provided to the NSA in
advance (or are simply delayed for public view).
The historical record can be modified by the NSA or NIST, since 
they have access to the private key.
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.