Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
1  
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. –  Richie Frame Mar 26 at 8:33
4  
Actually, an insider potentially could know these strings even longer ahead, assuming a predictable internal source. –  Paŭlo Ebermann Mar 26 at 23:28
2  
I've voted not to close as 'too opinion based' because I think there is scope for a non-opinion answer. –  figlesquidge Mar 27 at 10:03

3 Answers 3

up vote 7 down vote accepted

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

share|improve this answer
    
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. –  NDF1 Mar 26 at 10:22
    
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 –  Richie Frame Mar 26 at 10:51
    
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. –  NDF1 Mar 27 at 2:24
    
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. –  Richie Frame Mar 27 at 2:46
    
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")... –  NDF1 Mar 27 at 4:00

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

share|improve this answer
3  
The purpose is that it is free and publicly available, with a stored record. This is not an RNG for generating private numbers –  Richie Frame Mar 27 at 2:47

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.

share|improve this answer
    
It is too convenient to claim it is a 'prototype' or 'research' project. I think it was released at a time before the NSA leaks and designed to prey on the gullibility of users who might be inclined to use it due to NIST's trusted name stamped on it. The many unknowns about its inner workings, potential for insider knowledge of numbers before they are available, potential for insider manipulation of the numbers, potential use of a Dual EC DRBG standard for generating the numbers that can contain a kleptographic backdoor, all have the trademark signatures of NSA involvement from the start... –  NDF1 Mar 27 at 4:20
    
@NDF1 “…too convenient to claim it is a 'prototype' or 'research' project…” FYI: that's not a claim, it's written all over the related pages I've linked to. Also, your argumentation is based on unproven claims/theories of potential NSA involvement. That's merely opinion-based guessing you're doing there… and discussing such conspiracy theories is off-topic here. Nevertheless, I gladly accept your downvote as I understand you're currently wearing a tin-foil hat. Please feel motivated to ask questions at Crypto.SE, so you can learn about what's important in cypto, and what's opinion. Best… –  e-sushi Mar 27 at 12:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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