NSA encryption backdoor proof of concept published

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

Topics: Security, EMC

About

A Sydney, Australia-based journalist, Michael Lee covers a gamut of news in the technology space including information security, state Government initiatives, and local startups.

zdnet_core.socialButton.googleLabel Contact Disclosure

Kick off your day with ZDNet's daily email newsletter. It's the freshest tech news and opinion, served hot. Get it.

Related Stories

The best of ZDNet, delivered

You have been successfully signed up. To sign up for more newsletters or to manage your account, visit the Newsletter Subscription Center.
Subscription failed.