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

Feistel structured cipher consists of two halves that are incrementally permuted against one another.

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