Bullrun (decryption program)

Last updated
Bullrun classification guide published by theguardian.com Classification guide for Project BULLRUN.pdf
Bullrun classification guide published by theguardian.com

Bullrun (stylized BULLRUN) is a clandestine, highly classified program to crack encryption of online communications and data, which is run by the United States National Security Agency (NSA). [1] [2] The British Government Communications Headquarters (GCHQ) has a similar program codenamed Edgehill. According to the Bullrun classification guide published by The Guardian , the program uses multiple methods including computer network exploitation, [3] interdiction, industry relationships, collaboration with other intelligence community entities, and advanced mathematical techniques.

Contents

Information about the program's existence was leaked in 2013 by Edward Snowden. Although Snowden's documents do not contain technical information on exact cryptanalytic capabilities because Snowden did not have clearance access to such information, [4] they do contain a 2010 GCHQ presentation which claims that "vast amounts of encrypted Internet data which have up till now been discarded are now exploitable". [1] A number of technical details regarding the program found in Snowden's documents were additionally censored by the press at the behest of US intelligence officials. [5] Out of all the programs that have been leaked by Snowden, the Bullrun Decryption Program is by far the most expensive. Snowden claims that since 2011, expenses devoted to Bullrun amount to $800 million. The leaked documents reveal that Bullrun seeks to "defeat the encryption used in specific network communication technologies". [6]

Naming and access

According to the NSA's Bullrun Classification Guide, Bullrun is not a Sensitive Compartmented Information (SCI) control system or compartment, but the codeword has to be shown in the classification line, after all other classification and dissemination markings. Furthermore, any details about specific cryptographic successes were recommended to be additionally restricted (besides being marked Top Secret//SI) with Exceptionally Controlled Information labels; a non-exclusive list of possible Bullrun ECI labels was given as: APERIODIC, AMBULANT, AUNTIE, PAINTEDEAGLE, PAWLEYS, PITCHFORD, PENDLETON, PICARESQUE, and PIEDMONT without any details as to what these labels mean. [1] [2]

Access to the program is limited to a group of top personnel at the Five Eyes (FVEY), the NSA and the signals intelligence agencies of the United Kingdom (GCHQ), Canada (CSE), Australia (ASD), and New Zealand (GCSB). Signals that cannot be decrypted with current technology may be retained indefinitely while the agencies continue to attempt to decrypt them. [2]

Methods

Slide published by The Guardian diagramming the high-level architecture of NSA's "Exploitation [Cracking] of Common Internet Encryption Technologies" NSA-diagram-001.jpg
Slide published by The Guardian diagramming the high-level architecture of NSA's "Exploitation [Cracking] of Common Internet Encryption Technologies"

Through the NSA-designed Clipper chip, which used the Skipjack cipher with an intentional backdoor, and using various specifically designed laws such as CALEA, CESA and restrictions on export of encryption software as evidenced by Bernstein v. United States , the U.S. government had publicly attempted in the 1990s to ensure its access to communications and ability to decrypt. [7] [8] In particular, technical measures such as key escrow, a euphemism for a backdoor, have met with criticism and little success.

The NSA encourages the manufacturers of security technology to disclose backdoors to their products or encryption keys so that they may access the encrypted data. [9] However, fearing widespread adoption of encryption, the NSA set out to stealthily influence and weaken encryption standards and obtain master keyseither by agreement, by force of law, or by computer network exploitation (hacking). [5]

According to a Bullrun briefing document, the agency had successfully infiltrated both the Secure Sockets Layer as well as some virtual private networks (VPNs). [1] [2] The New York Times reported that: "But by 2006, an N.S.A. document notes, the agency had broken into communications for three foreign airlines, one travel reservation system, one foreign government's nuclear department and another's Internet service by cracking the virtual private networks that protected them. By 2010, the Edgehill program, the British counterencryption effort, was unscrambling VPN traffic for 30 targets and had set a goal of an additional 300." [5]

