# Feistel Structured Ciphers and The Data Encryption Standard (DES)

CS 463/480 Lecture, Dr. Lawlor

The Data Encryption Standard (DES) is a very old cipher from the 1970's, but it's got the same basic structure as modern more secure ciphers.
• DES encryption starts with a block of 64 bits of plaintext.
• A series of 16 rounds mix the plaintext bits with each other and the key, using a combination of bit shifting, XOR, and several very small (6 bit input, 4 bit output) substitution or "S-boxes".
Here's the source code, this version from PolarSSL/library/des.c.  This uses a set of macros to look up values in tables, named SB1 through SB8, used to implement the S boxes.  The full set of tables is graphed here.
`/* * DES round macro: applies DES S-boxes */#define DES_ROUND(X,Y)                          \{                                               \    T = *SK++ ^ X;                              \    Y ^= SB8[ (T      ) & 0x3F ] ^              \         SB6[ (T >>  8) & 0x3F ] ^              \         SB4[ (T >> 16) & 0x3F ] ^              \         SB2[ (T >> 24) & 0x3F ];               \                                                \    T = *SK++ ^ ((X << 28) | (X >> 4));         \    Y ^= SB7[ (T      ) & 0x3F ] ^              \         SB5[ (T >>  8) & 0x3F ] ^              \         SB3[ (T >> 16) & 0x3F ] ^              \         SB1[ (T >> 24) & 0x3F ];               \}/* * DES-ECB block encryption/decryption */int des_crypt_ecb( des_context *ctx,                    const unsigned char input[8],  // data size: 64 bits                    unsigned char output[8] ){    int i;    uint32_t X, Y; // data being encrypted    uint32_t T;  // temporary value used during round    uint32_t *SK = ctx->sk; // session keys    GET_UINT32_BE( X, input, 0 );  // converts bytes int (from big-endian)    GET_UINT32_BE( Y, input, 4 );    DES_IP( X, Y ); // "initial permutation"    for( i = 0; i < 8; i++ ) // 8 forward-reverse rounds (16 rounds total)    {        DES_ROUND( Y, X ); // xor's Y based on table[X]        DES_ROUND( X, Y ); // xor's X based on table[Y]    }    DES_FP( Y, X ); // "final permutation"    PUT_UINT32_BE( Y, output, 0 );    PUT_UINT32_BE( X, output, 4 );    return( 0 );}`
Like RC5, the basic iterative round structure of Y^=f(X); X^=f(Y); is called a "Feistel structured cipher", after IBM researcher Horst Feistel (1915 - 1990).

## Obsolete Features

The most obsolete aspect of DES is the very short key--64 bits, but 8 of those are just used for parity checking.  A 56-bit key space is within the realm of brute force today: FPGA implementations today can check hundreds of billions of keys per second, so can brute force DES keys in under a day.  ASIC implementations are even faster.

