NSA encryption backdoor proof of concept published

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.

SHARE:
TOPICS: Security, EMC
5

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

Michael Lee

About Michael Lee

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.

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

Talkback

5 comments
Log in or register to join the discussion
  • So...

    What you're saying is, this could render a 256 bit encryption basically as useless as a two bit algorithm?

    Well, let's hope that P&Q are a lot more complex than they appear in this theory.
    slickjim
  • Encryption schemes that use Dual_EC_DRBG

    ...are the only ones that are subject to this weakness. I use TrueCrypt, which uses a different method of generating random bits. In addition, I can use multi-tier encryption stacks, such as Blowfish over Serpent over AES. This scheme is pretty much bullet-proof, at least until the NSA gets their quantum computer.
    harry_dyke
    • Edit

      Twofish, not Blowfish.
      harry_dyke
  • Arrest them all.

    If any private citizen hacked their way into standard encryption schemes like this, they would be arrested and jailed. Why does the NSA get special treatment?
    Josh McCullough
  • Denial Pregnant

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

    This is what attorneys (IAAL) and logicians call a "Denial Pregnant." That is, you deny a meaningless detail but not the big accusation. "You drove at 90 mph through a school zone at noon yesterday." "I deny that I did that at noon yesterday."

    The question is not whether RSA entered into a contract or agreement, or whether IT engaged in conduct, or what its intention was, or whether any back doors are for anyone else's use. The questions are (1) Do back doors exist in your code? and (2) Can the NSA use them?

    As a matter of experience, I have never seen a Denial Pregnant that was NOT an attempt to conceal the truth.
    krsmav