display | more...

Feistel networks are a strategy for designing iterated block ciphers developed by Horst Feistel at IBM in 1974, that has been used in the design of many block ciphers, including DES, Blowfish, Twofish, and CAST. A Feistel network works in this way: Take a block of length n bits and divide it into two equal-sized halves, called L and R. A round of the cipher can be calculated from the previous round by:

Li = Ri-1

Ri = Li-1 XOR f(Ri-1, Ki)

where Ki is the subkey used in the ith round and f is an arbitrary round function (usually key mixing and s-box transformations). This is a very popular way of designing block ciphers because the whole construction is guaranteed to be invertible, even if the function f happens not to be, so long as the input to f may be reconstructed. Because the XOR function is used to combine the left half with the output of the round function, we may recompute Li-1 given Ri and Ri-1 (which is incidentally Li by definition), provided we can reconstruct the value of Ei:

Li-1 = Ri XOR f(Li, Ei)

Ri-1 = Li

So with the inverse structure here, we are essentially running the Feistel network backwards!

There is also an alternative structure called an unbalanced Feistel network, used in ciphers like Skipjack and MacGuffin, where the left and right halves are not of equal size. The characteristics of this sort of construction are still quite uncertain, although its use in a cipher such as Skipjack developed by an organization like the NSA is somewhat reassuring. MacGuffin was created to catalyze research in this method of cipher construction.