Project Rubicon: The NSA Secretly Sold Flawed Encryption for Decades

There have been a few moments in the past few years, when a conspiracy theory is suddenly demonstrated to be based in fact. Once upon a time, it was an absurd suggestion that the NSA had data taps in AT&T buildings across the country. Just like Snowden’s revelations confirmed those conspiracy theories, a news in February confirmed some theories about Crypto AG, a Swiss cryptography vendor.

The whole story reads like a cold-war era spy thriller, and like many of those novels, it all starts with World War II. As a result of a family investment, Boris Hagelin found himself at the helm of Aktiebolaget Cryptograph, later renamed to Crypto AG (1952), a Swedish company that built and sold cipher machines that competed with the famous Enigma machine. At the start of the war, Hagelin decided that Sweden was not the place to be, and moved to the United States. This was a fortuitous move, as it allowed Hagelin to market his company’s C-38 cipher machine to the US military. That device was designated the M-209 by the army, and became the standard in-the-field encryption machine.

From M-209 to PDP-11

The CX-52
The CX-52, thanks to Rama, Cc-by-sa-2.0-fr

In an interesting intersection of history, the M-209 caught the interest of Dennis Ritchie and Robert Morris, both Unix pioneers who worked at Bell Labs. Together with James Reeds, they wrote a paper on a statistical cryptanalysis of the cipher, and concluded their technique could decipher an unknown message of at least 2500 characters with almost perfect accuracy, in just a few minutes on a pdp-11.

Ritchie’s written recollection of the matter includes a relevant anecdote. As part of preparing the paper for publishing, the authors also submitted it to the NSA for review. It made enough of an impression that Ritchie and Morris got a visit from a “retired gentleman” from the NSA, sometime around 1978.

According to Ritchie:

…the agency didn’t particularly care about the M-209. What they did care about was that the method that Reeds had discovered was applicable to systems that were in current use by particular governments, and that even though it was hard to imagine that these people would find the paper and relate it to their own operations (which used commercially-available crypto machines)…

The result of that visit was a decision to delay publication indefinitely. As cool as it is to see some Unix heroes show up unexpectedly, perhaps the most interesting element of this anecdote is the reasoning for the unofficial request not to publish: Other governments are using commercially-available crypto machines that were vulnerable to this attack, and the NSA wanted to keep that information quiet.

The Handshake with the NSA

After the success of the M-209, Hagelin moved back to Sweden and re-established his company there, before finally moving himself and the company to Switzerland. The CIA and NSA (then called the AFSA) kept tabs on the activities of Hagelin and Crypto AG. A new machine was under development, the CX-52, and that worried the spooks back in the states.

You see, even during the war, it had been discovered that a C-38 encoded message could be broken in just a few hours. The new CX-52 was extremely difficult to decrypt, meaning that the NSA would lose their all-seeing eye into communications around the world. The NSA had a secret weapon in the form of William Friedman, who was chief cryptologist for the NSA, as well as a personal friend to Hagelin. In 1951, at the Cosmos Club in Washington D.C., Friedman made an informal proposal to Hagelin: Crypto AG would restrict sales of the newer, more secure machines to a list of approved customers, and the US would reimburse him for the lost sales. The men shook hands on the gentlemen’s agreement, and then waited for the slow process of making that agreement official.

The wheels of government turn slowly indeed, and it was February of 1955 before the agreement was finalized. In addition to the money and sales restrictions, the NSA would produce the instruction manuals for the improved machines. It’s been suggested that the NSA produced manuals included intentionally misleading instructions, intended to weaken the encryption of Crypto AG machines for specific users.

Building Backdoors

In 1967, Crypto AG released the H-460, an electronic encryption machine. This should have represented another massive leap in encryption strength over the older mechanical models, and it likely would have been such a leap, had the NSA not been the primary designer of the new system. How did they compromise the security of the system? It appears that they manipulated the random number generator at the heart of the system, such that at a known interval, the “random numbers” would repeat. The list of approved customers received units without the compromised generator, but H-460 devices sent to the rest of the world had this intentional weakness built-in from the factory. When the NSA intercepted a communication that had been encrypted using a weakened H-460, they could decrypt it in seconds rather than months.

1950’s era Crypto AG Device. Image by Cory Doctorow, CC BY-SA 2.0

Does a weakened random number generator sound familiar? How about the RDRAND instruction in Intel processors, just a few years ago? It was suggested that the random number generating instruction in Intel chips was untrustworthy. There were fireworks in the Linux kernel development, but ultimately, several different communities began treating RDRAND output as untrustworthy.

The Buyout

