Feistel cipher
Encyclopedia
In cryptography
, a Feistel cipher is a symmetric structure used in the construction of block cipher
s, named after the German
-born physicist
and cryptographer Horst Feistel
who did pioneering research while working for IBM
(USA); it is also commonly known as a Feistel network. A large proportion of block cipher
s use the scheme, including the Data Encryption Standard
(DES). The Feistel structure has the advantage that encryption
and decryption operations are very similar, even identical in some cases, requiring only a reversal of the key schedule
. Therefore the size of the code or circuitry required to implement such a cipher is nearly halved.
A Feistel network is an iterated cipher with an internal function called a round function.
cipher, designed by Horst Feistel and Don Coppersmith
. Feistel networks gained respectability when the U.S. Federal Government adopted the DES
(a cipher based on Lucifer, with changes made by the NSA
). Like other components of the DES, the iterative nature of the Feistel construction makes implementing the cryptosystem in hardware easier (particularly on the hardware available at the time of DES' design).
block cipher), and the structure and properties of Feistel ciphers have been extensively explored by cryptographers. Specifically, Michael Luby
and Charles Rackoff
analyzed the Feistel cipher construction, and proved that if the round function is a cryptographically secure pseudorandom function
, with Ki used as the seed, then 3 rounds is sufficient to make the block cipher a pseudorandom permutation
, while 4 rounds is sufficient to make it a "strong" pseudorandom permutation (which means that it remains pseudorandom even to an adversary who gets oracle
access to its inverse permutation).
Because of this very important result of Luby and Rackoff, Feistel ciphers are sometimes called Luby-Rackoff block ciphers. Further theoretical work has generalized the construction somewhat, and given more precise bounds for security.
be the round function and let
be the sub-keys for the rounds 
respectively.
Then the basic operation is as follows:
Split the plaintext block into two equal pieces, (
, 
)
For each round
, compute
.
Then the ciphertext is
.
Decryption of a ciphertext
is accomplished by computing for 
.
Then
is the plaintext again.
One advantage of the Feistel model compared to a substitution-permutation network
is that the round function
does not have to be invertible.
The diagram illustrates both encryption and decryption. Note the reversal of the subkey order for decryption; this is the only difference between encryption and decryption.
and 
are not of equal lengths. The Skipjack encryption algorithm is an example of such a cipher. The Texas Instruments
Digital Signature Transponder
uses a proprietary unbalanced Feistel cipher to perform challenge-response authentication
.
The Thorp shuffle is an extreme case of an unbalanced Feistel cipher in which one side is a single bit. This has better provable security than a balanced Feistel cipher but requires more rounds.
(OAEP) scheme uses a simple Feistel network to randomize ciphertexts in certain asymmetric key encryption schemes.
A generalized Feistel algorithm can be used to create strong permutations on small domains of size not a power of two (see Format-Preserving Encryption
).
is a Feistel cipher using a three-round Feistel network in its round function, Skipjack
is a modified Feistel cipher using a Feistel network in its G permutation, and Threefish
(part of Skein
) is a non-Feistel block cipher that uses a Feistel-like MIX function.
Blowfish
,
Camellia
,
CAST-128
,
DES
,
FEAL
,
ICE,
KASUMI,
LOKI97
,
Lucifer
,
MARS,
MAGENTA,
MISTY1
,
RC5
,
TEA
,
Triple DES
,
Twofish
,
XTEA
,
GOST 28147-89
Generalised Feistel:
CAST-256
,
MacGuffin
,
RC2
,
RC6
,
Skipjack
,
SMS4
,
CLEFIA
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, a Feistel cipher is a symmetric structure used in the construction of block cipher
Block cipher
In cryptography, a block cipher is a symmetric key cipher operating on fixed-length groups of bits, called blocks, with an unvarying transformation. A block cipher encryption algorithm might take a 128-bit block of plaintext as input, and output a corresponding 128-bit block of ciphertext...
s, named after the German
Germany
Germany , officially the Federal Republic of Germany , is a federal parliamentary republic in Europe. The country consists of 16 states while the capital and largest city is Berlin. Germany covers an area of 357,021 km2 and has a largely temperate seasonal climate...
-born physicist
Physicist
A physicist is a scientist who studies or practices physics. Physicists study a wide range of physical phenomena in many branches of physics spanning all length scales: from sub-atomic particles of which all ordinary matter is made to the behavior of the material Universe as a whole...
and cryptographer Horst Feistel
Horst Feistel
Horst Feistel was a German-born cryptographer who worked on the design of ciphers at IBM, initiating research that would culminate in the development of the Data Encryption Standard in the 1970s....
who did pioneering research while working for IBM
IBM
International Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...
(USA); it is also commonly known as a Feistel network. A large proportion of block cipher
Cipher
In cryptography, a cipher is an algorithm for performing encryption or decryption — a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. In non-technical usage, a “cipher” is the same thing as a “code”; however, the concepts...
s use the scheme, including the Data Encryption Standard
Data Encryption Standard
The Data Encryption Standard is a block cipher that uses shared secret encryption. It was selected by the National Bureau of Standards as an official Federal Information Processing Standard for the United States in 1976 and which has subsequently enjoyed widespread use internationally. It is...
(DES). The Feistel structure has the advantage that encryption
Encryption
In cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...
and decryption operations are very similar, even identical in some cases, requiring only a reversal of the key schedule
Key schedule
[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES [[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("[[Image:DES-key-schedule.png|thumbnail|220px|The key schedule of DES ("...
. Therefore the size of the code or circuitry required to implement such a cipher is nearly halved.
A Feistel network is an iterated cipher with an internal function called a round function.
Historical
Feistel networks were first seen commercially in IBM's LuciferLucifer (cipher)
In cryptography, Lucifer was the name given to several of the earliest civilian block ciphers, developed by Horst Feistel and his colleagues at IBM. Lucifer was a direct precursor to the Data Encryption Standard...
cipher, designed by Horst Feistel and Don Coppersmith
Don Coppersmith
Don Coppersmith is a cryptographer and mathematician. He was involved in the design of the Data Encryption Standard block cipher at IBM, particularly the design of the S-boxes, strengthening them against differential cryptanalysis...
. Feistel networks gained respectability when the U.S. Federal Government adopted the DES
Data Encryption Standard
The Data Encryption Standard is a block cipher that uses shared secret encryption. It was selected by the National Bureau of Standards as an official Federal Information Processing Standard for the United States in 1976 and which has subsequently enjoyed widespread use internationally. It is...
(a cipher based on Lucifer, with changes made by the NSA
National Security Agency
The National Security Agency/Central Security Service is a cryptologic intelligence agency of the United States Department of Defense responsible for the collection and analysis of foreign communications and foreign signals intelligence, as well as protecting U.S...
). Like other components of the DES, the iterative nature of the Feistel construction makes implementing the cryptosystem in hardware easier (particularly on the hardware available at the time of DES' design).
Theoretical work
Many modern and also some old symmetric block ciphers are based on Feistel networks (e.g. GOST 28147-89GOST 28147-89
The GOST block cipher, defined in the standard GOST 28147-89, is a Soviet and Russian government standard symmetric key block cipher. Also based on this block cipher is the GOST hash function....
block cipher), and the structure and properties of Feistel ciphers have been extensively explored by cryptographers. Specifically, Michael Luby
Michael Luby
Michael George Luby is a mathematician and computer scientist, VP Technology at Qualcomm and former co-founder and Chief Technology Officer of Digital Fountain. In coding theory he is known for leading the invention of the Tornado codes and the LT codes...
and Charles Rackoff
Charles Rackoff
Charles Weill Rackoff is an American cryptologist. Born and raised in New York City, Rackoff attended MIT as both an undergraduate and graduate student, and earned a Ph.D. degree in Computer Science in 1974. He spent a year as a postdoctoral scholar at INRIA in France.He currently works at the...
analyzed the Feistel cipher construction, and proved that if the round function is a cryptographically secure pseudorandom function
Pseudorandom function
In cryptography, a pseudorandom function family, abbreviated PRF, is a collection of efficiently-computable functions which emulate a random oracle in the following way: no efficient algorithm can distinguish between a function chosen randomly from the PRF family and a random oracle...
, with Ki used as the seed, then 3 rounds is sufficient to make the block cipher a pseudorandom permutation
Pseudorandom permutation
In cryptography, the term pseudorandom permutation, abbreviated PRP, refers to a function that cannot be distinguished from a random permutation with practical effort.A pseudorandom permutation family is a collection of pseudorandom permutations,...
, while 4 rounds is sufficient to make it a "strong" pseudorandom permutation (which means that it remains pseudorandom even to an adversary who gets oracle
Oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
access to its inverse permutation).
Because of this very important result of Luby and Rackoff, Feistel ciphers are sometimes called Luby-Rackoff block ciphers. Further theoretical work has generalized the construction somewhat, and given more precise bounds for security.
Construction details
Let be the round function and let be the sub-keys for the rounds respectively.Then the basic operation is as follows:
Split the plaintext block into two equal pieces, (
, )For each round
, compute.Then the ciphertext is
.Decryption of a ciphertext
is accomplished by computing for .Then
is the plaintext again.One advantage of the Feistel model compared to a substitution-permutation network
Substitution-permutation network
In cryptography, an SP-network, or substitution-permutation network , is a series of linked mathematical operations used in block cipher algorithms such as AES .Other ciphers that use SPNs are 3-Way, SAFER, SHARK, and Square....
is that the round function
does not have to be invertible.The diagram illustrates both encryption and decryption. Note the reversal of the subkey order for decryption; this is the only difference between encryption and decryption.
Unbalanced Feistel cipher
Unbalanced Feistel ciphers use a modified structure where and are not of equal lengths. The Skipjack encryption algorithm is an example of such a cipher. The Texas InstrumentsTexas Instruments
Texas Instruments Inc. , widely known as TI, is an American company based in Dallas, Texas, United States, which develops and commercializes semiconductor and computer technology...
Digital Signature Transponder
Digital Signature Transponder
The Texas Instruments Digital Signature Transponder is a cryptographically-enabled radio-frequency identification device used in a variety of wireless authentication applications...
uses a proprietary unbalanced Feistel cipher to perform challenge-response authentication
Challenge-response authentication
In computer security, challenge-response authentication is a family of protocols in which one party presents a question and another party must provide a valid answer to be authenticated....
.
The Thorp shuffle is an extreme case of an unbalanced Feistel cipher in which one side is a single bit. This has better provable security than a balanced Feistel cipher but requires more rounds.
Other uses
The Feistel construction is also used in cryptographic algorithms other than block ciphers. For example, the Optimal Asymmetric Encryption PaddingOptimal Asymmetric Encryption Padding
In cryptography, Optimal Asymmetric Encryption Padding is a padding scheme often used together with RSA encryption. OAEP was introduced by Bellare and Rogaway....
(OAEP) scheme uses a simple Feistel network to randomize ciphertexts in certain asymmetric key encryption schemes.
A generalized Feistel algorithm can be used to create strong permutations on small domains of size not a power of two (see Format-Preserving Encryption
Format-Preserving Encryption
In cryptography, format-preserving encryption refers to encrypting in such a way that the output is in the same format as the input . The meaning of "format" varies...
).
Feistel networks as a design component
Whether the entire cipher is a Feistel cipher or not, Feistel-like networks can be used as a component of a cipher's design. For example, MISTY1MISTY1
In cryptography, MISTY1 is a block cipher designed in 1995 by Mitsuru Matsui and others for Mitsubishi Electric.MISTY1 is one of the selected algorithms in the European NESSIE project, and has been recommended for Japanese government use by the CRYPTREC project."MISTY" can stand for "Mitsubishi...
is a Feistel cipher using a three-round Feistel network in its round function, Skipjack
Skipjack (cipher)
In cryptography, Skipjack is a block cipher—an algorithm for encryption—developed by the U.S. National Security Agency . Initially classified, it was originally intended for use in the controversial Clipper chip...
is a modified Feistel cipher using a Feistel network in its G permutation, and Threefish
Threefish
Threefish is a tweakable block cipher designed as part of the Skein hash function, an entry in the NIST hash function competition. Threefish uses no S-boxes or other table lookups in order to avoid cache timing attacks; its nonlinearity comes from alternating additions with exclusive ORs...
(part of Skein
Skein (hash function)
Skein is a cryptographic hash function and one out of five finalists in the NIST hash function competition to design what will become the SHA-3 standard, the intended successor of SHA-1 and SHA-2...
) is a non-Feistel block cipher that uses a Feistel-like MIX function.
List of Feistel ciphers
Feistel or modified Feistel:Blowfish
Blowfish (cipher)
Blowfish is a keyed, symmetric block cipher, designed in 1993 by Bruce Schneier and included in a large number of cipher suites and encryption products. Blowfish provides a good encryption rate in software and no effective cryptanalysis of it has been found to date...
,
Camellia
Camellia (cipher)
In cryptography, Camellia is a 128-bit block cipher jointly developed by Mitsubishi and NTT. The cipher has been approved for use by the ISO/IEC, the European Union's NESSIE project and the Japanese CRYPTREC project...
,
CAST-128
CAST-128
in cryptography, CAST-128 is a block cipher used in a number of products, notably as the default cipher in some versions of GPG and PGP. It has also been approved for Canadian government use by the Communications Security Establishment...
,
DES
Data Encryption Standard
The Data Encryption Standard is a block cipher that uses shared secret encryption. It was selected by the National Bureau of Standards as an official Federal Information Processing Standard for the United States in 1976 and which has subsequently enjoyed widespread use internationally. It is...
,
FEAL
FEAL
In cryptography, FEAL is a block cipher proposed as an alternative to the Data Encryption Standard , and designed to be much faster in software. The Feistel based algorithm was first published in 1987 by Akihiro Shimizu and Shoji Miyaguchi from NTT...
,
ICE,
KASUMI,
LOKI97
LOKI97
In cryptography, LOKI97 is a block cipher which was a candidate in the Advanced Encryption Standard competition. It is a member of the LOKI family of ciphers, earlier instances being LOKI89 and LOKI91...
,
Lucifer
Lucifer (cipher)
In cryptography, Lucifer was the name given to several of the earliest civilian block ciphers, developed by Horst Feistel and his colleagues at IBM. Lucifer was a direct precursor to the Data Encryption Standard...
,
MARS,
MAGENTA,
MISTY1
MISTY1
In cryptography, MISTY1 is a block cipher designed in 1995 by Mitsuru Matsui and others for Mitsubishi Electric.MISTY1 is one of the selected algorithms in the European NESSIE project, and has been recommended for Japanese government use by the CRYPTREC project."MISTY" can stand for "Mitsubishi...
,
RC5
RC5
In cryptography, RC5 is a block cipher notable for its simplicity. Designed by Ronald Rivest in 1994, RC stands for "Rivest Cipher", or alternatively, "Ron's Code"...
,
TEA
Tiny Encryption Algorithm
In cryptography, the Tiny Encryption Algorithm is a block cipher notable for its simplicity of description and implementation, typically a few lines of code...
,
Triple DES
Triple DES
In cryptography, Triple DES is the common name for the Triple Data Encryption Algorithm block cipher, which applies the Data Encryption Standard cipher algorithm three times to each data block....
,
Twofish
Twofish
In cryptography, Twofish is a symmetric key block cipher with a block size of 128 bits and key sizes up to 256 bits. It was one of the five finalists of the Advanced Encryption Standard contest, but was not selected for standardisation...
,
XTEA
XTEA
In cryptography, XTEA is a block cipher designed to correct weaknesses in TEA. The cipher's designers were David Wheeler and Roger Needham of the Cambridge Computer Laboratory, and the algorithm was presented in an unpublished technical report in 1997...
,
GOST 28147-89
GOST 28147-89
The GOST block cipher, defined in the standard GOST 28147-89, is a Soviet and Russian government standard symmetric key block cipher. Also based on this block cipher is the GOST hash function....
Generalised Feistel:
CAST-256
CAST-256
In cryptography, CAST-256 is a block cipher published in June 1998. It was submitted as a candidate for the Advanced Encryption Standard ; however, it was not among the five AES finalists. It is an extension of an earlier cipher, CAST-128; both were designed according to the "CAST" design...
,
MacGuffin
MacGuffin (cipher)
In cryptography, MacGuffin is a block cipher created in 1994 by Bruce Schneier and Matt Blaze at a Fast Software Encryption workshop. It was intended as a catalyst for analysis of a new cipher structure, known as Generalized Unbalanced Feistel Networks...
,
RC2
RC2
In cryptography, RC2 is a block cipher designed by Ron Rivest in 1987. "RC" stands for "Ron's Code" or "Rivest Cipher"; other ciphers designed by Rivest include RC4, RC5 and RC6....
,
RC6
RC6
In cryptography, RC6 is a symmetric key block cipher derived from RC5. It was designed by Ron Rivest, Matt Robshaw, Ray Sidney, and Yiqun Lisa Yin to meet the requirements of the Advanced Encryption Standard competition. The algorithm was one of the five finalists, and was also submitted to the...
,
Skipjack
Skipjack (cipher)
In cryptography, Skipjack is a block cipher—an algorithm for encryption—developed by the U.S. National Security Agency . Initially classified, it was originally intended for use in the controversial Clipper chip...
,
SMS4
SMS4
SMS4 is a block cipher used in the Chinese National Standard for Wireless LAN WAPI .SMS4 was a proposed cipher to be used in IEEE 802.11i standard, but has so far been rejected by ISO. One of the reasons for the rejection has been opposition to the WAPI fast-track proposal by the IEEE.The SMS4...
,
CLEFIA
CLEFIA
-External links:* * *...
See also
- CryptographyCryptographyCryptography is the practice and study of techniques for secure communication in the presence of third parties...
- Stream cipherStream cipherIn cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...
- Substitution-permutation networkSubstitution-permutation networkIn cryptography, an SP-network, or substitution-permutation network , is a series of linked mathematical operations used in block cipher algorithms such as AES .Other ciphers that use SPNs are 3-Way, SAFER, SHARK, and Square....
- Lifting schemeLifting schemeThe lifting scheme is a technique for both designing wavelets and performing the discrete wavelet transform.Actually it is worthwhile to merge these steps and design the wavelet filters while performing the wavelet transform....
for discrete wavelet transform has pretty much the same structure - Format-Preserving EncryptionFormat-Preserving EncryptionIn cryptography, format-preserving encryption refers to encrypting in such a way that the output is in the same format as the input . The meaning of "format" varies...