Friday, December 27, 2013

More on RSA/NSA

In a recent post, I mentioned the report that RSA accepted a ten million dollar payment from the National Security Agency in exchange for deliberately making a vulnerable pseudorandom number generator the default choice for their encryption software. A recent Wired article by Matt Blaze goes into detail on the technology and its implications. It's worth reading the whole piece—the following is a sketch.

DUAL_EC_DRBG is an algorithm for generating pseudorandom numbers—pseudo because the process is deterministic, so if you know all of the inputs to the  generator you can predict the output. Blaze writes:
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.
In other words, the value of Q could have been chosen in a way that, along with additional information, let those who chose it deduce what number came out of the random number generator, hence predict the key the software using it would generate, hence decrypt messages encrypted with that key. The process only works in one direction—knowing the value of Q doesn't let you deduce the information needed to use it as a back door to decrypt. Knowing how Q was generated does.

Which means, assuming the obvious conjectures are correct, that what the NSA was embedding in RSA software was a master key. Using it the NSA could decrypt information encrypted using numbers generated by DUAL_EC_DRBG. Other people could use that master key only if they were able to get from NSA the information on how the value of Q used in the standard had been generated. 

A very clever idea. Assuming Blaze is correct, quite a lot of the cryptographic infrastructure generated during the nine years when DUAL_EC_DRBG was the default algorithm in RSA encryption software is insecure against the NSA. Also  against anyone else who somehow obtains the information on how Q was generated.

I should  add that RSA has denied the charges but offered no explanation of why they made that particular PNG the default in their software and kept it the default long after security professionals had pointed out its weakness. Nor has RSA denied or explained the purported ten million dollar payment from NSA. Their denial amounts to "trust us, we didn't do it."

4 comments:

Anonymous said...

"DUAL_EC_DRBG is an algorithm for generating pseudorandom numbers—pseudo because the process is determinant"

I think you mean deterministic here, no?

David Friedman said...

Ricardo:

Thank you. Fixed.

Martin Wolf said...

Note that the Daniel Brown who was one of the first to describe this technique for backdooring an EC-based RNG (and who actually obtained a patent on that idea!) was also a member of the ANSI standardization committee for this RNG, of which a representative from RSA was also a member. So they can hardly claim that they were not aware of this.

Also note that the Wikipedia page on Dual EC DRBG has been prominently mentioning the backdoor suspicions ever since the very first version of that page was written in 2007.

This page contains a nice timeline, illustrating that there was a *long* period of time during which the RSA company reasonably must have known that their choice of default RNG was one which no responsible security engineer could recommend in good faith, yet they did nothing about it until the Snowden revelations made it impossible to ignore any longer.

I'm not a professional cryptographer so of course it's easy to be a back-seat driver, but it seems to me that the entire security community dropped the ball on this one. This is a community where a highly theoretical "break" which reduces the strength of an algorithm from e.g. 2^256 to 2^248, is considered a serious reason for worry, yet the fact that a popular, mainstream crypto library from one of the largest companies in the field, used an RNG which almost certainly contained a rather blatant backdoor, managed to mostly fly under the radar for years!

Anonymous said...

You need to watch Jacob Applebaum's talk on the most recent leaks, which were published in Der Spiegel last week. It's called "Infect and Protect" on Youtube