Though it wasn’t entirely without conflict, the agreement between the NSA and Hagelin lasted until his retirement. Boris Hagelin had planned to pass his company to his son, Bo Hagelin, but Bo died in a car crash in the Washington D.C. area in 1970. Shortly after this event, Boris Hagelin stepped down from leadership of the company, and a buyout of the company was carried out. A series of shell companies were used to mask the identity of the new owners of Crypto AG, but recently declassified documentation reveals the truth of the matter. Crypto AG was purchased in a joint venture between the CIA and the West German BND. From 1970 until 2018, one of the foremost providers of encryption equipment for governments around the world was secretly a covert operation run by these two intelligence agencies. This operation was eventually known as Rubicon.

The details of Rubicon were chased down by a group of journalists, as well as the Crypto Museum in the Netherlands. Most of the information presented here is distilled from the Crypto Museum and The Washington Post story. You may be looking for a link to the declassified CIA documentation, but unfortunately only snippets are available. From the Washington Post: “The Post was able to read all of the documents, but the source of the material insisted that only excerpts be published.”

An unexpected benefit was that Crypto AG was a profitable business. The paperwork of the business was handled by the BND, who then shared the profits with the CIA. This arrangement persisted until 1993, when the CIA bought out the German involvement in the project. By this time, the financial profitability of Crypto AG had faded, but many governments were still using their products.

Real World Uses of the Crypto AG Backdoor

We have a few glimpses into the intelligence that Crypto AG helped to gather: In 1978, the Egyptian president came to Camp David to negotiate a peace accord, and his communications were “secured” using Crypto AG hardware. In 1979, after the Iranians captured American hostages, president Carter’s negotiations relied heavily on intelligence captured through Crypto AG hardware.

An example that included some fallout was the bombing of a West Berlin club in 1986. Because of this program, the NSA was able to conclusively determine that Libya was behind the bombing. The decision was made to be precise when revealing what the US knew about the bombing coordination, giving hints to the nature of NSA capabilities.

Leaking Information

As you might imagine, it was impossible to keep the NSA’s involvement in Crypto AG a perfect secret. Peter Frutiger, for example, was an engineer for the company who figured out that something was wrong with Crypto AG products. He made a trip to Syria to troubleshoot complaints, and proceeded to fix the vulnerable devices he found there. For his trouble, the Crypto AG CEO fired Frutiger as soon as his fix was discovered.

Mengia Caflisch was another employee, too smart for her own good, who made life difficult for her unseen overlords. Together with other researchers from the company, she discovered some of the weaknesses of Crypto AG’s products, and tried to improve their security.

In response to company engineers doing their job too well, the CIA began looking for someone to keep the engineers in line. They settled on Kjell-Ove Widman, A mathematics professor from a Swedish university. More importantly, Widman was a famous cryptographer was sympathetic to the US. His recruitment in 1979 was rather straightforward, and Widman served as the CIA’s man until 1994. As a somewhat famous cryptographer, his word became law in the company, keeping the rest of the company in line. Widman helped to develop the next generation of compromised algorithms, aiming for flaws that wouldn’t show up in a statistical analysis, and yet could be easily explained as human error. He got more than he bargained for, as Widman was one of the representatives that went to Argentina in 1982, to explain vulnerabilities in Crypto AG devices. The gambit worked — the vulnerable algorithm was replaced by a more advanced, but still vulnerable cipher, and Argentina remained a Crypto AG customer.

The tensions between Crypto AG and customers came to a head in 1992. Iranian communications had been vulnerable for a decade, and Iran was slowly becoming wise to the con. Hans Buehler, a Crypto AG sales rep, was detained in Tehran, and interrogated about company products. The only problem? As far as Buehler knew, his company was legitimate. Nine months passed while the CIA and German BND argued over what to do. The US policy was to never pay ransom demands, so the CIA was unwilling to be a part of bailing out Buehler. Finally the German agency opted to provide the ransom money, and secured Buehler’s release. This event proved to be the beginning of the end for the CIA-BND partnership. In 1994, the CIA bought out the BND’s ownership of Crypto AG.

The End of the Story?

The declassified information dries up around this era. Thanks to news reporting in 1995 and the 2014 release of the Friedman archives, some of this story was already known. The 2018 sale of the remaining Crypto AG assets seems to have been the end of the CIA’s involvement with the company. Two companies, CyOne and Crypto International AG, were created from the ashes of Crypto AG. While it appears that neither of these new companies are actively compromised, their products may still contain compromised cryptography, and so should still be considered untrustworthy.

It’s unclear whether any governments are still using CIA-era Crypto AG hardware for their communications, but the inertia of governments and red tape would lead one to assume that these products are still in use somewhere. Beyond that possibility, we have to wonder whether other proprietary encryption products have been similarly compromised. It’s even conceivable that an open source encryption product has been subtly designed to be vulnerable.

Operation Rubicon was considered “the intelligence coup of the century” by the CIA, and it’s not hard to understand why. The question we are left with, is what the intelligence coup of the 21st century will look like, and will we see it coming, or only learn about it years later.