In Memory of Horst Feistel

In Memory of Horst Feistel

How IBM Made The World A Whole Lot More Secure

IBM is a renowned world leader in cryptography, and is developing an amazing platform for trust with their Hyperledger project. The roots of their lead can be traced back to the creation of the Feistel cipher and which implements a symmetric key method.

In the 1960s, though, most of the cryptography research was conducted by governments, but IBM spotted a commercial opportunity and setup a cryptography research group in their Yorktown Heights, NY laboratory (and named after IBM’s founder — Thomas J. Watson Sr.). The lab went on to produce amazing advancements such as DRAM, the relational database and the FORTRAN programming language:

One of their best recruits was Horst Feistel, a physicist turned cryptographer, and who joined them in the 1970s. His work led to the creation of the Lucifer and DES (Data Encryption Standard) ciphers:

In the early 1970s, IBM patented the Lucifer cipher and which was then used by Lloyds Bank within some of the first ATM cash dispensers. After an evaluation by the NSA, Lucifer’s key size was reduced from 112 bits to 56 bits, after which it was published as the DES standard in 1975. DES then became manditory within its usage within US government electronic fund transfers, and went on to became a de-factor interational standard.

The Festel cipher

A Feistel cipher essentially uses same encryption and decryption process, and 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). Each round is then:

The function applied (F) does not have to be reversible, which is unlike the case for AES. With AES we have S-boxes with are used to scramble the rounds with defined mappings between byte values. Also, in AES, we have an inverse function between the encryption and the decryption process, while a Feistel just applies the key in the reverse order.

A sample run is:

Input text: hello
Key:  qwerty
Mode:  ecb

==============================
Cipher:  769e845b64e6f7fe
Cipher:  dp6EW2Tm9/4=
Plain text: hello

As we have an input of 40 bits (5 x 8 bit characters), we will thus only fill one block. The cipher is 0x769e845b64e6f7fe, which is 16 hex values, and which gives 64 bits (16 x 4). The following uses 64-bit block sizes [here] and with the operation of:

A code example in Python 3.8 is [here]:

Typical modes are ECB (Electronic Code Book) and CBC (Cipher Block Chain). ECB adds a counter value within each round, whereas CBC takes the output from a previous round and feeds into the present round.

DES is most commonly used Feistel cipher. Format-preserving, Feistel-based encryption (FFX) is used in format-preserving encryption (FPE).

A demo is here.

3-DES

One of the great problems with DES is that its key had been reduced to 56 bits, and which is easily cracked by brute force these days. And so 3-DES was created, and which used two keys (K1 and K2). The encryption process then becomes [here]:

C=E_K1(D_K2(E_K1(P)))

and to decrpyt

P=D_K1(E_K2(D_K1(C))).

and where E_K1 is the encrpytion with K1, and D_K1 is the decryption with K1. If you are interested, here’s how it all works: