7 DES(Data Encryption Standard)

Hiteishi Diwanji

epgp books
  • ¨ DES was issued in 1977by the National Bureau of Standards(Now National Institute of Standards and Technology(NIST))
  • ¨ In Data Encryption Algorithm, Data is encrypted in the block of 64 bits and key length is 56 bits. The output is of 64 bits.
  • ¨ For Decryption, the same keys are used in reverse.
  • ¨ 64 bit plaintext passes through an Initial Permutation(IP) . The input bits are rearranged and permuted input is generated.
  • ¨ Then 16 rounds are performed with same function involving permutation and substitution.
  • ¨ The output is of 64 bits. The left and right halves are swapped. This swapped output is passed through permutation (IP-1) that is inverse of initial permutation.

Key generation overview

  • ¨ 56 bit key is used. The key is passed through a permutation function.
  • ¨ For each of the 16 rounds, a subkey(Ki) is produced by the combination of a left circular shift and a permutation.
  • ¨ For each round, different subkey is generated.

DES works on bits

  • ¨ DES works in the block of 64 message bits, equal to 16 hexadecimal numbers. DES example

Plaintext :02468aceeca86420

 

Key :                      0f1571c947d9e859

Ciphertext :       da02ce3a89ecac3b

Suppose M being the message:

  • ¨ M = 0123456789ABCDEF, represented in hexadecimal.
  • ¨ The binary form of M consists 64-bits in one block :
  • ¨ M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

L = 0000 0001 0010 0011 0100 0101 0110 0111 R = 1000 1001 1010 1011 1100 1101 1110 1111

Key Generation:

 

  • ¨ Key K = 133457799BBCDFF1 represented in hexadecimal.
  • ¨ K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001

    Step 1: Produce 16 subkeys, each 48-bits long.

Step 2: Encrypt block of 64-bit.

Step 1: Produce 16 subkeys, each 48-bits long.

  • ¨ Given 64-bit key gets permuted as per table mentioned below:

 

Check the table the first entry “57” indicates that from the key denoted as K, 57th bit moves as the first bit after permutation and key is denoted as K+.Given key of length 64-bits

  • ¨ K = 00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001 After permutation 56-bits
  • ¨ K+ = 1111000 0110011 0010101 0101111 0101010 1011001 1001111 0001111
  • ¨ Divide the key to form two parts of 28 bits. Left half denoted by C0 and right halve is denoted by D0.
  • ¨ Check K+,

C0 = 1111000 0110011 0010101 0101111

D0 = 0101010 1011001 1001111 0001111

  • ¨ Produce sixteen blocks Cn and Dn, nε[1,16].

Each pair of blocks Cn and Dn is formed from the previous pair Cn-1 and Dn-1, respectively, for n = 1, 2, …, 16, using the schedule of “left circular shifts” of the previous block.

  • ¨ C0 = 1111000011001100101010101111 D0 = 0101010101100110011110001111
  • ¨ C1 = 1110000110011001010101011111 D1 = 1010101011001100111100011110
  • ¨ C2 = 1100001100110010101010111111 D2 = 0101010110011001111000111101
  • ¨ C3 = 0000110011001010101011111111 D3 = 0101011001100111100011110101
  • ¨ C4 = 0011001100101010101111111100 D4 = 0101100110011110001111010101
  • ¨ C5 = 1100110010101010111111110000 D5 = 0110011001111000111101010101
  • ¨ C6 = 0011001010101011111111000011 D6 = 1001100111100011110101010101
  • ¨ C7 = 1100101010101111111100001100 D7 = 0110011110001111010101010110
  • ¨ C8 = 0010101010111111110000110011 D8 = 1001111000111101010101011001
  • ¨ C16 = 1111000011001100101010101111 D16 = 0101010101100110011110001111
  • ¨ C15 = 1111100001100110010101010111 D15 = 1010101010110011001111000111
  • ¨ C14 = 1111111000011001100101010101 D14 = 1110101010101100110011110001
  • ¨ C13 = 0111111110000110011001010101 D13 = 0111101010101011001100111100
  • ¨ C12 = 0101111111100001100110010101 D12 = 0001111010101010110011001111
  • ¨ C11 = 0101011111111000011001100101 D11 = 1100011110101010101100110011
  • ¨ C9 = 0101010101111111100001100110 D9 = 0011110001111010101010110011
  • ¨ C10 = 0101010111111110000110011001 D10 = 1111000111101010101011001100
    • ¨ For each round starting from 1 to 16, the permutation is performed according to table PC-2 and it is applied to pairs formed as CnDn. Every pair consists of 56 bits, after applying PC-2 48 bits are generated as shown below:

