Data Encryption Standard

DES is the best studied symmetric key algorithm

---

• Overview
• Internal Structure of DES
  • initial and final permutation
  • the $f$-function
  • key schedule
• Decryption
  • reversed key schedule
• Security
  • Exhaustive Key Search
  • Weak Keys
  • Analytical Attacks
• Implementations
• Alternatives
  • 2DES
  • 3DES

---

Overview

Fiestel Network paradigm of block ciphers

• $L_i=R_{i-1}$

• $R_i=L_{i-1}\oplus f(R_{i-1},K_i)$

• advantageous since encryption and decryption are very similar

• thing of $f$ as a pseudorandom generator

• each round bijectively maps input to output even if $f$ is not bijective (it is surjective)

Internal Structure of DES

Initial and Final Permutation

$IP$ and $I{P}^{-1}$ add no additional security but are 2 bitwise permutations before and after the feistel network

The $f$-function

E-box: $[X_i,X_{i+1},X_{i+2},X_{i+3}]\to [X_{i-1},X_i,X_{i+1},X_{i+2},X_{i+3},X_{i+4}]$

• increases the diffusion behaviour of DES since certain input bits influence two different output locations

S-box: all S boxes in a round are different

• core of the cryptographic strength
• only non-linear element and provide confusion
• criteria
  1. no single output bit should be too close to a linear combination of the input bits
  2. if the lowest and highest bits of input are fixed and the four middle bits are varied, each of the 4-bit output values must occur exactly once
  3. if two inputs to an s-box differ in exactly one bit their outputs must differ in at least two bits
  4. If two inputs to an S-box differ in the two middle bits, their outputs must differ in at least two bits.
  5. If two inputs to an S-box differ in their first two bits and are identical in their last two bits, the two outputs must be different.
  6. For any nonzero 6-bit difference between inputs, no more than 8 of the 32 pairs of inputs exhibiting that difference may result in the same output difference.
  7. A collision (zero output difference) at the 32-bit output of the eight S-boxes is only possible for three adjacent S-boxes.
• non linearity $S(a)\oplus S(b)\ne S(a\oplus b)$

P-permutation: introduces diffusion

• ensures by end of 5th round every bit is a function of every plaintext bit and every key bit

Key Schedule

• derives 16 rounds keys of 48 bits from 56-bit master key (every 8th bit is used as odd parity bit over previous 7 bits for total 64-bit master key)

1. initial permutation $PC-1$
2. split into two halves $C_0$ and $D_0$
3. start 16 round key schedule
   1. with each round the two halves are cyclically shifted by 1 bit id $i$ (round index) is a perfect square
   2. other wise rotated left by 2
   3. total rotation positions are $4\cdot 1+12\cdot 2=28$ which gives us $C_0=C_{16}$ and same for $D$ (this is useful for decryption)
4. Each round key comes from a permutation on $C_i,D_i$ given by $PC-2$ (same permutation)

Decryption

• essentially same as encryption, just key schedule needs to be reversed

Reversed Key Schedule

from $K$ generate $k_{16}$

$$\begin{array}{rl}{k}_{16}& =PC-2(C_{16},D_{16})\\ & =PC-2(C_0,D_0)\\ & =PC-2(PC-1(K))\end{array}$$

and the remaining can be derived with right shift on $(C_0,D_0)$