Feistel Structured Ciphers

CS 463 Lecture, Dr. Lawlor

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).
DES Feistel structure

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.

Here's a very simple 64-bit software implementation of a Feistel cipher. We won't use the substitution table until below.

/* 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;
}

(Try this in NetRun now!)

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 C 0: 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=0xffffffffffffffffsin(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=0xffffffffffffffffsin(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.