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).

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;
}```

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<>b)&0xff]                <

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.