As part of Bullrun, NSA has also been actively working to "Insert vulnerabilities into commercial encryption systems, IT systems, networks, and endpoint communications devices used by targets". [10] The New York Times has reported that the random number generator Dual_EC_DRBG contains a back door, which would allow the NSA to break encryption keys generated by the random number generator. [11] Even though this random number generator was known to be insecure and slow soon after the standard was published, and a potential NSA kleptographic backdoor was found in 2007 while alternative random number generators without these flaws were certified and widely available, RSA Security continued using Dual_EC_DRBG in the company's BSAFE toolkit and Data Protection Manager until September 2013. While RSA Security has denied knowingly inserting a backdoor into BSAFE, it has not yet given an explanation for the continued usage of Dual_EC_DRBG after its flaws became apparent in 2006 and 2007. [12] It was reported on December 20, 2013, that RSA had accepted a payment of $10 million from the NSA to set the random number generator as the default. [13] [14] Leaked NSA documents state that their effort was “a challenge in finesse” and that “Eventually, N.S.A. became the sole editor” of the standard. [5]

By 2010, the leaked documents state that the NSA had developed "groundbreaking capabilities" against encrypted Internet traffic. A GCHQ document warned however "These capabilities are among the SIGINT community's most fragile, and the inadvertent disclosure of the simple 'fact of' could alert the adversary and result in immediate loss of the capability." [5] The document later states that "there will be NO 'need to know.'" [5] Several experts, including Bruce Schneier and Christopher Soghoian, had speculated that a successful attack against RC4, an encryption algorithm used in at least 50 percent of all SSL/TLS traffic at the time, was a plausible avenue, given several publicly known weaknesses of RC4. [15] Others have speculated that NSA has gained ability to crack 1024-bit RSA/DH keys. [16] RC4 has since been prohibited for all versions of TLS by RFC 7465 in 2015, due to the RC4 attacks weakening or breaking RC4 used in SSL/TLS.

Fallout

In the wake of Bullrun revelations, some open source projects, including FreeBSD and OpenSSL, have seen an increase in their reluctance to (fully) trust hardware-based cryptographic primitives. [17] [18]

Many other software projects, companies and organizations responded with an increase in the evaluation of their security and encryption processes. For example, Google doubled the size of their TLS certificates from 1024 bits to 2048 bits. [19]

Revelations of the NSA backdoors and purposeful complication of standards has led to a backlash in their participation in standards bodies. [20] Prior to the revelations the NSA's presence on these committees was seen as a benefit given their expertise with encryption. [21]

There has been speculation that the NSA was aware of the Heartbleed bug, which caused major websites to be vulnerable to password theft, but did not reveal this information in order to exploit it themselves. [22]

Etymology

The name "Bullrun" was taken from the First Battle of Bull Run, the first major battle of the American Civil War. [1] Its predecessor "Manassas", [2] is both an alternate name for the battle and where the battle took place. "EDGEHILL" is from the Battle of Edgehill, the first battle of the English Civil War. [23]

See also

Related Research Articles

In cryptography, RC4 is a stream cipher. While it is remarkable for its simplicity and speed in software, multiple vulnerabilities have been discovered in RC4, rendering it insecure. It is especially vulnerable when the beginning of the output keystream is not discarded, or when nonrandom or related keys are used. Particularly problematic uses of RC4 have led to very insecure protocols such as WEP.

A cryptographically secure pseudorandom number generator (CSPRNG) or cryptographic pseudorandom number generator (CPRNG) is a pseudorandom number generator (PRNG) with properties that make it suitable for use in cryptography. It is also referred to as a cryptographic random number generator (CRNG).

Transport Layer Security (TLS) is a cryptographic protocol designed to provide communications security over a computer network. The protocol is widely used in applications such as email, instant messaging, and voice over IP, but its use in securing HTTPS remains the most publicly visible.

<span class="mw-page-title-main">Daniel J. Bernstein</span> American mathematician, cryptologist and computer scientist (born 1971)

