How the NSA weakened an encryption device

The Dutch TX-1000 pocket teletype initially encrypted using the DES method. But then the NSA enforced a different method. A new research paper shows that it was easy to crack.

As anyone interested in crypto probably knows, the NSA tried for decades to prevent the spread of encryption technology. Even the book “The Codebreakers” (1967) by David Kahn was not supposed to be published because the then little-known authority vetoed it. Only when Kahn defanged his book in some places was he finally allowed to publish it.

Short keys and publication bans

There are numerous other examples in which the NSA intervened against effective cryptotechnology. For example, the key length (56 bits) of the DES encryption method, which was already modest at the time, was also fixed at the instigation of the state eavesdroppers in the early 1970s. Originally, it was supposed to be 128 bits.

As soon as the DES was in the bag, the scientists Ron Rivest, Adi Shamir and Leonard Adleman invented the RSA encryption method named after them. The NSA quickly suspected that this would revolutionize cryptology. So it tried to prevent the three inventors from publishing it – in vain, because too many people already knew about it.

Things became grotesque in 1987, when U.S. investigators (presumably again at the instigation of the NSA) threatened the three Israeli cryptologists Amos Fiat, Adi Shamir and Uriel Feige with a prison sentence if they published a method they had developed. At that time, the method had long been in the public domain. Apart from that, it had been developed in Israel, not in the USA. The US investigators dropped their threat after only two days.

The manipulated pocket teletype

In 2019, Paul Reuvers and Marc Simons reported on their website Cryptomuseum about another case of this kind, unknown until then. It involved a device called the PX-1000, which was a pocket-sized teleprinter that also supported encrypted message transmission. According to Paul and Marc, Nelson Mandela was one of the users of this device.

Quelle/Source: Cryptomuseum

The PX-1000 was developed from 1980 to 1982 by a company called “Text Lite” in Amsterdam. Among others, it was marketed by Philips. The encryption method that the PX-1000 supported was the aforementioned DES. Today it is possible to crack this algorithm by trying all the keys, but at that time only financially strong secret services or military organizations managed to do so, if at all.

In 1984, the version PX-1000Cr was released, which used a different encryption method. As Paul and Marc reported on their site, this change did not come about by chance. Rather, the NSA had induced Philips to use a presumably much weaker encryption method instead of DES (but it doesn’t have a name that I know of). Once again, the NSA had succeeded in hindering the spread of effective cryptography.

Paul and Marc succeeded in reconstructing how the NSA method works. Unsurprisingly, it is a stream cipher based on linear feedback shift registers (LFSRs). LFSRs have been the method of choice for decades when designing encryption hardware. One LFSR (usually more than one is used; in the case of the PX-1000Cr, there are three) can be used to generate a random sequence in a simple and inexpensive way, which is then added to the plaintext (as with the one-time pad). An LFSR method was used in GSM cell phones, for example.

However, it is known that an LFSR-generated random sequence is not quite as random as a cryptologist would wish. It is therefore far from easy to construct a secure encryption scheme from LFSRs. In any case, the GSM cipher algorithm in question has been cracked.

When the NSA prescribed an LFSR procedure for the PX-1000Cr, however, security gaps were, to all appearances, deliberate. However, Paul and Marc were initially unable to say whether these really existed and how they could be exploited.

NSA procedure cracked

At the end of 2021, Paul and Marc received an e-mail from the German computer scientist Stefan Marsiske. He claimed that he had cracked the NSA procedure of the PX-1000Cr. A few weeks later, Marsiske visited them in Eindhoven and demonstrated his attack. In fact, he was able to decode a 17-letter message in less than 4 seconds without any additional information. It doesn’t get much more insecure than that.

On February 15, 2022, Stefan Marsiske published an article describing his attack in “Proof-of-Concept or Get The F*ck Out” (on page 59), which I have not seen before. There is some additional information on Marsiske’s blog. As far as I understand it, Marsiske converted the encryption scheme into a Boolean function, which he was able to solve using a SAT solver.

Quelle/Source: Marsiske

Such an attack should not actually lead to success with a modern encryption method – unless, of course, that is exactly what is intended. In any case, congratulations to Stefan Marsiske for this great crypto analysis.

Cold War crypto

The manipulated pocket teletype thing has to be seen against the background of the Cold War, of course. The cryptography history of the Cold War is a fascinating topic, but only small parts of it have been researched so far. Most of the information on it is still classified. I am curious to see what else will come to light in the coming years. Undoubtedly, we will learn about further manipulation actions of the NSA.

If you want to add a comment, you need to add it to the German version here.
Follow @KlausSchmeh

Further reading: An unsolved cryptogram from the home of the NSA

Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/