How the Government Hacks You: Chapter 5

A History of Government Involvement in Creating Encryption

The first modern standard for computer cryptography was established in 1975. A research group at IBM came up with ‘Data Encryption Standard’, also known as DES, and published it in the Federal Register. It was then submitted to the U.S. National Bureau of Standards for ratification.

However, the NBS consulted with the NSA before making their ruling. After the NSA tinkered with the encryption, it was much stronger against differential cryptanalysis, but significantly weakened against brute-force attacks. Experts at the time sounded the alarm, explaining that the drastically reduced 56-bit key size was insufficient to the task.

The government ignored them, of course. Was there direct government tampering with the design of DES? THE NSA seems to think so.

“In 1973 NBS solicited private industry for a data encryption standard (DES). The first offerings were disappointing, so NSA began working on its own algorithm. Then Howard Rosenblum, deputy director for research and engineering, discovered that Walter Tuchman of IBM was working on a modification to Lucifer for general use. NSA gave Tuchman a clearance and brought him in to work jointly with the Agency on his Lucifer modification.” - NSA Declassified Documents

The experts at the time were entirely correct. The S-box did make the standard stronger in normal usage, but the short key length made brute force a realistic possibility. At least for anyone with massive computing power available, such as the government. DES became the U.S. federal standard in November of 1976.

By the late 90’s, public computing power caught up and exceeded what the entire U.S. government had available in the 70’s. Spending only $250,000 (as compared to billions available in government resources) the Electronic Frontier Foundation broke DES with two days of computing time. They did it again the next year with the help of Distributed.net in less than a day. It was clear that the government, with billions at the disposal, could crack DES any time that they wanted. That was likely the case from the start.

It wasn’t until 2001 that the U.S. government announced that they wanted to replace DES. Advanced Encryption Standard (AES) was a far more reasonable key length, variable to lengths of 128, 192, and 256 bits. This move eliminates practical brute force attacks under proper implementation, unless it’s a completely inside job. It’s even symmetrical, so AES is resistant to quantum attacks, which we’ll discuss later. This reflected the U.S. government’s move towards establishing backdoors instead of using inherently bad encryption.

AES has several well known side-channel attacks against systems that leak certain kinds of data. For example, Daniel Bernstein came up with a clever timing attack on systems that leaked clock information. Ashokkumar, Giri, and Menezes from the Indian Institute of Technology came up with an attack that required normal user privilege on the encrypting system, cutting down the side-channel attack time significantly. But the core implementation of AES is sound, on a properly secured system.

In 2013, it looked like the government was back to their old tricks again, this time in the SHA-3 competition. NIST proposed to limit the key length of entries as they pleased, by determining a strength VS speed tradeoff of their own choosing. This caused a maelstrom of protest. It was seen as an attempt to weaken entries against quantum attacks. Eventually, they caved. The winner was Keccak, a sponge-based algorithm with variable key lengths up to 512 bits. But it has yet to see widespread support in the industry.

Defeated Forms of Encryption

"This is the golden age of spying." - Paul Carl Kocher - 2019 Marconi Prize winner for the development of SSL/TLS

Many different types of encryption have come and gone. Some of them were adopted into the mainstream for decades, like DES mentioned above. Others were ‘here today, gone tomorrow’ before they could see wide use. As a public service, we’ll go over some of the most common encryption methods that systems should no longer be using, whether or not a particular government or organization endorses them.

CMEA: Cellular Message Encryption Algorithm was used for securing mobile phones in the U.S. It is massively insecure. The key size is only 64 bits. Despite this, it became a Telecommunications Industry Association (TIA) standard. It can be defeated in 338 plaintexts, for any block size. It was criminally weak, as far as the protection it provided for something as important as mobile phone communications.

A5/1: This encryption had a rough start to life. Originally used in the EU for GSM encryption, it rapidly expanded to be a worldwide cipher, with over 7 billion use cases. That in and of itself was not a bad thing. Broad adoption can bring about needed scrutiny and improve the implementation of encryption measures. But Germany wanted it to be strong, while other countries, including the U.S.A., wanted it to be much weaker. The problem was, the NSA could already crack the strongest version. In the end, though the initial setup was expensive, multiple countries were able to break A5/1. And there was a second problem…

A5/2: In order to export A5/1 to other countries, and for use in markets where ‘strong’ encryption wasn’t allowed, an even weaker version of the cipher was created called A5/2. Predictably, it too was broken, and even more trivially than the original. In 2006, all support was pulled by the major carrier networks.

Triple DES: Though not entirely useless, 3DES should be considered defeated given that it has a known weakness and publicly available details on an attack vector. OpenSSL no longer includes it as an option, as it is considered too weak. It theoretically had 168 bits of key length, but that was effectively reduced to 112 bits because of a meet-in-the-middle plaintext attack, common to ciphers that go multiple rounds with the same algorithm. Certain known chosen-plaintext methods further reduce its security, so much so that NIST considers it to only have an effective 80 bit key length. In short: It can be brute forced, don’t use it for anything serious.

RC5: But not all of RC5. You see, this cipher has a variable key. By crowd sourcing and using distributed Cloud computing, the two weaker key lengths of RC5, the ones using 56-bit and 64-bit keys, have been beaten. It is suggested that the 128 bit block size be used for RC5, as that would take several hundred years to crack using current techniques.

There are many other, lesser known broken ciphers. But the ones listed above have seen a level of mainstream adoption over the past 20 years.

These examples form the core argument against limiting the strength of encryption allowed by a particular government. As plainly demonstrated above, particularly by the RC5 situation, short key lengths render ciphers useless. There’s no compromise to be had in this situation: Encryption either works, or it doesn’t. It either protects privacy, for everyone, or it protects noone.