In the early 1970s, cryptographers in the USA and in East Germany developed two suprisingly similar encryption methods. Did one party steal from the other? Or was a useful concept invented twice?
As already mentioned in my last blog post, I recently gave a presentation about Cold War cryptography at the 44CON hacker conference in London.
Among other things, I spoke about Feistel ciphers in East Germany. A Feistel cipher (named for IBM employee Horst Feistel) is a cipher that divides a plaintext block into two branches. In each round, one of the branches is fed to a non-linear function, the result of which is xored with the other branch.
The DES, the most important encryption algorithm of the early computer era, is a Feistel cipher with 16 rounds and a block length of 64 bits. In fact, the developers of DES are considered the inventors of the Feistel concept. The DES is introduced on one of the slides I used for my presentation:
The standard Feistel cipher (two branches) can be generalized to a Feistel cipher with four branches, as can be seen on the next slide:
Let’s now look at the T-310, an East German electronic cipher machine introduced in the 1970s. Contrary to most other Cold War encryption devices, the cipher implemented by the T-310 is known. Bernd Lippmann, director of the Stasi Museum foundation in Berlin, found the specification in the Stasi archive (BStU) and provided it to me.
The following slide shows two pages from the T-310 specification. A lot of mathematics is involved.
After Bernd Lippmann had provided me the specification, I published it in an article in Cryptologia:
Years later, Nicolas Courtois, a renowned cryptologist from the University College of London, looked at my article and at the original specification. He said: “This algorithm is a Feistel cipher with four branches.”
I was quite confused. The four-branch Feistel concept was first published in the academic literature in 1987. I could not believe that East German cryptologists had already known it in the early 1970s. So, I took a look at the T-310 specification again and drew a diagram of the relevant algorithm part.
There was no doubt that Nicolas was right. Here’s a comparison of the DES and the T-310 algorithm:
As mentioned on the slide, there are three possible reasons why the DES and the T-310 use a similar concept:
- The developers of DES (they worked for IBM and the NSA) stole the concept from East Germany.
- East German cryptologists stole the concept from the USA.
- The two-branch and the four-branch Feistel cipher were invented indpendently from each other in the USA and East Germany.
I have no idea which expanation is the correct one. Does a reader have a clue? If so, I would be very interested to know. My next presentation about Feistel ciphers will be at the NSA Crypto History Symposium in October. Perhaps, I can present some new information about this question there.
Follow @KlausSchmeh
Further reading: The Ice Cream Van Public Key Encryption System
Linkedin: https://www.linkedin.com/groups/13501820
Facebook: https://www.facebook.com/groups/763282653806483/
Kommentare (7)