K2 = 011110 011010 111011 011001 110110 111100 100111 100101

K3 = 010101 011111 110010 001010 010000 101100 111110 011001

K4 = 011100 101010 110111 010110 110110 110011 010100 011101

K5 = 011111 001110 110000 000111 111010 110101 001110 101000

K6 = 011000 111010 010100 111110 010100 000111 101100 101111

K7 = 111011 001000 010010 110111 111101 100001 100010 111100

K8 = 111101 111000 101000 111010 110000 010011 101111 111011

K9 = 111000 001101 101111 101011 111011 011110 011110 000001

K10 = 101100 011111 001101 000111 101110 100100 011001 001111

K11 = 001000 010101 111111 010011 110111 101101 001110 000110

K12 = 011101 010111 000111 110101 100101 000110 011111 101001

K13 = 100101 111100 010111 010001 111110 101011 101001 000001

K14 = 010111 110100 001110 110111 111100 101110 011100 111010

K15 = 101111 111001 000110 001101 001111 010011 111100 001010

K16 = 110010 110011 110110 001011 000011 100001 011111 110101

 

Step 2: Encrypt each data block consisting of 64-bit.

 

Initial permutation IP is applied on the given message M having length of 64 bits. The 58th bit goes as the first bit. Then 50th bit is taken and moved as the second bit. Last bit is the 7th bit of original data

 

  • ¨ After applying the initial permutation,
  • ¨ M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

 

After applying IP,

 

1100 1100 0000 0000 1100 1100 1111 1111 1111 0000 1010 1010 1111 0000 1010 1010

 

  • ¨ After permutation separate left 32 bits denote as L0, and a right 32 bits denote as R0.
  • ¨ L0 = 1100 1100 0000 0000 1100 1100 1111 1111 R0 = 1111 0000 1010 1010 1111 0000 1010 1010
  • ¨ 16 iterations are performed. 1<=n<=16. 32 bits data block and a 48 bits key Kn produces a 32 bits block.

 

Generate Ln and Rn

  • ¨ Consider + as XOR addition,
  • ¨ Ln = Rn-1   Rn = Ln-1 + f(Rn-1,Kn)
  • ¨ for n = 16, the block produced is L16R16. Consider n = 1,
  • ¨ K1 = 000110 110000 001011 101111 111111 000111 000001 110010 L1 = R0 = 1111 0000 1010 1010 1111 0000 1010 1010

 

R1 = L0 + f(R0,K1)

 

How function f works?

  • ¨ In first step, every Rn-1 gets expanded to 48 bits from 32 bits. For that some bits need to be repeated in Rn-1 .
  • ¨ Use the expand table. Thus E(Rn-1) has input as clock of 32 bits, and output as block of 48 bits.
  • ¨ E(R0) is:
  • ¨ R0 = 1111 0000 1010 1010 1111 0000 1010 1010

E(R0) = 011110 100001 010101 010101 011110 100001 010101 010101

  • ¨ For function f, generated bits of E(Rn-1) and Kn (key pertaining to the round) are XORed.
  • ¨ Kn + E(Rn-1).
  • ¨ Out of 48 bits, Form 8 groups consisting of 6 bits. These 6 bits forms combination of row and column in “S boxes”. For every group there is a separate S box. A 4 bit number is stored at the intersection of row and column. The new 4 bits replace the 6 bits and all eight groups form 32 bits.
  • ¨ Kn + E(Rn-1) =B1B2B3B4B5B6B7B8, All Bi comprises of 6 bits.
  • ¨ S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8)

