The Strange Tail of Nelson Mandela, The NSA and A Backdoor Cipher

The Strange Tail of Nelson Mandela, The NSA and A Backdoor Cipher

I love cipher cracking, and have tried to implement most of the well-known ciphers here. Along with this, I also am intrigued by a very human intervention: the crypto backdoor. Perhaps, its a child-like trait, and where children often love sending secret messages to their friends? But, like a child, we often loved listening to the secret conversations of our friends and in spying on those we were not suppose too — it was fun and part of learning about our world. We, though, as adults, have learnt to control our desire to spy on others — but it is still inside us.

Overall, the skill of inserting a backdoor often requires a great deal of knowledge of cipher implementations, and which then creates a trapdoor that allows a privileged person in, but not others. It is a magic wand, and which allows the ‘good’ in, and the ‘bad’ out. The deception is that anyone doing a cryptoanalysis, cannot see where the backdoor has been installed. These days, luckily, our trapdoor method is provided by public key encryption, and where the private key is the magic wand.

One previously suspected backdoor is the NSA-derived PC-1000Cr encryption method. And, so, just this week, Stefan Marsiske announced that he had finally broken the method, and has managed to crack the cipher in just 4 seconds with only 17 characters of ciphertext. His main software tool was the Python integration of the Z3 algebraic solver program, and his GitHub is here and also from his blog.

Philips and the NSA

The story of the PX-1000Cr algorithm goes back to the early 1980s. At the time, Philips (the Dutch technology company) had released a messaging terminal (a pocket Telex machine) and which integrated the newly defined DES encryption method:

It is thought that the NSA was so upset with the integration of DES, that they went out and bought all the stock that they could. But, Philips and the NSA seems to have had a good relationship at the time, and where Philips even implemented the SAVILLE cipher within a range of cryptophones. But, the NSA didn’t much like the usage of the DES algorithm that IBM had created. With its 56-bit encryption, it was fairly strong in its security and required considerable amounts of computing power to crack even a single encryption key. And, to this day, the DES method has not been broken, but where the 56-bit key size can now be broken by brute force with the use of GPUs or ASICs. And, so, the NSA asked for DES to be replaced by PX-1000Cr in the PX-1000 product. And, many thought that the new method had a backdoor in it.

Nelson Mandela and secret communications

Philip’s revised product appeared on the market in 1984 (!!!), and it is thought that, in 1986, the PX-1000 was used in Operation Vula. This involved the tapping of communications between Nelson Mandela and anti-apartheid groups. For this Nelson used secret communications to prepare for his expected release from prison. While there is no evidence that the weekend cipher was targeted at Nelson Mandela, there are some who believe that it could have been. But, it may have been that Nelson Mandela and the associated groups managed to get hold of the older version of the device, and which contained the DES implementation. This would have not allowed the NSA to read the encrypted communications.

So here’s Stef talking about the cipher:

DES

DES is based on the Feistel cipher which was named after Horst Feistel from IBM. It uses essentially the same encryption and decryption process, where the key application is just reversed. The basic structure is given below and where we split the input data into blocks. Each block is then split into two (left and right):

If you want to find our more about its history, try here:

Unlike the PX-1000Cr algorithm, DES remains free of any major backdoors.

Conclusions

In the world of cryptography and ciphers, it's machine v humans, and the human brain still shows it is a match for anything that machines can throw at us … it just takes us a little longer.

If you are interested in DES and its usage of the Friestel cipher (as used in DES), try here:

https://asecuritysite.com/symmetric/fei

and in backdoors in crypto:

And if you like cracking ciphers, try here:

https://asecuritysite.com/challenges