The Feistel Network (Feistel Construction)

Feistel network (Feistel construction) is a type of block cipher with a particular iterative structure. Many modern algorithms use a Feistel network as their basis.

In 1973, Horst Feistel published an article in Scientific American titled “Cryptography and Computer Security” ( “Cryptography and Computer Privacy”), in which he revealed several important aspects of encryption and also introduced the construction later named the Feistel network. This scheme was used in IBM’s Lucifer project, on which Feistel and Don Coppersmith worked. This project was more experimental in nature, but it became the basis for DES. The algorithm’s iterative structure made it easier to implement in hardware.

Construction

encryption

decryption

• the plaintext block is split into 2 equal parts (
• each round computes ( - the round number)

,

where is some function, and is the key for round . The result of performing rounds is . But usually, in round, the permutation and is not performed, which allows the same procedure to be used for decryption as well, simply by inverting the order in which the round key material is used:

,

Small changes make it possible to achieve full identity between the encryption and decryption procedures. One of the advantages of this model is that the algorithm can be applied regardless of the function , which can be of any complexity.

Encryption

Suppose some information needs to be encrypted, represented in binary form (as a sequence of zeros and ones) and residing in the memory of a computer or other device (for example, in a file).

Encryption algorithm.

• The information is split into blocks of equal (fixed) length. The resulting blocks are called input blocks, since they are fed to the input of the algorithm. If the length of the input block is smaller than the size the chosen encryption algorithm can encrypt at once (the block size), the block is lengthened by some means. As a rule the block length is a power of two, for example 64 bits or 128 bits.

Decryption

Decryption of information proceeds in the same way as encryption, with the sole exception that the keys follow in reverse order, that is, not from the first to the N-th, but from the N-th to the first.

Example implementation in C

Modifications of the Feistel network

With a large encryption block size (128 bits or more), implementing such a Feistel network on 32-bit architectures can cause difficulties, so modified variants of this construction are used. In ordinary situations, networks with 4 branches are used. The figure shows the most common modifications. There are also schemes in which the lengths of the halves and do not match. These are called unbalanced .

Modifications of the Feistel network

type 1

type 2

type 3

Features of the Feistel network

• each pass consists of a single layer (the transformations are all of the same type)
• a reversible (irreversible) operation applies to one part of the block being encrypted a value computed from the other part
• The network is invertible (decryption does not require computing the inverse function)
• Decryption uses the same algorithm, the same text is fed to the input, and the keys are used in reverse order
• The input block is split into several identical sub-blocks – branches

Ciphers based on the Feistel network (construction)

Such ciphers use a classical or modified Feistel network as their basis:

• Blowfish
• Camellia
• CAST
• DES
• FEAL
• GOST 28147-89
• KASUMI
• LOKI97
• Lucifer
• MacGuffin
• MARS
• MAGENTA
• MISTY1
• RC2
• RC5
• RC6
• Skipjack
• TEA
• Triple DES
• Twofish
• XTEA

See also

• Cryptography
• Stream cipher
• Substitution-permutation network
• The lifting scheme for the discrete wavelet transform has roughly the same structure
• Format-preserving encryption
• Lai–Massey scheme