Daniel Julius Bernstein is an American mathematician, cryptologist, and computer scientist. He is a visiting professor at CASA at Ruhr University Bochum, as well as a research professor of Computer Science at the University of Illinois at Chicago. Before this, he was a visiting professor in the department of mathematics and computer science at the Eindhoven University of Technology.

Niels T. Ferguson is a Dutch cryptographer and consultant who currently works for Microsoft. He has worked with others, including Bruce Schneier, designing cryptographic algorithms, testing algorithms and protocols, and writing papers and books. Among the designs Ferguson has contributed to is the AES finalist block cipher algorithm Twofish as well as the stream cipher Helix and the Skein hash function.

Articles related to cryptography include:

<span class="mw-page-title-main">RSA Security</span> American computer security company

RSA Security LLC, formerly RSA Security, Inc. and trade name RSA, is an American computer and network security company with a focus on encryption and decryption standards. RSA was named after the initials of its co-founders, Ron Rivest, Adi Shamir and Leonard Adleman, after whom the RSA public key cryptography algorithm was also named. Among its products is the SecurID authentication token. The BSAFE cryptography libraries were also initially owned by RSA. RSA is known for incorporating backdoors developed by the NSA in its products. It also organizes the annual RSA Conference, an information security conference.

<span class="mw-page-title-main">Export of cryptography from the United States</span> Transfer from the United States to another country of technology related to cryptography

The export of cryptography from the United States to other countries has experienced various levels of restrictions over time. World War II illustrated that code-breaking and cryptography can play an integral part in national security and the ability to prosecute war. Changes in technology and the preservation of free speech have been competing factors in the regulation and constraint of cryptographic technologies for export.

<span class="mw-page-title-main">Nothing-up-my-sleeve number</span> Numbers used by cryptographers to show that they are working in good faith

In cryptography, nothing-up-my-sleeve numbers are any numbers which, by their construction, are above suspicion of hidden properties. They are used in creating cryptographic functions such as hashes and ciphers. These algorithms often need randomized constants for mixing or initialization purposes. The cryptographer may wish to pick these values in a way that demonstrates the constants were not selected for a nefarious purpose, for example, to create a backdoor to the algorithm. These fears can be allayed by using numbers created in a way that leaves little room for adjustment. An example would be the use of initial digits from the number π as the constants. Using digits of π millions of places after the decimal point would not be considered trustworthy because the algorithm designer might have selected that starting point because it created a secret weakness the designer could later exploit—though even with natural-seeming selections, enough entropy exists in the possible choices that the utility of these numbers has been questioned.

The security of cryptographic systems depends on some secret data that is known to authorized persons but unknown and unpredictable to others. To achieve this unpredictability, some randomization is typically employed. Modern cryptographic protocols often require frequent generation of random quantities. Cryptographic attacks that subvert or exploit weaknesses in this process are known as random number generator attacks.

Kleptography is the study of stealing information securely and subliminally. The term was introduced by Adam Young and Moti Yung in the Proceedings of Advances in Cryptology – Crypto '96. Kleptography is a subfield of cryptovirology and is a natural extension of the theory of subliminal channels that was pioneered by Gus Simmons while at Sandia National Laboratory. A kleptographic backdoor is synonymously referred to as an asymmetric backdoor. Kleptography encompasses secure and covert communications through cryptosystems and cryptographic protocols. This is reminiscent of, but not the same as steganography that studies covert communications through graphics, video, digital audio data, and so forth.

Below is a timeline of notable events related to cryptography.

The Microsoft Windows platform specific Cryptographic Application Programming Interface is an application programming interface included with Microsoft Windows operating systems that provides services to enable developers to secure Windows-based applications using cryptography. It is a set of dynamically linked libraries that provides an abstraction layer which isolates programmers from the code used to encrypt the data. The Crypto API was first introduced in Windows NT 4.0 and enhanced in subsequent versions.

<span class="mw-page-title-main">Network Security Services</span> Collection of cryptographic computer libraries

