A Brief History of NSA Backdoors.
In response to the recent revelations about the NSA backdooring RSA libraries I’ve compiled a brief, incomplete, history of NSA backdoors. Help me make it better by emailing corrections and additions to email@example.com.
Update: added Actel backdoor, Update 2: There is a hackernews thread for discussion.
1946-1970, The Ultra Secret: After WW2, the British Empire sold captured German Enigma cipher machines to many allied countries and former colonies1. The US and the UK had broken Enigma but had kept this fact secret so that countries would use these broken ciphers. To clarify: the British sold machines they knew they could break to allied nations, then the US and the UK spied on those countries for nearly 30 years exploiting the weaknesses in those machines.
1957 - Present, The Boris Project: In 1957 William Friedman of the NSA met with his old friend Boris Hagelin. The purpose of their meeting was to begin “the Boris Project”, in which Crypto AG ciphers would be weakened and backdoored so that the NSA could listen to NATO communications (there is some evidence that suggests that the Boris Project predates this meeting). The meeting was first made public in the biography of Friedman, “The Man Who Broke Purple” 2. Further details were made public with the publication of the "The Puzzle Palace" including letters showing Friedman’s concern about direction of the project3. From interviews with ex-employers we know that the addition of backdoors to Crypto AG ciphers occurred no later, and possibility earlier, than the 1970’s and likely continues to the present day4. These backdoors included covert channels that allowed full key reconstruction5.
Slowly the world figured out that Crypto AG was not a reliable vendor of cryptographic hardware. In 1986 Reagan tipped off the Libyans that the US could decrypt their communications by talking about information he could only get through Libya decrypts on TV6. In 1991 the Iranians learned that the NSA could break their diplomatic communications when transcripts of Iranian diplomatic communications ended up in a French court case7. In 1992 Iranians got so upset with Crypto AG that they charged a Crypto AG salesman with espionage8. Although, despite this evidence, the Iranians appear to have continued to use Crypto AG machines for diplomatic communications until, and perhaps beyond, 20039. In 2004 Ahmed Chalabi was accused of selling the Iranians the methods by which the US was breaking their codes. It is speculated that this might have been information on Crypto AG backdoors or weaknesses10.
1979 - Present, DES: The Data Encryption Standard was altered by the NSA to make it harder to mathematically attack but easier to attack via Brute Force methods. The original version of DES, called Lucifer, used a block and key length of 128-bits and was vulnerable to differential cryptanalysis. NSA requested that the already small DES key size of 64-bits be shrunk even more to 48-bits, IBM resisted and they compromised on 56-bits11. This key size allowed the NSA to break communications secured by DES.
1993, Clipper Chip: The NSA was deeply concerned with the public adoption by Americans of cryptography that they couldn’t break. In 1993 they proposed that voice communication be secured with an encryption chip called “the Clipper Chip”. The Clipper Chip was backdoored such that the NSA could, at will, break any communication secured by the Clipper Chip. Unlike most of the backdoors in this list the NSA announced that the presence of the backdoor. Due to its known insecurity the Clipper Chip was never widely adopted.
1997 Lotus Notes: The NSA requested that Lotus weaken its cryptography so that the NSA could break documents and emails secured by Lotus notes12. This Software was used by citizens, companies and governments worldwide1314.
200? - Present, Actel ProASIC3 FPGA: In 2012 Skorobogatov and Woods discovered that Actel military grade FPGA’s contained a backdoor. The researchers were able to reverse engineer the key such that they could exploit the backdoor15. This chip is used in US weapon systems, nuclear power plants and transportation16. All other Actel chips appear to have this backdoor as well17. At first there was some concern that the backdoor was planted by a foreign government but it was revealed that Actel, an american company, intentionally added this backdoor[^24].
While there is no smoking gun linking this backdoor to the NSA (at least not yet), it seems implausible to me that a US Company would design a complex backdoor and insert it into chips used in critical US systems without US government approval. Additionally, if Actel had created this backdoor without US approval I would expect more of a response from the US government. The US response has been, to my knowledge, complete silence on the issue.
2004 - 2013, Dual_EC_DRBG: Dual Elliptic Curve Deterministic Random Bit Generator[ or Dual_EC_DRBG is a random number generator created by the NSA. It is designed so that if the NSA selected the internal constants carefully, they could generate a secret key which would allow them to break encryption schemes that relied on Dual_EC_DRBG for security. This property of Dual_EC_DRBG was discovered in 2006 by Brown and rediscovered by Shumow and Ferguson in 2007 leading to public speculation that Dual_EC_DRBG was backdoored18. In 200419 the NSA paid RSA security 10 million dollars20 to add Dual_EC_DRBG as the default choice in some of its libraries. The NSA then used the fact that RSA was using Dual_EC_DRBG to get it approved as a NIST standard.
2013, Enabling for Encryption Chips: In the NSA’s budget request documents released by Edward Snowden, one of the goals of the NSA’s SIGINT project is to fully backdoor or “enable” certain encryption chips by the end of 201321. It is not publicly known to which encryption chips they are referring.
2013, Trusted Computing Platforms/Modules: A resource in the same, previously mentioned, budget request is the exploitation of foreign Trusted Computing Platforms and technologies22. There has been some concern expressed in Germany that the Microsoft TCM 2.0 could be backdoored by the NSA23.
I have an older post in which I speculate about designing a cipher with a backdoor.
"The British government insisted upon this silence because it has given the thousands of Enigma machines that it had gathered up after the end of the war to its former colonies as they gained independence and needed secure systems of communication." p 979 The Codebreakers by David Kahn ↩
"The reason for concern, it was stated in one of several attempts to see what had been written, was that the book might deprive the NSA of the daily information enabling it to read the secret messages of other NATO countries, a process subsequently described as the clandestine reading of all NATO countries’ messages. The ability to read all NATO messages was no doubt a natural aim in the aftermath of Suez. It had then seemed that while NSA was able to monitor and decipher many of the British and French communications, the Agency was not able to decipher them all.[..] Friedman’s problem was basically that of seeing into the cryptological future, of estimating what measures, overt and convert, would have to be taken by America in the years ahead to counter new machines that might be introduced by Europe’s various makers of ciphermachines [..] It is Significant that from 1957 onwards Friedman’s private correspondence shows a growing disillusion not only with the NSA — perhaps an inevitable reaction by a master of cryptography — but also with some implications of the profession to which he had devoted his life." - The Man Who Broke Purple by Ronald Clark ↩
"With regard to the connection with Hagelin, evidence can be seen in a revealing letter dated August 8, 1958, from Friedman to Howard Engstrom, who had left office as deputy director of NSA only a few days before. In his letter, Friedman indicated his frustration over the handling of the "Boris" project and the fact that it was apparently being taken out of his hands", The Puzzle Palace by James Bamford ↩
"One former engineer says he first heard that the machines were being "adjusted" from Boris Hagelin Jr., son of the company’s founder and sales manager for North and South America. When they were stranded in Buenos Aires, Argentina, for a few days in 1970, the younger Mr. Hagelin complained to the engineer about being forced by his father to rig the machines, the engineer says. Back in Switzerland, the engineer confronted the elder Mr. Hagelin. The old man, he says, confirmed the deception and justified it with a theory of political paternalism. "He said different countries need different levels of security," recalls the engineer, who asked not to be identified. While the United States and other leading Western countries required completely secure communications, Mr. Hagelin explained, such security would not be appropriate for the Third World countries that were Crypto’s customers. [..] According to this engineer and several others, the alterations in the designs of various machines were detectable, if at all, only to an expert in cryptologic mathematics. Sometimes the mathematical formulas that determined the strength of the encryption contained certain flaws making the codes rapidly breakable by a cryptanalyst who knew the technical details. In other cases, the designs included a "trapdoor" — allowing an insider to derive the numerical "key" to the encrypted text from certain clues hidden in the text itself." - No Such Agency Part Four: Rigging the Game by Scott Shane and Tom Bowman, Sun Staff ↩
"Depending on the projected usage area the manipulation on the cryptographic devices were more or less subtle, said Polzer. Some buyers only got simplified code technology according to the motto "for these customers that is sufficient, they don’t not need such a good stuff." In more delicate cases the specialists reached deeper into the cryptographic trick box: The machines prepared in this way enriched the encrypted text with "auxiliary informations" that allowed all who knew this addition to reconstruct the original key. The result was the same: What looked like inpenetrateable secret code to the users of the Crypto-machines, who acted in good faith, was readable with not more than a finger exercise for the informed listener." - Who is the authorized fourth, DER SPIEGEL issue 36/96 pages 206-207 ↩
"First, U.S. President Ronald Reagan informed the world on national television that the United States was reading Libyan communications. This admission was part of a speech justifying the retaliatory bombing of Libya for its alleged involvement in the La Belle discotheque bombing in Berlin’s Schoeneberg district, where two U.S. soldiers and a Turkish woman were killed, and 200 others injured. Reagan wasn’t talking about American monitoring of Libyan news broadcasts. Rather, his "direct, precise, and undeniable proof" referred to secret (encrypted) diplomatic communication between Tripoli and the Libyan embassy in East Berlin." - NSA, Crypto AG, and the Iraq-Iran Conflict by J. Orlin Grabbe ↩
"Next, this leak was compounded by the U.S. demonstration that it was also reading secret Iranian communications. As reported in Switzerland’s Neue Zurcher Zeitung, the U.S. provided the contents of encrypted Iranian messages to France to assist in the conviction of Ali Vakili Rad and Massoud Hendi for the stabbing death in the Paris suburb of Suresnes of the former Iranian prime minister Shahpour Bakhtiar and his personal secretary Katibeh Fallouch." - NSA, Crypto AG, and the Iraq-Iran Conflict by J. Orlin Grabbe ↩
" In 1992, Iran arrested Hans Buehler, a Crypto AG employee, on suspicion that Crypto AG had installed back doors in the encryption machines it sold to Iran — at the request of the NSA. He proclaimed his innocence through repeated interrogations, and was finally released nine months later in 1993 when Crypto AG paid a million dollars for his freedom — then promptly fired him and billed him for the release money. At this point Buehler started asking inconvenient questions about the relationship between Crypto AG and the NSA." - Breaking Iranian Codes Crypto-Gram by Bruce Schneier ↩
"Tarfa: As you know, Khomeini did not use telephones, but we monitored the communications between the Iranian ministry of foreign affairs and the Iranian embassies around the world, because they were using the same machine as the military. We would intercept the information from the Iranian embassies in Turkey, Afghanistan, Pakistan, and any instructions from the ministry of foreign affairs to the embassies. We sent this information to the intelligence service to be analyzed. For example, when the Taliban had control in Mazar-e-Sharif, [in 1998] we had this information. We even followed up on Iranian operations beyond Iran. We exposed Iranian sources in Iraq through the embassy. Iran continued to use the T450 at least until the Americans occupied Iraq in 2003. Murray: We now know every major power involved in World War II was reading some, if not all, of the major codes of both their enemies and their allies. The Swiss T450 machine was from that era. It is a bit shocking that Iran continued using this machine into 2003." - Saddam’s Generals: Perspectives of the Iran-Iraq War., by Kevin M. Woods, et al ↩
"Ahmed Chalabi is accused of informing the Iranians that the U.S. had broken its intelligence codes. What exactly did the U.S. break? How could the Iranians verify Chalabi’s claim, and what might they do about it? This is an attempt to answer some of those questions. [..] To protect their secrets, Iranian intelligence — like the leaders of all countries — communicate in code. These aren’t pencil-and-paper codes, but software-based encryption machines. The Iranians probably didn’t build their own, but bought them from a company like the Swiss-owned Crypto AG. Some encryption machines protect telephone calls, others protect fax and Telex messages, and still others protect computer communications." - Breaking Iranian Codes Crypto-Gram by Bruce Schneier ↩
"NSA worked closely with IBM to strengthen the algorithm against all except brute force attacks and to strengthen substitution tables, called S-Boxes. Conversely, NSA tried to convince IBM to reduce the length of the key from 64-bit to 48-bits. Ultimately, they compromised on a 56-bit key." Book III: Retrenchment and Reform by Tom Johnson ↩
"Before the US crypto export regulations were finally disolved the export version of Lotus Notes used to include a key escrow / backdoor feature called differential cryptography. The idea was that they got permission to export 64 bit crypto if 24 of those bits were encrypted for the NSA’s public key. The NSA would then only have the small matter of brute-forcing the remaining 40 bits to get the plaintext, and everyone else would get a not-that-great 64 bit key space (which probably already back then NSA would have had the compute power to brute force also, only at higher cost)." NSA’s Backdoor Key from Lotus-Notes ↩
"Giant US software manufacturer Lotus has been lowering the profile of information about how they have installed an NSA-only trapdoor into e-mail and conference systems used by many European governments, including the German Ministry of Defence, the French Ministry of Education and Research and the Ministry of Education in Latvia." Only NSA can listen, so that’s OK by Duncan Campbell ↩
"One of the world’s most widely used e-mail programs, the American Lotus Notes, is not so secure as most of its 400,000 to 500,000 Swedish users believe. To be sure, it includes advanced cryptography in its e-mail function, but the codes that protect the encryption have been surrendered to American authorities. With them, the U.S. government can decode encrypted information. Among Swedish users are 349 parliament members, 15,000 tax agency employees, as well as employees in large businesses and the defense department.
I didn't know that our Notes keys were deposited (with the U.S.). It was interesting to learn this,'' says Data Security Chief Jan Karlsson at the [Swedish] defense department. Gunnar Grenfors, Parliament director and daily e-mail user, says,I didn’t know about this—here we handle sensitive information concerning Sweden’s interests, and we should not leave the keys to this information to the U.S. government or anyone else. This must be a basic requirement.”” Secret Swedish E-Mail Can Be Read by the U.S.A. by Fredrik Laurin, Calle Froste, Svenska Dagbladet ↩
"One could possibly argue that the backdoor we discovered is a bug or something overlooked by the developers. However, this is not the case as we performed intensive investigation into this problem and found proof that the backdoor was deliberately inserted and even used as a part of the overall security scheme. We cannot disclose all of these findings at present due to a confidentiality agreement." - Breakthrough silicon scanning discovers backdoor in military chip (DRAFT of 05 March 2012) by Skorobogatov and Woods ↩
"This particular chip is prevalent in many systems from weapons, nuclear power plants to public transport. In other words, this backdoor access could be turned into an advanced Stuxnet weapon to attack potentially millions of systems. The scale and range of possible attacks has huge implications for National Security and public infrastructure."" China not to blame for backdoor in US military chip Security experts, along with researcher who found the backdoor, say no evidence of China’s involvement by Taylor Armerding ↩
"We analysed other Microsemi/Actel products and found they all have the same deliberate backdoor." - Breakthrough silicon scanning discovers backdoor in military chip (DRAFT of 05 March 2012) by Skorobogatov and Woods ↩
"What Shumow and Ferguson showed is that these numbers have a relationship with a second, secret set of numbers that can act as a kind of skeleton key. If you know the secret numbers, you can predict the output of the random-number generator after collecting just 32 bytes of its output. To put that in real terms, you only need to monitor one TLS internet encryption connection in order to crack the security of that protocol. If you know the secret numbers, you can completely break any instantiation of Dual_EC_DRBG." - Did NSA Put a Secret Backdoor in New Encryption Standard? by Bruce Schneier ↩
"Curry told WIRED that the company added the Dual EC DRBG algorithm to its libraries in 2004 and 2005 at a time when elliptic curve algorithms were becoming the rage and were considered to have advantages over other algorithms." RSA Tells Its Developer Customers: Stop Using NSA-Linked Algorithm by Kim Zetter ↩
"Undisclosed until now was that RSA received $10 million in a deal that set the NSA formula as the preferred, or default, method for number generation in the BSafe software, according to two sources familiar with the contract." Exclusive: Secret contract tied NSA and security industry pioneer by JOSEPH MENN ↩
"(TS//SI//REL TO USA, FVEY) Complete enable for [REDACTED] encryption chips used in Virtual Private Network and Web encryption devices [CCP_00009]" - (U) COMPUTER NETWORK OPERATIONS (U) SIGINT ENABLING ↩
"(TS//SI//REL TO USA, FVEY) Exploit foreign trusted computing platforms and technologies." - (U) COMPUTER NETWORK OPERATIONS (U) SIGINT ENABLING ↩
"The BSI’s announcement explained that "from the perspective of the BSI, the use of Windows 8 in combination with a TPM 2.0 is accompanied by a loss of control over the operating system and the hardware used" (per the translation). It suggested that the combination of Windows 8 and TPM 2.0 could enable "sabotage" by third parties. [..] The Zeit Online article cites an interview (in German) with Dr. Rüdiger Weis of the Beuth Hochschule für Technik Berlin institution who said that "together with the procedures implemented by Microsoft within Windows 8 (particularly secure boot) the control over its own hardware and software is removed from largely the user" (Bing translation). Weis added that "the TPM chip for the NSA is a dream" (translation), in the wake of Edward Snowden’s disclosures about broad U.S. National Security Administration spying." - German Agency Sees Security Issues with Windows 8 and TPM 2.0 by Kurt Mackie ↩
Three Great Games I Played at the Boston Festival of Indie Games.
Synthesis is a very pretty game, but watching other people play it didn’t look that engaging. Synthesis has to be played to be understood, it is strangely, oddly, engaging. It has serious flow. Synthesis is a continuous graph based cellular automata sandbox game. If you ever wasted a few hours playing with Conway’s Game of Life, this is the game for you. It takes everything fun about clicking randomly, pushing start and seeing unexpected emergent patterns and turns it up to 11. For such a deep game the UI is simple but allows complex actions such as writing novel automata and introducing them into the world. Think Steven Wolfram’s A New Kind of Science on DMT in game form.
PWN Combat Hacking:
PWN Combat Hacking has two players compete to take over (hack) nodes (computers) in a graph (network). The game plays and looks suspiciously like the final hacker battle in the 1995 film Hackers. PWN has simple rules that result in well executed gameplay. Sadly I haven’t been able to play it since FIG because attempting to update OSX from 10.7 to 10.8 (PWN only works on 10.8) resulted in catastrophic harddrive failure.
Nika is a board game inspired by Peloponnesian War. It manages to abstract both the tactical elements of hoplites fighting in Phalanx and strategic elements. These strategic elements include cooperation between allied armies, and trade-offs between defense and offense. More incredibly it does this with a very simple set of rules. The game was explained to me and I was off and playing within three minutes. I’ve played more than my fair share of strategic games, I’ve even designed a few. Nika feels different strategically than other games. I couldn’t map it into another game I was good at and that felt wonderful. There is something about Nika that was really fresh and kept me guessing. Wind Catcher Games is planning to sell it in the future by sadly it is not currently available.
Why Google Should Customize your Gmail Login Page to Prevent Phishing.
Disclaimer: The following post is uses Gmail and Google Accounts as a punching bag, but these problems discussed are both widely known, universal to identity providers on the web and not Google’s fault. Gmail has just been chosen to play the victim only due to it’s popularity and general bestness.
Password phishing attacks have been going on for over 25 years and the situation has only gotten worse. This post argues that by using a browser plugin to customize login pages on the client, attacks will have significantly greater difficulty forging believable login pages.
Two Phishing Attacks
I will argue this point by first showing two phishing attacks which would probably fool a fairly sophisticated computer user. These attacks are almost definitely not novel and are probably used in the wild. Compare these attacks to typical advice on preventing phishing. Consider the following two attacks:
Fake OAuth page: Websites will often allow users to authenticate with their google account using OAuth. If they are not logged into their Google account already it will ask them to login1. The workflow looks like this:
- Alice goes to a site that appears to have content that Alice wants.
- To access the content Website requires that Alice authenticates with her Google account before making a purchase.
- Alice clicks ‘authenticate with Google’ and is taken to a Google accounts login screen.
- Alice enters her username and password and is then allowed into the site.
Eve wants to steal Alice’s password so she setups up a website as above but in step 3 Alice is sent to a fake, but realistic looking gmail login page. Alice just gave her username and password away. Eve can interactively check if Alice’s provided a real username/password by supplying it to Gmail to see if it works. If Alice had Two-Factor authentication setup Eve can merely request a verification code from Alice as part of the login request. In fact if Eve wants to change the password and lock Alice out of her own account she can claim that the first verification code that Alice supplied (as part of her second factor) was incorrect and ask for a second one (loading the page for 60 seconds to wait for the first verification token to expire).
Tabnapping: Gmail has a habit of signing users out of their gmail accounts, which has trained users to sign back in at random points during the day. This can be exploited by crafting a page which when it detects that the user is inactive or idle it transforms into a fake gmail page saying that user has been logged out and that they should login again. This general approach is called tabnapping.
- Eve sents Alice a link to a fake Google Doc.
- Alice opens link and goes to bed, while she is sleeping the fake Google Doc rewrites itself so that it looks like a “you’ve been logged out, please login here” Google page.
- Alice wakes up, checks her laptop, logs into the fake Google login page. Game over.
Alice should be able to notice that she is signed into Google in other tabs: As [Google says]:(http://www.google.com/about/company/rewardprogram.html)
"At this time, the ability of malicious web sites to log users out of unrelated web applications is essentially unavoidable; it is a consequence of how the web is designed, and cannot be reliably prevented by any single website.” This means that Eve can log Alice out of her Google Account. In fact Eve can keep logging Alice out until Alice logs into Eve’s fake Google Account.
Alice can tell the difference between the fake login page and the real login page by inspecting the URL: Unfortunately there are really effective ways of making fake but undetectable urls (see also URL redirecting).
Alice uses HTTPS so she is safe: Phishing sites legally acquire valid HTTPS certificates. HTTPS offers zero protection in this scenario, other than the minimal cost to request a cert for a domain they control.
The crux of the problem is that users have no way2 of telling a real Google accounts or Gmail login page from a fake one since the styling of a login page can be easily copied.
Customize/Skin the Login Page: Users will often skin or customize the look of the internal gmail web application by choosing a theme. Google should force new users to choose a unique skin for their ‘trusted’ home computer and persist this skin even when they are not signed into their Gmail account so that the skin will be applied to the login screen for their Gmail account. This skin would persist on the client 3, so an attacker would not be able to learn it by querying Google. Since the attacker can’t learn the skin that user is using, the attacker can’t replicate what the user expects to see. Thus the attacker will have difficulty fooling the user4. An example skin is shown below.
qr-codes: For added security the page could display a qr-code which the user could scan with their mobile phone to log themselves in without typing in a password. Isaac Potoczny-Jones has a neat blog post on using qr-codes as authentication5.
There are several problems with training users to use the look of a website to determine its trustworthiness.
- The unique skin is now acting as a authentication to the user, but browsers and security models are not designed to protect how gmail looks to a user. Screen sharing skype sessions, xss attacks and photos could expose the look of the skin which then an attacker could copy. Since the user now trusts login pages that have their unique skin they will be easier to fool if the skin is compromised.
This is a real risk, but users already use the look of a webpage to judge it’s trustworthiness. Most phishing attacks are not targeted and this would stop these sorts of attacks and seriously complicate more advanced attack.
- The unique skin can not persist across clients. The first time a user uses a computer they have to login to a plain page or a page which has the skin of another user.
This solution probably wouldn’t be that useful for people that use many different computers.
- Chrome already has this functionality in that you can sign into chrome.. Since you are signing into the browser rather than into webpage phishing is impossible.
Unfortunately, signing into Google Chrome does not automatically sign you into all your Google Accounts. Passwords can be saved in Google Chrome, but there are numerous ways to trick someone into entering their password into a realistic looking login screen.
Yes, yes, they can check the certificate of the page and maybe catch a poorly generated cert, but how many times do you check the certificate of the page when you login to Gmail? ↩
This is really the tricky part as an attacker can wipe browser cookies at will. One surefire way would be to use a browser plugin or use the Google Chrome Sync functionality. ↩
All users can be fooled given enough time and effort. ↩
I don’t see any reason why Google is not doing this already. They support Two-Factor authentication. While qr-auth is as vulnerable as username/password schemes, a successful attack only steals a one-use token rather than a username and password. This would be perfect for situations in which someone is concerned about a keylogger. In fact if you combine qr-auth with a browser plugin it becomes more secure than username/password schemes since the plugin can verify if the page is gmail or not. ↩