Data Encryption Standard (DES)

---

Data Encryption Standard (DES) is a symmetric block cipher which encrypts data in 64-bit blocks.

• aka Data Encryption Algorithm (DEA)
• developed by IBM in early 1970s
• US gov standard until 1990s
• DES is a Feistel cipher
• uses a 56-bit key
• the length of key determines the strength of the algorithm
• was compromised and is no longer used
  • succeeded by triple DES

Basic Concepts

1. Data is divided into 64-bit blocks
2. the data is then manipulated by 16 separate steps of encryption
   • involve substitutions, bit-shifting, and logical operations using a 56-bit key
3. data is then further scrambled using a swapping algorithm
4. data is then transposed one last time

Key Schedule Algorithm

• the key schedule algorithm is used to generate subkeys
• to generate keys for each round:
  • 56-bit key is split into two 28-bit halves
  • halves are circularly shifted after each round by 1 or 2 bits
  • 48-bits from the first two halves are selected and permuted to form the round key (subkey)
    • means there is a different key for each round
    • is derived from the previous round key

Substitution Boxes

• DES uses eight S-boxes
  • are substitution boxes that are lookup tables
  • each S-box has a table that determines what to substitute the bits passed into it for
  • each item passed into the box is substituted with the item that matches it in the lookup table
  • each s-box takes in 6 bits produces 4 bits
    • the middle 4 bits of the 6-bit input are used to lookup the 4-bit replacement
  • 8 S-boxes taken together map 48 bits to 32 bits
    • each can be viewed as an array of 4 rows and 16 columns, with one nibble (4‐bit value) stored in each of the 64 positions
      • each of its four rows is a permutation of the hexadecimal digits

DES S-box 1 (in Hexadecimal)

• six-bit input to S-box is denoted
• first and last input bits are used to index the row
  • while the middle four bits index the column
• output is in hex

Round F Function

• the round function works as follows:
  1. Expand the 32-bit half that was input to 48-bits
     • done by replicating some bits
  2. XOR the resultant 48 bits with the 48-bit round key
  3. Split the result into eight 6-bit sections
  4. pass each portion through a different S-box
     • each s-box produces a 4-bit output, giving 32 output bits
  5. transpose the output bits
• above is done for each round
• DES has 16 rounds
• only reason DES is not secure is the short key
  • 56-bit key is not long enough to prevent a brute force attack
• has a key space of
  • the total number of possible keys

One Round of DES

• Each number indicates the number of bits

• DES round function can be written as
  • is the P-box permutation
  • is the S-boxes substitution
  • is the expansion permutation
  • is the right half
  • is the subkey/round key
• the new left half is simply the old right half
• the expansion permutation expands its input from 32 to 48 bits, and the subkey is then XORed with the result
  • permutes the 32 input bits of input, with the expansion from 32 to 48 bits achieved by repeating some of the input bits in the output
  • plays an important role in diffusion within a block
• The 48-bit output of the expansion (XOR) step is fed into the S-boxes, which serve to compress the result down to 32-bits
• 32-bit output is then passed through the P-box permutation
• Finally, the 32-bit output of the P-box is XORed with the old left half to obtain the new right half
• S-boxes (and XOR of subkey) serve to provide confusion

Vulnerabilities

• 3 main attacks:
  • brute-force attack
    • given a pair of plaintext and ciphertext blocks (), the adversary needs to test, in the worst case, keys to find a key such that
  • differential cryptanalysis
  • linear analysis