Network Security Services (NSS) is a collection of cryptographic computer libraries designed to support cross-platform development of security-enabled client and server applications with optional support for hardware TLS/SSL acceleration on the server side and hardware smart cards on the client side. NSS provides a complete open-source implementation of cryptographic libraries supporting Transport Layer Security (TLS) / Secure Sockets Layer (SSL) and S/MIME. NSS releases prior to version 3.14 are tri-licensed under the Mozilla Public License 1.1, the GNU General Public License, and the GNU Lesser General Public License. Since release 3.14, NSS releases are licensed under GPL-compatible Mozilla Public License 2.0.

Dual_EC_DRBG is an algorithm that was presented as a cryptographically secure pseudorandom number generator (CSPRNG) using methods in elliptic curve cryptography. Despite wide public criticism, including the public identification of the possibility that the National Security Agency put a backdoor into a recommended implementation, it was, for seven years, one of four CSPRNGs standardized in NIST SP 800-90A as originally published circa June 2006, until it was withdrawn in 2014.

In cryptography, Curve25519 is an elliptic curve used in elliptic-curve cryptography (ECC) offering 128 bits of security and designed for use with the Elliptic-curve Diffie–Hellman (ECDH) key agreement scheme. It is one of the fastest curves in ECC, and is not covered by any known patents. The reference implementation is public domain software.

NIST SP 800-90A is a publication by the National Institute of Standards and Technology with the title Recommendation for Random Number Generation Using Deterministic Random Bit Generators. The publication contains the specification for three allegedly cryptographically secure pseudorandom number generators for use in cryptography: Hash DRBG, HMAC DRBG, and CTR DRBG. Earlier versions included a fourth generator, Dual_EC_DRBG. Dual_EC_DRBG was later reported to probably contain a kleptographic backdoor inserted by the United States National Security Agency (NSA).

Dell BSAFE, formerly known as RSA BSAFE, is a FIPS 140-2 validated cryptography library, available in both C and Java. BSAFE was initially created by RSA Security, which was purchased by EMC and then, in turn, by Dell. When Dell sold the RSA business to Symphony Technology Group in 2020, Dell elected to retain the BSAFE product line. BSAFE was one of the most common encryption toolkits before the RSA patent expired in September 2000. It also contained implementations of the RCx ciphers, with the most common one being RC4. From 2004 to 2013 the default random number generator in the library was a NIST-approved RNG standard, widely known to be insecure from at least 2006, containing a kleptographic backdoor from the American National Security Agency (NSA), as part of its secret Bullrun program. In 2013 Reuters revealed that RSA had received a payment of $10 million to set the compromised algorithm as the default option. The RNG standard was subsequently withdrawn in 2014, and the RNG removed from BSAFE beginning in 2015.

<span class="mw-page-title-main">Matthew D. Green</span> American cryptographer and security technologist (born 1976)

Matthew Daniel Green is an American cryptographer and security technologist. Green is an Associate Professor of Computer Science at the Johns Hopkins Information Security Institute. He specializes in applied cryptography, privacy-enhanced information storage systems, anonymous cryptocurrencies, elliptic curve crypto-systems, and satellite television piracy. He is a member of the teams that developed the Zerocoin anonymous cryptocurrency and Zerocash. He has also been influential in the development of the Zcash system. He has been involved in the groups that exposed vulnerabilities in RSA BSAFE, Speedpass and E-ZPass. Green lives in Baltimore, MD with his wife, Melissa, 2 children and 2 miniature dachshunds.

<span class="mw-page-title-main">Crypto Wars</span> Attempts to limit access to strong cryptography

Attempts, unofficially dubbed the "Crypto Wars", have been made by the United States (US) and allied governments to limit the public's and foreign nations' access to cryptography strong enough to thwart decryption by national intelligence agencies, especially the National Security Agency (NSA).

