[Infowarrior] - Matt Blaze on RSA-NSA Scheming

[Richard Forno]

How Worried Should We Be About the Alleged RSA-NSA Scheming?

	• By Matt Blaze
	• 12.27.13

http://www.wired.com/opinion/2013/12/what-we-really-lost-with-the-rsa-nsa-revelations/


A Reuters news story published a week ago raised disturbing questions about the relationship between the NSA and RSA Security (now a division of EMC), a prominent vendor of cryptographic technologies. The article claims that RSA entered into a $10 million contract that required, among other things, that RSA make the (not yet standardized) DUAL_EC_DRBG random number generator the default in its widely used BSAFE cryptographic library. BSAFE is used internally for RSA’s products as well as by other vendors, who license it from RSA to develop their own products around it. A couple days later, RSA issued a response, in which it denies that it deliberately weakened its products, but is silent about most of the claims in the Reuters piece.

Random numbers in cryptographic libraries are a big deal. The security of many of the most widely used cryptographic protocols — particularly those involved in key generation and initial session setup — utterly depends on an unpredictable source of random numbers. If that source is predictable to an adversary, the security of the entire system collapses completely. And DUAL_EC_DRBG is widely and very credibly suspected of containing a subtle backdoor that allows the NSA1 to predict its output under certain conditions.

It’s still unclear exactly why RSA agreed to make DUAL_EC_DRBG the default in BSAFE — whether they understood from the outset that it was likely compromised or were somehow hoodwinked by NSA. But it is clear that it remained BSAFE’s default random number generator from 2004 until September of this year; there’s an instructive timeline and analysis unraveling what happened here. RSA says it trusted the NSA in 2004, and that it “continued to rely upon” NIST (the federal agency concerned with, among other things, cryptographic standards for the federal government) as the “arbiter” of the algorithm’s security after concerns about a backdoor were publicly raised in 2007.

I believe RSA richly deserves criticism for, at best, abdicating its responsibility to customers to critically evaluate what it sells. But that’s not the main point of this post. Rather, the central question here is: Just how worried we should be about the NSA’s apparent sabotage of BSAFE’s random numbers?

Unfortunately, right now the answer is not very comforting.

What Exactly Has Been Compromised Here?

DUAL_EC_DRBG lies in a peculiar corner of a peculiar class of random number generators. Its algorithm is deterministic, which means here that its output is entirely determined by an initial “seed” parameter (that has to come from some other source of random bits that, for security, must be unpredictable and kept secret). If you know the seed value, you can re-run the algorithm and get the same random output every time.

So if an adversary learns the seed value, the random numbers aren’t secure. This isn’t in and of itself a problem; in fact, any purely algorithmic random number generator has this property. (These algorithms are also sometimes called “pseudorandom” for that reason.) The critical thing for security purposes is that it not be possible to “reverse” the algorithm to discover the seed value or otherwise predict future output bits just by looking at the random output. There are a number of widely-analyzed cryptographic pseudorandom number generators that have been developed by the crypto community. Typically, they’re built on other cryptographic algorithms, such as secret-key ciphers or hash functions.

But DUAL_EC_DRBG is somewhat unusual because it’s based not on a secret key cipher or hash function but on the public key (“number theoretic”) technique called elliptic curve cryptography.

Public key cryptography is an unusual choice for a random number generator function because it is much slower than corresponding secret key techniques; each random bit requires much more computation to produce than it would in a generator based on traditional secret key techniques. Under limited circumstances, however, there may be legitimate reasons for a designer to prefer a public-key based random number generator (having to do with specific hardware designs or other algorithms a system uses). So standardizing a public-key based scheme as an option is not in and of itself an unreasonable thing to do. NIST held a public workshop in 2004 at which DUAL_EC_DRBG was proposed for consideration as a standard. (That’s around when RSA incorporated it as the default for BSAFE.) NIST officially recommended it as a standard option in 2006.

Unfortunately, however, DUAL_EC_DRBG’s design turns out to have a serious potential flaw depending on how it is used.

One of its parameters, called “Q” in the standard, turns out to have the property that if it is chosen in a certain way, whoever selected it can have a secret backdoor that allows them to reverse the algorithm and discover the seed. (This property of Q appears to have first been noted by Daniel Brown in 2006.) And a fixed value of Q is specified in the standard, with no explanation of how it was selected. That this could provide the NSA with an effective backdoor to predict DUAL_EC_DRBG’s output was observed in a talk at the 2007 CRYPTO conference by Dan Shumow and Niels Ferguson of Microsoft.

