21
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ That reddit post (as of this post) looks to have only 1 poster who seems to understand what this is for, and how handy this could be. $\endgroup$ – Richie Frame Mar 26 '14 at 8:33
  • 5
    $\begingroup$ Actually, an insider potentially could know these strings even longer ahead, assuming a predictable internal source. $\endgroup$ – Paŭlo Ebermann Mar 26 '14 at 23:28
20
$\begingroup$

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:

Beacon block diagram

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.

$\endgroup$
  • $\begingroup$ Good answer. I think there is another security problem. Within the 60s delay period, NIST would have access to the system and source code thus they could strategically alter the future random output to whatever they wanted suit their purpose. Even with the 'Unpredictable Sampling' applications linked above I could imagine a few scenarios where a company could pay off an employee inside the NIST to cook the next number and have a particular item/location scanned/checked. Even other agencies like the DEA might have need of "parallel constructions" under the pretense of "random" searches. $\endgroup$ – NDF1 Mar 26 '14 at 10:22
  • $\begingroup$ The problem with that scenario is that it the output is digitally signed and then hashed, and one of the inputs is the prior output, so tampering with the seed to produce the desired output is not easy $\endgroup$ – Richie Frame Mar 26 '14 at 10:51
  • $\begingroup$ It gets new entropy from the entanglement source to form the next seed for the dubious Dual EC DRBG, which then outputs the new 512 bits of entropy. Surely it hashes and signs only the most recent 512 bits of DRBG output with the past random bits and current timestamp to form a MAC. In which case the output of the DRBG being assumedly random could be replaced without anyone knowing. Surely it doesn't include the past outputs of random bits, current timestamp and signature as part of the seed into the next DRBG output... If it was doing that, then it sounds more like a PRNG rather than a TRNG. $\endgroup$ – NDF1 Mar 27 '14 at 2:24
  • $\begingroup$ Nothing actually said it uses Dual EC DRBG, they do not specify what they use. And yes, the output of the DRBG could be replaced with nonrandom data, but being able to manipulate the output hash is not easy. $\endgroup$ – Richie Frame Mar 27 '14 at 2:46
  • $\begingroup$ The "seedValue" is the hashed output of the entropy source and DRBG. This must be the random 512 bits that the users of the system want. This seedValue is what could be replaced entirely by an insider. It's not needed to manipulate the entropy input into the DRBG. The "signatureValue" is an RSA signature computed over the version, frequency, timeStamp, randomValue, previousHashValue & errorCode. The "outputValue" is the SHA-512 hash of the "signatureValue" as a 64 byte string. They can not be expecting users to use the "outputValue" (the hash of an RSA signature as their "random bits")... $\endgroup$ – NDF1 Mar 27 '14 at 4:00
6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ The purpose is that it is free and publicly available, with a stored record. This is not an RNG for generating private numbers $\endgroup$ – Richie Frame Mar 27 '14 at 2:47
  • 3
    $\begingroup$ How do you know that the "true random number generator" you bought is actually generating truly random numbers, and hasn't been subverted to produce (semi)deterministic output instead? (Answer: unless you built and tested it yourself, you can't, really. The best you can do is feed randomness from multiple sources into a well designed entropy pool like Fortuna, and hope that no attacker can predict all the sources.) $\endgroup$ – Ilmari Karonen Mar 30 '18 at 1:05
  • $\begingroup$ @IlmariKaronen That's why you should build your own :-) $\endgroup$ – Paul Uszak Oct 29 '18 at 14:12
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ If you're explaining the untrustworthiness of NIST, it might be worth pointing out that they have (many times) publicly stated that they work with NSA on crypto matters. Indeed they are required to do so under law. $\endgroup$ – Paul Uszak Oct 29 '18 at 14:25
-2
$\begingroup$

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.

beacon

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.

$\endgroup$
  • 2
    $\begingroup$ it was frozen for about 4hrs when you posted this $\endgroup$ – Richie Frame Apr 14 '18 at 3:22
  • 3
    $\begingroup$ -1 for this unhelpful answer. First of all, it is clearly stated that this is a prototype service. "NIST Randomness Beacon (Prototype Implementation) -- work in progress" You should expect ups and downs from the service. The other point that cost you was your first sentence, because you most certainly cannot see all usages for all cases ever. If you think using a prototype service in a production-grade service is OK, then you have much bigger DevOps problems than I can help you with here. $\endgroup$ – Urda Apr 20 '18 at 0:35
  • 3
    $\begingroup$ @PaulUszak you absolutely do not, because it's a research project looking into the usages of such a chained, data source. Is it production grade? No. Is it useful? Possibly, did you not review the "Uses" section as detailed on nist.gov/programs-projects/nist-randomness-beacon , because that's far greater than zero. It clearly looks like you did not. If we limited all developing technologies to what works now we'd have nothing today. Drop the snark, it's unbecoming on a stackexchange site. $\endgroup$ – Urda Apr 21 '18 at 4:39
  • 2
    $\begingroup$ …as I can't tell what timezone the server's on… – here’s a hint: “…record generation time in POSIX format (number of seconds since midnight UTC” So, when you look at the last timestamp generated and compare that to the current UTC time, you know how long it’s been since the last record publication/generation. $\endgroup$ – e-sushi Apr 21 '18 at 9:32
  • 4
    $\begingroup$ @PaulUszak I am starting to think you are not reading anything here. I have fully explained why your answer is unhelpful, and why your downvotes are earned here. Is it production grade? No. Is it useful? Possibly. is the key. I'm excited you brought up MITM, because I'm curious how you think that is possible because 1) the endpoint is served over SSL and 2) all records are signed by NIST and can be verified with a public key from NIST. You do not seem to understand the project and have a broken understanding of it. Please review it before continuing. $\endgroup$ – Urda Apr 22 '18 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.