1974 and The Patent That Started Cyber Security: Feistel Ciphers

--

The Feistel cipher applies a symmetric key infrastructure and was named after Horst Feistel. In the 1960s, IBM set up a cryptography research group in their Yorktown Heights, NY laboratory. Horst joined them in the 1970s and his work led to the creation of the Lucifer and DES (Data Encryption Standard) ciphers [here]:

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

IBM is a renowned world leader in cryptography and is developing an amazing platform for trust with its Hyperledger project. The roots of their leadship 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 set up 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:

The Festel cipher

A Feistel cipher essentially uses 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). 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 structure 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 gives 64 bits (16 x 4).

An example cipher is given here:

and 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 the most commonly used Feistel cipher. Format-preserving, Feistel-based encryption (FFX) is used in format-preserving encryption (FPE).

These days, we never use DES but use 3DES, instead. This is because the 56-bit encryption key used in DES is easily crackable these days, but the 112-bit equivalent key for 3DES is highly secure. Learn more here:

https://asecuritysite.com/des

--

--

Prof Bill Buchanan OBE FRSE
ASecuritySite: When Bob Met Alice

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. Based in Edinburgh. Old World Breaker. New World Creator. Building trust.