where Si(Bi) refers to the i-th S box.

  • ¨ S1, S2,…, S8, has input of 6-bits and generates a 4-bit block.
  • ¨ S1(B) works as follows:

The first bit combined with last bit in block B represents(00,01,10,11) in binary correspondingly 0,1,2,3 in decimal represented as i. The middle 4 bits of B corresponds to 0 to 15 in decimal (binary 0000 to 1111) represented as j. Check the corresponding S box for intersection of the row(ith in this case) with column(j-th in this case), the number is between 0 to 15 and can be depicted as a 4 bit block considered as S1(B) output .

 

For example block B = 011100 as input. “0” is the first bit and “0” is the last bit producing 00 for the row lookup. The in between four bits are “1110” equivalent to decimal 14.So lookup in column number 14. In row 0, column 14 the value stored is 0 in binary 0000. Hence S1(011011) = 0000.

 

 

 

  • ¨ The binary output 011000 010001 011110 111010 100001 100110 010100 100111. results in 0101 1100 1000 0010 1011 0101 1001 0111 after passing through S-box.
  • ¨ The last step is to permute output of S-box:

The permutation is applied as per table P. Input is of 32-bit and output is of 32-bit.

  • ¨ P
  • ¨ = 1100 1100 0000 0000 1100 1100 1111 1111 + 0010 0011 0100 1010 1010 1001 1011 1011 = 1110 1111 0100 1010 0110 0101 0100 0100
  • ¨ For the second round, assign L2 = R1 and compute R2 =L1 + f(R1, K2), and repeat till round 16.
  • ¨ After round sixteen, L16 and R16 are generated. The order is reversed to generate the 64-bit block R16L16
  • ¨ Finally IP-1 is applied for permutation

Bit 40 takes first bit position, bit 8 takes second bit position, until bit 25 occupies last position.

 

At the end of round 16:

 

L16 = 0100 0011 0100 0010 0011 0010 0011 0100

R16 = 0000 1010 0100 1100 1101 1001 1001 0101

Order must be reversed and the final permutation must be applied:

R16L16 = 00001010 01001100 11011001 10010101 01000011 01000010 00110010 00110100

IP-1 = 10000101 11101000 00010011 01010100 00001111 00001010 10110100 00000101

Convert to hexadecimal:

85E813540F0AB405.

Given M = 0123456789ABCDEF, encryption C = 85E813540F0AB405.

 

Decryption:

 

Decryption, inverse operation of encryption follows steps similar to encrytion, but keys are applied in the reverse way.

 

The Strength of DES

  • ¨ The use of 56-Bit keys.
  • n 256 possible keys so brute force attack is impractical.
  • ¨ The Nature of the DES algorithm.
  • n Design criteria for S-boxes were not made public. No one has been successful in finding weakness in S-box.
  • ¨ Timing attacks.
  • n Timing attack exploits that encryption and decryption algorithm takes slightly different amounts of time on different inputs.

Suggested Reading:

 

  1. Cryptography and Network Security Principles and Practice by William Stallings, sixth Edition, PEARSON.
  2. Security in Computing by Charles Pfleeger & Shari Lawrence Pfleeger, fourth Edition, PEARSON.
  3. Network Security by Charlie Kaufman, Radia Perlman, Mike Speciner, second Edition, PHI.
  4. The Complete Reference – Network Security by Roberta Bragg, Mark Rhodes-Ousley & Keith Strassberg, Tata McGraw Hill
  5. Network Security Bible by Eric Cole, Ronald Krutz, James Conley, Wiley
  6. Hacking 6 Exposed by Stuart McClure, Joel Scambray & George Kurtz , Tata McGraw Hill .
  7. www.snort.org
  8. https://nmap.org

 

you can view video on DES(Data Encryption Standard)