The other big problem with DES is the substitution tables--modern timing or cache line flushing attacks can reveal information about data-dependent reads from tables.  This is nearly unfixable on a modern machine, but you might make some progress by shrinking the tables until they each fit in one 64-byte cache line, like this simplified demo implementation (missing the real key schedule and mixing):
```enum {n_rounds=16, n_keys=n_rounds};

// Circular bit rotate left: rotate v left by count bits
unsigned int ROTL(unsigned int v,unsigned int count)
{
return (v<<count) | (v>>(32-count));
}
unsigned int ROTR(unsigned int v,unsigned int count)
{
return (v>>count) | (v<<(32-count));
}

/* This is a 32-bit in, 32-bit out permutation:
Expand to 6-bit fields
Look up 6-bit fields in substitution tables
Combine 4-bit outputs back to 32-bit integer
(Caution: the key needs to be mixed in after expansion,
making this not quite the DES permutation!)
*/
unsigned int DES_expandpermute(unsigned int X) {
/* DES S-boxes: 8 tables, 6 bit input, 4 bit output */
const static unsigned char tables[8][64]=
{{
14,0,4,15,13,7,1,4,2,14,15,2,11,13,8,1,3,10,10,6,6,12,12,11,5,9,9,5,0,3,7,8
,4,15,1,12,14,8,8,2,13,4,6,9,2,1,11,7,15,5,12,11,9,3,7,14,3,10,10,0,5,6,0,13
},{
15,3,1,13,8,4,14,7,6,15,11,2,3,8,4,14,9,12,7,0,2,1,13,10,12,6,0,9,5,11,10,5
,0,13,14,8,7,10,11,1,10,3,4,15,13,4,1,2,5,11,8,6,12,7,6,12,9,0,3,5,2,14,15,9
},{
10,13,0,7,9,0,14,9,6,3,3,4,15,6,5,10,1,2,13,8,12,5,7,14,11,12,4,11,2,15,8,1
,13,1,6,10,4,13,9,0,8,6,15,9,3,8,0,7,11,4,1,15,2,14,12,3,5,11,10,5,14,2,7,12
},{
7,13,13,8,14,11,3,5,0,6,6,15,9,0,10,3,1,4,2,7,8,2,5,12,11,1,12,10,4,14,15,9
,10,3,6,15,9,0,0,6,12,10,11,1,7,13,13,8,15,9,1,4,3,5,14,11,5,12,2,7,8,2,4,14
},{
2,14,12,11,4,2,1,12,7,4,10,7,11,13,6,1,8,5,5,0,3,15,15,10,13,3,0,9,14,8,9,6
,4,11,2,8,1,12,11,7,10,1,13,14,7,2,8,13,15,6,9,15,12,0,5,9,6,10,3,4,0,5,14,3
},{
12,10,1,15,10,4,15,2,9,7,2,12,6,9,8,5,0,6,13,1,3,13,4,14,14,0,7,11,5,3,11,8
,9,4,14,3,15,2,5,12,2,9,8,5,12,15,3,10,7,11,0,14,4,1,10,7,1,6,13,0,11,8,6,13
},{
4,13,11,0,2,11,14,7,15,4,0,9,8,1,13,10,3,14,12,3,9,5,7,12,5,2,10,15,6,8,1,6
,1,6,4,11,11,13,13,8,12,1,3,4,7,10,14,7,10,9,15,5,6,0,8,15,0,14,5,2,9,3,2,12
},{
13,1,2,15,8,13,4,8,6,10,15,3,11,7,1,4,10,12,9,5,3,6,14,11,5,0,0,14,12,9,7,2
,7,2,11,1,4,14,1,7,9,4,12,10,14,8,2,13,0,15,6,12,10,9,13,0,15,3,3,5,5,6,8,11
}};

unsigned int ret=0;
for (int startbit=0;startbit<8;startbit++)
{
unsigned int Xs=ROTR(X,startbit*4-1)&0x3F; // extract 6 bits
unsigned int t=tables[startbit][Xs];
printf("%x",t);
ret|=(t<<(startbit*4));
}
return ret;
}

// This function is wrong: keys get mixed after expansion, before permutation.
unsigned int DES_round(unsigned int X,const unsigned int *keys) {
return DES_expandpermute(X^keys[0]);
}

// Mix two integers worth of data, A and B, using these keys.
void DES_rounds(unsigned int &A,unsigned int &B,const unsigned int *keys) {
for (int round=0;round<=n_rounds;round+=2) {
printf(" round %d: %08x %08x\n", round, A,B);
A ^= DES_round(B,&keys[round]);
B ^= DES_round(A,&keys[(round+1)]);
}
}

// Run some simple tests, encrypting ascending data
void foo(void) {
unsigned int keys[n_keys];
for (int k=0;k<n_keys;k++) keys[k]=0; // add real key schedule here

unsigned int A=1, B=0; // plaintext
DES_rounds(A,B,keys);
printf("Encrypted to 0x%08x  0x%08x \n",A,B);
}```

(Try this in NetRun now!)