This was a very serious observation that should have concerned anyone using the scheme for random numbers. But RSA not only continued to maintain support for DUAL_EC_DRBG in BSAFE, it remained the default random number generator. This means that any programmer employing the library who wasn’t explicitly trying to use a different algorithm would end up with DUAL_EC_DRBG.

Further evidence suggesting that NSA compromised DUAL_EC_DRBG emerged in September 2013, when the Snowden documents revealed that NSA had invested effort into influencing certain cryptographic standards to allow them to easily break them. DUAL_EC_DRBG wasn’t explicitly named, but the mysterious selection of its “Q” parameter fits the bill perfectly — and it has been widely assumed that this (and possibly other) standards are what are being referred to here.

This means that DUAL_EC_DRBG is, in effect, a master key cryptosystem (MKCS), in which the designer — the U.S. government in this case — knows a secret backdoor (how Q was generated) that allows it to reverse the algorithm … but that would be hard (in cryptographic terms) for someone else to discover and exploit just by looking at the standard. I gave a talk at the CRYPTO ’95 rump session in which Joan Feigenbaum and Tom Leighton and I formalized the MKCS concept and concluded that, in practice, they need to be based on public key techniques; DUAL_EC_DRBG fits the bill exactly.

The Implications of an NSA Backdoor Here…

So assuming that there is, indeed, an NSA backdoor in DUAL_EC_DRBG, what does that mean for the security of the systems that use it?

It’s a bit nuanced, so stick with me here.

First the good news: Given the public specification, the secret parameters of the “Q”-based backdoor are hard to find if you didn’t actually generate Q yourself.

It’s not that it’s hard to see that that there might be secret backdoor parameters. What’s hard to find is their actual values so you can exploit it yourself. How hard? As hard as the underlying problem, called EC Discrete Logarithm, which is believed to be infeasible to solve in practice. So that means that “only” the NSA, or whoever selected Q, is likely to have the secret required to break it, unless they’ve shared these values with someone else. (You only have to do the hard calculation once, but it’s believed to be a very hard problem, even for an entity with vast resources.)

Also, even if you know the secret behind Q (as NSA is presumed to) — not every system that uses DUAL_EC_DRBG is automatically vulnerable. Exploiting the backdoor requires that the system expose a certain number of bits of output in the “clear”. Many cryptographic systems do this, but not all do. It depends on the specifics of the protocol and its implementation, which varies widely.

Which brings us to several pieces of rather bad news.

The first, needless to say, is that even if only the NSA can exploit the backdoor, not everyone trusts the NSA. Especially in light of the recent (and ongoing) Snowden document leaks. (And, because the “secret” is essentially a small set of numbers, one cannot exclude the possibility that the NSA might have shared the backdoor with some of its Five Eyes partners in other countries.)

This is especially bad news for any developers using BSAFE who aspire to reach the international market. It may be possible to make the case, however credulously, that U.S. citizens should trust the NSA not to abuse their encrypted data. But that case is much harder to make to potential customers outside the U.S. who do not enjoy whatever procedural and legal protections NSA affords Americans whose traffic it intercepts.

So the bad news for BSAFE is bad news for the U.S. software market generally, at least when it comes to software with security implications.

Also, we can’t exclude the possibility that the secret backdoor parameters could someday leak, walking out the NSA’s secure doors with some future Snowden — but who might not have our best interests at heart.

Another piece of bad news is that random number generators are used everywhere in cryptographic protocols. Even though the DUAL_EC_DRBG backdoor can’t always be exploited, it is going to be extremely difficult, sometimes impossible, to be certain whether all the various systems we rely on are vulnerable. Random numbers are used not just in secure communications protocols (like SSL), but in encrypted file storage, authentication, and, perhaps most worrying, in the generation of keys and certificates. And keys stay vulnerable even after the software that generated them is replaced.

BSAFE shipped with the vulnerable algorithm as a default for almost a full decade.

* * *

If the NSA sabotaged a secure random number generator in a widely used commercial library, it used an extremely blunt instrument. It wasn’t narrowly focused on a particular system used by its targets, or even any particular system at all. Indeed, just as we will have a hard time unraveling just what has been compromised, the NSA could not have predicted everything it will end up compromising. It is the doomsday nuclear option of cryptographic backdoors, forever contaminating whatever it comes into contact with … whether friend or foe.

There’s far more at stake here than NSA’s reputation or RSA’s and other U.S. business interests, however. We urgently need NSA and RSA to come clean with the public so we can begin to unravel the damage that’s been done to the basic mechanisms of trust in our online world.

1 Corrections after publish date [12/27/2013]: An earlier version of this story included “(or anyone else)” here.


---
Just because i'm near the punchbowl doesn't mean I'm also drinking from it.