NSA encryption backdoor proof of concept published

Much of the theory behind how an NSA-compromised pseudo-random number generator could be abused has been published, but now one security freelancer has published code that shows it is possible.

Although weaknesses in one pseudo-random number generator (PRNG) at the heart of a US National Security Agency (NSA) scandal have been known for years, recent media attention has given light to proof-of-concept code.

The Dual Elliptic Curve Deterministic Random Bit Generator, or Dual_EC_DRBG as it is referred to by the US National Institute of Standards and Technology (NIST), has been fraught with controversy.

NIST's specifications for Dual_EC_DRBG (along with three other PRNGs) is in Special Publication (SP) 800-90A, Recommendation for Random Number Generation Using Deterministic Random Bit Generators (PDF), with Elaine Barker and John Kelsey as authors.

Kelsey notes (PDF), however, that much of the work on the standards was conducted by the NSA. The problem, according to Kelsey, is that the Dual_EC_DRBG, like many algorithms, relies on parameters labelled P and Q for security. These could be randomly generated; however, the actual choice of P and Q were dictated by those involved in the design of the algorithm — the NSA.

Research professor Matthew Green at John Hopkins University highlighted the problem of non-random parameters in his blog, stating that if the mathematical relationship between P and Q is known, then by using this relationship and the output of the PRNG, the next output can be predicted. This can then be used recursively to determine all subsequent outputs.

Security freelancer Aris Adamantiadis has combined all of the theory to generate a proof of concept exploiting the flaw. While the NSA-defined values of P and Q are unknown, Adamantiadis generates his own to demonstrate that the known relationship between the two parameters, which the NSA presumably knows, can be used to predict the next output of the PRNG.

Adamantiadis has since published the source code for his proof of concept on GitHub for those curious enough to test it for themselves.

NIST no longer recommends the use of Dual_EC_DRBG (PDF), and in September reissued SP 800-90A and reopened the discussions around its other special papers: SP 800-90B: Recommendation for the Entropy Sources Used for Random Bit Generation; and SP 800-90C: Recommendation for Random Bit Generator (RBG) Constructions.

EMC's security division, RSA, has also recommended against using the PRNG. It has come under fire for allegedly being involved in a $10 million contract with the NSA to use Dual_EC_DRBG as the default PRNG in its BSafe offering. RSA has since denied the claims , stating that it has "never entered into any contract or engaged in any project with the intention of weakening RSA's products, or introducing potential 'backdoors' into our products for anyone's use".