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