Zum Inhalt springen

BULLRUN: The NSA's $250 Million Encryption Weakening Program

Zusammenfassung

BULLRUN was a classified NSA program, revealed by Edward Snowden in 2013, that spent approximately $250 million per year to covertly weaken commercial encryption products and standards. The program’s methods included inserting backdoors into encryption standards, influencing standards bodies to adopt weaker algorithms, and pressuring technology companies to implement weakened versions of their products. The most documented action was the insertion of a backdoor into a NIST-standardized random number generator (Dual EC DRBG) that RSA Security had accepted $10 million from the NSA to include as the default in their products.

The Random Number Generator Backdoor

Dual EC DRBG (Dual Elliptic Curve Deterministic Random Bit Generator) was standardized by NIST in 2006 as part of SP 800-90A. A Deterministic Random Bit Generator (DRBG) is a component of cryptographic systems: it produces the pseudo-random numbers used for key generation, nonces, and other cryptographic operations. The security of the cryptographic system depends on the unpredictability of these numbers.

Cryptographers Niels Ferguson and Dan Shumow identified a potential backdoor structure in Dual EC DRBG at a 2007 CRYPTO conference presentation. They showed that the algorithm included two specific elliptic curve points (P and Q) whose relationship could allow someone who knew the discrete logarithm between them to predict subsequent outputs given a small amount of observed output. If the NSA had chosen those points knowing the discrete logarithm (essentially, if they picked both P and Q rather than using independently generated points), they could reconstruct any session key generated using Dual EC DRBG.

The Snowden documents, published in 2013, confirmed what Ferguson and Shumow had suspected: the NSA had inserted this backdoor deliberately.

RSA Security’s Role

RSA Security — a major cryptographic security company, maker of the SecurID token and the BSAFE cryptographic library — had signed a $10 million contract with the NSA in 2004 to make Dual EC DRBG the default random number generator in BSAFE. This made the backdoor pervasive: BSAFE was widely used in banking, healthcare, and government systems.

RSA Security denied knowing the algorithm was backdoored. Cryptographers who had read the 2007 Ferguson-Shumow paper found the defense difficult to accept; the paper had specifically warned about the backdoor structure. Whether RSA’s executives knew or chose not to investigate is disputed.

The Broader Program

BULLRUN extended beyond Dual EC DRBG. The Snowden documents described the program as targeting SSL/TLS (the protocol protecting HTTPS), VPN protocols, and 4G/LTE cellular encryption. Methods included:

  • Direct influence on standards bodies: NSA liaisons to NIST, IETF, and other standards organizations working to weaken specifications before publication.
  • Commercial relationships: Contracts with technology companies to implement weakened versions of security products.
  • Exploitation of known vulnerabilities: Stockpiling of exploits for cryptographic implementation weaknesses.

The Privacy War and Cryptography history articles provide broader context for the ongoing tension between intelligence agencies and strong encryption.

📚 Sources