16 Data Encryption Standard

epgp books

 

 

 

 

Learning Objectives

  •  To know the design of DES.
  •  To learn about encryption and decryption in DES.
  •  To learn about strength of DES.
  •  To understand differential and linear cryptanalysis.
  1. INTRODUCTION

The Data Encryption Standard (DES) was jointly developed in 1974 by IBM and the U.S. government to set a standard that everyone could use to securely communicate with each other. It operates on blocks of 64 bits using a secret key that is 56 bits long. The original proposal used a secret key that was 64 bits long. It is widely believed that the removal of these 8 bits from the key was done to make it possible for U.S. government agencies to secretly crack messages.

 

DES started out as the “Lucifer” algorithm developed by IBM. The US National Security Agency (NSA) made several modifications, after which it was adopted as Federal Information Processing Standard (FIPS) standard 46-3 and ANSI standard X3.92.

 

DES (and most of the other major symmetric ciphers) is based on a cipher known as the Feistel block cipher. This was a block cipher developed by the IBM cryptography researcher Horst Feistel in the early 70’s. It consists of a number of rounds where each round contains bit-shuffling, non-linear substitutions (S-boxes) and exclusive OR operations. Most symmetric encryption schemes today are based on this structure (known as a feistel network). As with most encryption schemes, DES expects two inputs – the plaintext to be encrypted and the secret key. The manner in which the plaintext is accepted, and the key arrangement used for encryption and decryption, both determine the type of cipher it is. DES is therefore a symmetric, 64 bit block cipher as it uses the same key for both encryption and decryption and only operates on 64 bit blocks of data at a time5 (be they plaintext or ciphertext). The key size used is 56 bits, however a 64 bit (or eight-byte) key is actually input. The least significant bit of each byte is either used for parity (odd for DES) or set arbitrarily and does not increase the security in any way. All blocks are numbered from left to right which makes the eight bit of each byte the parity bit.

 

 

The above figure shows the work flow during a DES encryption. An initial permutation on 64 bit plaintext block is performed at the first step in sequence of flow. Then plaintext block is spilted into two 32 bit sub blocks. After that, blocks undergo 16 rounds of identical operations. The 32 bit left half and 32 bit right half are swapped at the end of 16 th round.Then it is permuted using a inverse initial permutation function. The output of this final permutation is 64 bit ciphertext.

   1.1.1    Initial Permutation IP

 

IP is first step of the data computation .IP reorders the input data bits even bits to left half(LH), odd bits to 32 bit right half (RH). It has quite regular in structure so that easy to implement in h/w.

 

For example:

 

IP(675a6967 5e5a6b5a) = (ffb2194d 004df6fb)

 

1.1.2    DES Round Structure

Let’s see what is happening in each round.32 bit RH bits are given to expansion function E. The output of E is 48 bit. It is XORed with 48 bit key and output is given to 8 S boxes. Here Each S box has 6 bit input and it produces 4 bit output. Then outputs from all S boxes are combined and given to input of permutation P Box. Hence 32 bit permuted bits are the output of each round.

1.1.3    Substitution Boxes S

 

DES uses eight S-boxes which map 6 to 4 bits.Each S-box is actually 4 little 4 bit boxes .Outer bits 1 & 6 (row bits) select one row of 4.Inner bits 2-5 (col bits) are substituted .Result is 8 lots of 4 bits, or 32 bits.Row selection depends on both data & key. Feature known as autoclaving (autokeying) is applied here.

 

For example:

 

S(18 09 12 3d 11 17 38 39) = 5fd25e03

  1. DES Key Schedule

Subkeys should be computed in each round of DES. Initial permutation of the key (PC1) which selects 56-bits in two 28-bit halves .

 

16 tages consisting of (i)Rotating each half separately either 1 or 2 places depending on the key rotation schedule K (ii) Selecting 24-bits from each half & permuting them by PC2 for use in round function F

  1. DES Decryption

Decrypt must unwind steps of data computation .With Feistel design, do encryption steps again using subkeys in reverse order (SK16 … SK1).IP undoes final FP step of encryption First round with SK16 undoes 16th encrypt round till 16th round with SK1 undoes 1st encrypt round then final FP undoes initial encryption IP thus recovering original data value

  1. Avalanche Effect

One of the key desirable properties of encryption algorithm is Avalance effect, where a change of one input or key bit results in changing approx half output bits. Making attempts to “home-in” by guessing keys impossible in DES.DES exhibits strong avalanche.

  1. Strength of DES 5.1 Key Size

DES uses 56-bit keys, which have 256 = 7.2 x 1016 values. Even though it is hard to do brute force search ,recent advances have shown is possible. They are listed below:

  • in 1997 on Internet in a few months
  • in 1998 on dedicated h/w (EFF) in a few days
  • in 1999 above combined in 22hrs!

So alternatives to DES has to be considered.

 

5.2 Analytic Attacks

 

Several analytic attacks on DES are possible. These analytic attacks utilise some deep structure of the cipher .IT can be done by gathering information about encryptions or can eventually recover some/all of the sub-key bits or if necessary then exhaustively search for the rest .Generally these are statistical attacks include differential cryptanalysis ,linear cryptanalysis and related key attacks

 

5.3 Timing Attacks

 

Timing attacks done at actual implementation of cipher. It uses knowledge of consequences of implementation to derive information about some/all subkey bits, specifically use fact that calculations can take varying times depending on the value of the inputs to it. It is particularly problematic on smartcards.

using a large number of trial encryptions . The effectiveness given by: |p–1/2|

6    DES Design Criteria

 

DES design criteria is reported bt Coppersmith. There are 7 criteria for S-boxes provide for non-linearity, resistance to differential cryptanalysis and good confusion and 3 criteria for permutation P provide for increased diffusion.

 

SUMMARY

 

We have considered Feistel cipher design & structure DES details to strength the Differential & Linear Cryptanalysis.

you can view video on Data Encryption Standard