Horst Feistel, The Feistel Cipher and a bit of Rust

Horst Feistel, The Feistel Cipher and a bit of Rust

Some may think that the roots of Cybersecurity go back to the discovery of the first computer worm in the 1980s, or into the late 1970s with the discovery of public-key encryption and the Diffie-Hellman method. But, we can trace it back into the early 1970s, and with the work of Horst Feistel. The roots of his work at IBM can be traced back to the creation of the Feistel cipher and which implements a symmetric key method.

In the 1960s, 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:

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 mandatory within its usage within US government electronic fund transfers and went on to become a de-facto international standard.

The Festel cipher

A Feistel cipher essentially uses the 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 using FFX (Format-preserving, Feistel-based encryption) is [here]:

Input: This is a secret message!

Key: 3006938325eadc643e2352c95e4e1309

Cipher: c5a8230b62332d9aceadb25c6b7b659afab790bc40d9f4e0cb

Decrypted: This is a secret message!

As we can see, we have 25 characters in the plaintext message, and that maps to 25 bytes (50 hex characters) for the ciphertext. A code example in Rust is [here]:

extern crate aes;
extern crate fpe;
extern crate hex;
extern crate rand;
use std::env;
use rand::{Rng};

fn main() {

use aes::Aes128;
    use fpe::ff1::{BinaryNumeralString,FF1};
    
    let key = rand::thread_rng().gen::<[u8; 16]>();

let radix = 2;

let mut instr="hello 123";

let args: Vec<String> = env::args().collect();
  
    if args.len() >1 { instr = args[1].as_str();}

let pt = instr.as_bytes();
    let ff = FF1::<Aes128>::new(&key, radix).unwrap();
   
    let ct = ff.encrypt(&[], &BinaryNumeralString::from_bytes_le(&pt)).unwrap();
    
    let p2 = ff.decrypt(&[], &ct).unwrap();

println!("Input: {0}\n", instr);
    let p2_str=String::from_utf8(p2.to_bytes_le());
    println!("Key: {}\n",hex::encode(key));
    println!("Cipher: {}\n",hex::encode(ct.to_bytes_le()));
    println!("Decrypted: {0}", p2_str.unwrap());
}

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).

A demo is here.

Conclusions

Have you looked at the complexity of the AES cipher, with its row and column swapping, inverse functions, and its S-boxes? To me, there is real beauty in the Feistel cipher, as it just applies the key in the reverse order.

In this article, I have outlined FFX, but, if you want to see a pure Feistel cipher in action, try here:

https://asecuritysite.com/symmetric/fei

and for Format Preserving Encryption (FPE):

https://asecuritysite.com/fpe/