References

  1. 1 2 3 4 5 Ball, James; Borger, Julian; Greenwald, Glenn (September 5, 2013). "US and UK spy agencies defeat privacy and security on the internet". The Guardian .
  2. 1 2 3 4 5 Perlroth, Nicole; Larson, Jeff; Shane, Scott (September 5, 2013). "The NSA's Secret Campaign to Crack, Undermine Internet Security". ProPublica.
  3. "Computer Network Exploitation vs. Computer Network Attack - Schneier on Security". www.schneier.com. Retrieved 2016-09-11.
  4. Sean Michael Kerner (2013-09-09). "NSA Bullrun, 9/11 and Why Enterprises Should Walk Before They Run". Eweek.com. Retrieved 2014-01-23.
  5. 1 2 3 4 5 6 Perlroth, Nicole; Larson, Jeff; Shane, Scott (2013-09-05). "N.S.A. Able to Foil Basic Safeguards of Privacy on Web". New York Times. Retrieved 16 April 2015.
  6. "Edward Snowden Reveals Secret Decryption Programs". International Business Times. 2013-09-06. Retrieved 16 April 2015.
  7. Mike Godwin (May 2000). "Rendering Unto CESA: Clinton's contradictory encryption policy". Reason. Retrieved 2013-09-09. [...] there was an effort to regulate the use and sale of encryption tools, domestically and abroad. [...] By 1996, the administration had abandoned the Clipper Chip as such, but it continued to lobby both at home and abroad for software-based "key escrow" encryption standards.
  8. "Administration Statement on Commercial Encryption Policy". July 12, 1996. Retrieved 2013-09-09. Although we do not control the use of encryption within the US, we do, with some exceptions, limit the export of non-escrowed mass market encryption to products using a key length of 40 bits.
  9. ("NSA is Changing User's Internet Experience.") Info Security Institute
  10. "Secret Documents Reveal N.S.A. Campaign Against Encryption". New York Times.
  11. "New York Times provides new details about NSA backdoor in crypto spec". Ars Technica. 2013.
  12. Matthew Green (2013-09-20). "RSA warns developers not to use RSA products".
  13. Menn, Joseph (December 20, 2013). "Exclusive: Secret contract tied NSA and security industry pioneer". Reuters. San Francisco. Archived from the original on September 24, 2015. Retrieved December 20, 2013.
  14. Reuters in San Francisco (2013-12-20). "$10m NSA contract with security firm RSA led to encryption 'back door' | World news". theguardian.com. Retrieved 2014-01-23.{{cite news}}: |author= has generic name (help)
  15. "That earth-shattering NSA crypto-cracking: Have spooks smashed RC4?". The Register. 2013-09-06. Retrieved 16 April 2015.
  16. "Google strengthens its SSL configuration against possible attacks". 2013-11-19. Retrieved 16 April 2015.
  17. Goodin, Dan (2013-12-10). ""We cannot trust" Intel and Via's chip-based crypto, FreeBSD developers say". Ars Technica . Retrieved 2014-01-23.
  18. Security News (2013-09-10). "Torvalds shoots down call to yank 'backdoored' Intel RdRand in Linux crypto". The Register .
  19. Tim Bray, Google Identity Team (July 2013). "Google certificates upgrade in progress". Google Developer Blog.{{cite web}}: |author= has generic name (help)
  20. Schneier, Bruce (5 September 2013). "The US government has betrayed the internet. We need to take it back". The Guardian . Retrieved 9 January 2017.
  21. John Gilmore (6 Sep 2013). "Opening Discussion: Speculation on 'BULLRUN'". The Mail Archive. The Cryptography Mailing List. the big companies involved ... are all in bed with NSA to make damn sure that working end-to-end encryption never becomes the default on mobile phones
  22. Michael Riley (2014-04-11). "NSA Said to Have Used Heartbleed Bug, Exposing Consumers". Bloomberg.com. Bloomberg.
  23. Ward, Mark (6 September 2013). "Snowden leaks: US and UK 'crack online encryption'". BBC News. Retrieved 6 September 2013.