Horst Feistel's general alternating left-right structure used in DES became quite popular during the 1980's and 1990's, and came to be known as a "Feistel" structure. In addition to DES, it's used by Schneier's "Blowfish", RC5, and a number of other older ciphers.

The basic idea is to use the left half of the data to scramble the right half, then vice versa (Schneier and Kelsey showed how to generalize this to "unbalanced Feistel" in 1996).

The big advantages of a Feistel structure are:

- The decryption operation is identical to encryption, but you
just feed in the data and round keys in the opposite order.

- It works with *any* round function F: the function can be
noninvertible, fast to compute, hard to analyze, easy to
implement in software or hardware, etc.

/* Feistel-structured cipher: */ typedef unsigned long var; /* Bit rotate rightwards */ var ror(var v,unsigned int bits) { return (v>>bits)|(v<<(8*sizeof(var)-bits)); } /* Byte substitution table (stolen from Rijndael) */ unsigned char s[256] = { 0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76, 0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0, 0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15, 0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75, 0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84, 0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF, 0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8, 0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2, 0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73, 0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB, 0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79, 0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08, 0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A, 0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E, 0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF, 0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16 }; /* This class is used to encrypt or decrypt a block of data. */ class cipherblock { public: var L,R; // current state, Left and Right halves // Perform one round, using this key. // Modifies L depending on both R and the round key. void round(var &L,const var &R,var key,unsigned int stage) { var f; // f is this round's modification to L /* ... any round function goes here... */ f=R^key; L=L^f; } // Print the current state of this block void print(const char *description,int stage) { printf("%s %d: %016lx %016lx\n",description,stage,L,R); } }; int foo(void) { var plain=0xabcdef0000000; // plaintext var key=0xf0f0f0f0f123456; // encryption key cipherblock b; b.L=plain; b.R=plain>>32; b.print("Plaintext",0); // Take several rounds to scramble the data for (int r=0;r<3;r++) { b.round(b.L,b.R,key,r); b.print("L",r); b.round(b.R,b.L,key,r); b.print("R",r); } b.print("Ciphertext",0); // Walk rounds backwards to unscramble the data for (int r=2;r>=0;r--) { b.print("R",r); b.round(b.R,b.L,key,r); b.print("L",r); b.round(b.L,b.R,key,r); } b.print("Plaintext",0); return 0; }

Note
that using plain XOR as our round function (f) above gives
terrible results:

Plaintext 0: 000abcdef0000000 00000000000abcde L 0: 0f05b3d1ff188888 00000000000abcde R 0: 0f05b3d1ff188888 000abcdef0000000 L 1: 00000000000abcde 000abcdef0000000 R 1: 00000000000abcde 0f05b3d1ff188888 L 2: 000abcdef0000000 0f05b3d1ff188888 R 2: 000abcdef0000000 00000000000abcde Ciphertext 0: 000abcdef0000000 00000000000abcde R 2: 000abcdef0000000 00000000000abcde L 2: 000abcdef0000000 0f05b3d1ff188888 R 1: 00000000000abcde 0f05b3d1ff188888 L 1: 00000000000abcde 000abcdef0000000 R 0: 0f05b3d1ff188888 000abcdef0000000 L 0: 0f05b3d1ff188888 00000000000abcde Plaintext 0: 000abcdef0000000 00000000000abcde

The
action of each round is to cancel out the effect of the previous
round, so we're left with unencrypted ciphertext!

One
common way to analyze round functions is "differential
cryptanalysis", where we vary the cipher's input and watch how the
output changes. They can fail in surprisingly subtle ways,
but one common problem is changing one bit of the plaintext only
changes one bit of the ciphertext. This is very bad, because
a man-in-the-middle can selectively change bits of a message, for
example converting a permission bit from 0 to 1 in an ATM
transaction, without even being able to understand the rest of the
message!

In class, we tried quite a few different round functions.

Round Function |
Example |
Discussion |

f=key; (Try this in NetRun now!) |
P 0: 000abcdef0000000 00000000000abcde L 0: 000abcdeff0f0f0f 00000000000abcde R 0: 000abcdeff0f0f0f 000000000f05b3d1 L 1: 000abcdef0000000 000000000f05b3d1 R 1: 000abcdef0000000 00000000000abcde L 2: 000abcdeff0f0f0f 00000000000abcde R 2: 000abcdeff0f0f0f 000000000f05b3d1 C 0: 000abcdeff0f0f0f 000000000f05b3d1 |
Useless--each round undoes the effect of the
previous round. Note that "f=R^key;" is nearly as bad.
The problem is repeated XORs will cancel each other out. |

f=ror(key,8<<stage); (Try this in NetRun now!) |
P 0: 000abcdef0000000 00000000000abcde L 0: 0f0abcdef00f0f0f 00000000000abcde R 0: 0f0abcdef00f0f0f 0f0000000005b3d1 L 1: 0005bcdef00f0000 0f0000000005b3d1 R 1: 0005bcdef00f0000 000f00000005bcde L 2: 0f0ab3d1f00f0000 000f00000005bcde R 2: 0f0ab3d1f00f0000 0f000f0f0005bcde C 0: 0f0ab3d1f00f0000 0f000f0f0005bcde |
Shifting the key around helps somewhat.
We move by a different distance at each stage:
8<<stage makes shifts of 8, 16, and 32 bits. Our
key doesn't have much entropy, though, so XORing a few
shifted copies with the data doesn't cover up much. |

f=ror(R^key,8<<stage); (Try this in NetRun now!) |
P 0: 000abcdef0000000 00000000000abcde L 0: d10abcdef00f05b3 00000000000abcde R 0: d10abcdef00f05b3 bcd10abcdef5bcd4 L 1: 62d1000ffab3d449 bcd10abcdef5bcd4 R 1: 62d1000ffab3d449 6797686ddefa4968 L 2: b32446689d24bc24 6797686ddefa4968 R 2: b32446689d24bc24 f5bcdb466dde0f00 |
Mixing with the right hand side provides more
mixing, so we're approaching plausibly encrypted.
Differential analysis shows only the low bits of the
ciphertext change when we change one low bit of the
plaintext, but at least it's more than one bit. |

f=0xffffffffffffffff*sin(key*(stage+1)); (Try this in NetRun now!) |
P 0: 000abcdef0000000 00000000000abcde L 0: 800677b1f9756000 00000000000abcde R 0: 800677b1f9756000 800ccb6f097fdcde L 1: 5dc4eb9d33b83800 800ccb6f097fdcde R 1: 5dc4eb9d33b83800 5dce5743c3b284de L 2: a23b17b49560e000 5dce5743c3b284de R 2: a23b17b49560e000 a231ab6a656a5cde C 0: a23b17b49560e000 a231ab6a656a5cde |
In theory sin(integer) returns an irrational
number, but as you can see, the low bits here are actually
all zeros. Generally, floating point operations are
rarely used due to portability concerns, where a different
OS or upgraded math library changes the cipher. |

f=0xffffffffffffffff*sin(key*(stage+1)); f=f^ror(f^R,4); (Try this in NetRun now!) |
P 0: 000abcdef0000000 00000000000abcde L 0: 6806bb0709e29dcd 00000000000abcde R 0: 6806bb0709e29dcd 5e8c6c698976a302 L 1: 9df0c82f97147a7d 5e8c6c698976a302 R 1: 9df0c82f97147a7d 574dd50576666925 L 2: 38841694fcc7496f 574dd50576666925 R 2: 38841694fcc7496f 54c59787051f4833 C 0: 38841694fcc7496f 54c59787051f4833 |
A poor entropy generator can be improved by
bit mixing. Also, mixing in data from the right hand
side helps the cipher resist differential analysis. |

f=s[(R^key)&0xff]; (Try this in NetRun now!) |
P 0: 000abcdef0000000 00000000000abcde L 0: 000abcdef000003e 00000000000abcde R 0: 000abcdef000003e 00000000000abc19 L 1: 000abcdef0000079 00000000000abc19 R 1: 000abcdef0000079 00000000000abc21 L 2: 000abcdef0000048 00000000000abc21 R 2: 000abcdef0000048 00000000000abc81 C 0: 000abcdef0000048 00000000000abc81 |
Lookups in a substitution table are a very
good way to mix bits. For a Feistel cipher, the table
doesn't need to have an inverse, so it can be filled with
any random-looking data, like digits of pi. The big
downside is an 8-bit table only produces 8 bits of output! |

var idx=(R^key)+stage; for (b=0;b<64;b+=8) f=f^( s[(idx>>b)&0xff] <<b ); (Try this in NetRun now!) |
P 0: 000abcdef0000000 00000000000abcde L 0: 6369dfbd866b6d3e 00000000000abcde R 0: 6369dfbd866b6d3e fbf99e7aa7491619 L 1: 6cf0d4674431b9ce fbf99e7aa7491619 R 1: 6cf0d4674431b9ce ab75d6ff14fb583c L 2: 0e6d2271eb8ee258 ab75d6ff14fb583c R 2: 0e6d2271eb8ee258 0049455c7df70df7 C 0: 0e6d2271eb8ee258 0049455c7df70df7 |
A short table can be extended by running each
byte through the substitution table separately, and sticking
the results together. This gives us full-width output,
but differential cryptanalysis shows we don't have mixing
between bytes yet. |

... s[] as above, then ... f=f^ror(f,stage*23+1); (Try this in NetRun now!) |
P 0: 000abcdef0000000 00000000000abcde L 0: 52d86e0c3d5edba1 00000000000abcde R 0: 52d86e0c3d5edba1 0051500132335048 L 1: dac66f13cbe668d4 0051500132335048 R 1: dac66f13cbe668d4 49607e2b9a85a8d2 L 2: 06f4c81e58a443eb 49607e2b9a85a8d2 R 2: 06f4c81e58a443eb f63b209d92fb5e23 C 0: 06f4c81e58a443eb f63b209d92fb5e23 |
Adding nearly any bit reordering after the
substitution table gives much better mixing. After
several rounds, the data looks well encrypted. Most
ciphers have this substitute-permute structure. |

There
are several possible pitfalls in a Feistel-type cipher:

- A poor scrambling function (above) can leak plaintext bits to the output, or allow changes in plaintext to reflect directly into the ciphertext and vice versa. Sometimes the flaw in a "poor" function won't be obvious for decades, until somebody realizes how to break it.
- The more rounds we use, the better the statistical scrambling
of the plaintext, but the cipher uses more computational
effort. Typical ciphers use a few dozen rounds, or allow
different round counts for higher security.

- Even with a good scrambling function, the key schedule is
another possible weakness--using different keys at each stage
helps reduce the chance of future stages replicating (or
undoing) previous stage work. But using unrelated keys
across the stages would make it possible for an attacker to
simply split the key bits in half, which Diffie and Hellman call
the "meet-in-the-middle
attack". Working backwards from the ciphertext, and
working forwards from known or guessed plaintext, an attacker
could look for places where the half-decrypted and
half-encrypted data intersect (for example, by using a big
hashtable). This could cut the search time from O(2^k) to
O(2^(k/2)) for a
*k*-bit key, although it would use substantial O(2^(k/2)) space.