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:

  1. The developers of DES (they worked for IBM and the NSA) stole the concept from East Germany.
  2. East German cryptologists stole the concept from the USA.
  3. 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.


Further reading: The Ice Cream Van Public Key Encryption System

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

Subscribe to Blog via Email

Enter your email address to subscribe to this blog and receive notifications of new posts by email.

Kommentare (6)

  1. #1 TWO
    INCIRLIK
    17. September 2019
  2. #2 Thomas
    17. September 2019

    @Klaus
    “East German cryptologists had already known it (i.e. the four branches Feistel concept) in the early 1970s”. Is this assumption based on the T 310 cipher specification in the image the clue? Is it dated and available on Jörg Drobick’s website? I couldn’t find a hint in his chronology (http://scz.bplaced.net/t310.html#chr)

  3. #3 Klaus Schmeh
    18. September 2019

    Bill Ricker via Facebook:
    Efficiency in crypto is at best a mixed blessing :-/

  4. #4 Klaus Schmeh
    18. September 2019

    Bill Ricker via Facebook:

    Neat article.

    > I could not believe that East German cryptologists had already known it in the early 1970s.

    Hardly the first time the open academic crypto community found something that the state secret crypto communities with their captive mathematicians had found decades earlier — sometimes used and sometimes ignored. (After all, the DES S-boxes were tweaked to prevent an attack that IBM and NSA knew then but the rest didn’t learn until much later.)
    Once one sees Feistel, if one has slower eastern blok hardware, making it 4 branch to use a 4:1 ratio of block to register makes emminent sense to hardware designers, if not to cryptographers, right?

  5. #5 Klaus Schmeh
    18. September 2019

    Bill Ricker via Facebook:
    The IBM patent applications (1971) and Scientific American article (1973) on LUCIFER and Feistel model make “theft” by Stasi’s NSA-equivalent back office not very difficult at all.

    AFAIK, only the /thinking/ (justification) for NSA’s tweak to the S-boxes was classified, which is why DES was publicly specifiable (and prior LUCIFER revs in business uses prior to standardization).

  6. #6 Joe
    Berlin
    19. September 2019

    Der Algorithmus der T-310 stammt ursprünglich aus der Alpha-Klasse die zuerst in der SKS V/I realisiert wurde.
    Diese existierte schon vor 1973 und kann wg. der Geheimhaltung des DES/Feistel nur als Parallelentwicklung angesehen werden.
    Die Betrachtung des Alpha Algorithmus als Feistel gilt trotzdem als sehr gewagt. Man beachte bitte den Langzeitschlüssel.