Feistel Block Cipher

Question

Can anybody explain, in simple terms, how Feistal Block Ciphers work. I am not a math student so I do not understand the math behind it, just would like the principles.

Answer 1

Cryptography is at least half-mathematics so you have to use a bit of mathematics at some point, if you want to understand cryptography. However, for the specific case of Feistel schemes, mathematics are not hard.

A block cipher should transform a data block (a sequence of n bits) into another block of the same size, such that:

• the transform is parameterized by knowledge of some (secret) value (the key);
• with the key, it is easy to compute the transform and its inverse;
• without the key, well, tough luck.

Hans Feistel designed a generic way of building block ciphers. Namely, the cipher will consist of the application of several rounds, each round looking like this:

• You split the input block into two halves, let's call them L (as "left") and R ("right"). Usually, you do an even split (both halves have length n/2 bits) but that's not an absolute necessity.
• You compute a value S which is the result of "mangling" together R and the key K. Details of the mangling are where overall security hides, and are not part of the "Feistel structure" per se: Feistel described the overall design, not a precise block cipher. Roughly speaking, the mangling should propagate bits of R and K all over the place and should depend upon the round number. The value S must have the same size than L.
• You compute the value R' as being equal to L xor S. "xor" is the bitwise "exclusive or" combination. By "bitwise" I mean that the first bit of L is combined with the first bit of S, yielding the first bit of R'; then the second bit of L is combined with the second bit of S, yielding the second bit of R'; and so on. The "exclusive or" of two bits is 0 if both bits are equal, 1 otherwise.
• You define the value L' as being equal to R.
• The output of the round is the concatenation of L' and R', in that order.

In simple words, a Feistel round consists in xoring the left half of the data with a value derived from the combination of the right half and the key, and then swapping the left and right halves. The Wikipedia article on Feistel ciphers has some nice diagrams.

The whole point of the structure is that computing the inverse transform (which means "decryption") is easy if you know the key. This is where there are some mathematics:

• for all a, b and c, if a xor b = c then a = b xor c
• for all a and b, a xor b = b xor a

(Write it down with the bit values, there are only eight combinations, so it is easy to see that it works). Thus, if you have L' and R', and the key K, then you have R (L' is equal to R); from R and K you can do the mangling again, and obtain S. Since R' = L xor S, you can rewrite it as: L = R' xor S. In other words, given the output of a round (L' and R') and the key K, you can run the mangling part again, and, with a simple xor, recompute the round input (L and R).

At that point you have the Feistel scheme. Things become complex (cryptographically speaking) when you want to know how to do the mangling, and how many rounds you will use. DES is a well-known standard which uses a Feistel scheme with 64-bit blocks, a 64-bit key, and 16 rounds (on the 64 key bits, only 56 are actually used, so the key is often said to have length 56, not 64). "Triple DES", which consists of three successive DES encryptions (with distinct keys !) can be viewed as a Feistel scheme with 48 rounds.

Luby and Rackoff have shown in 1988 that if you use wide enough blocks (say 256 bits or more) and the mangling steps consist in random-oracle like functions (think "ideal hash functions" here), then 4 rounds are enough to achieve ultimate security; however, building a "random-oracle like function" is hard (quite harder, actually, than building a secure enough mangling), and if you build a block cipher out of existing hash functions, performance will very likely be poor (hash functions are fast for processing long runs of data, but here we are talking about four hash function invocations on small data elements per encrypted block).

Most notably, the currently recommended standard block cipher, the AES, is not a Feistel block cipher.