DES

Introduction

Data Encryption Standard (DES) is a 16-round Feistel network, and it uses the same round function in all rounds. In addition, the round function is basically an SPN.

It uses different sub-keys in each round, each derived from the master key. And this process is called Key Expansion.

DES Round (Mangler) Function

Computation of $f(k_i,R)$, where $k_i \in \{0,1\}^{48}$ is a 48-bit sub-key and $R \in \{0,1\}^{32}$

• $E$: Expansion Function
  • $R$ is expanded to 48-bit value $R^\prime \coloneq E(R)$
  • Duplicate half of the bit of $R$
• Key Mixing
  • Expanded result is XOR-ed with the sub-key $R^\prime \oplus k_i$
  • The resulting value is divided into 8 blocks, each with 6 bits, and fed into the S-boxes
• S-boxes
  • Each S-box takes 6 input bits, and output 4 bits
  • Outputs from 8 S-boxes gives a 32-bit result
  • 1-bit of input changes results in at least 2 bits of output changes.
• Mixing Permutation
  • The 4 bits of output from any S-box affect the input to 6 S-boxes in the next round

    graph TD
  input["32-bit input"]
  subkey["48-bit sub-key"]
  e(("E"))
  inter["48-bit intermediate"]
  inter2["48-bit intermediate"]
  inter3["32-bit intermediate"]
  xor(("XOR"))
  s1["s<sub>1</sub>"]
  s2["s<sub>2</sub>"]
  s3["s<sub>3</sub>"]
  s4["s<sub>4</sub>"]
  s5["s<sub>5</sub>"]
  s6["s<sub>6</sub>"]
  s7["s<sub>7</sub>"]
  s8["s<sub>8</sub>"]
  output["32-bit output"]

  input --> e --> inter --> xor
  subkey --> xor --> inter2

  inter2 --> s1 --> inter3
  inter2 --> s2 --> inter3
  inter2 --> s3 --> inter3
  inter2 --> s4 --> inter3
  inter2 --> s5 --> inter3
  inter2 --> s6 --> inter3
  inter2 --> s7 --> inter3
  inter2 --> s8 --> inter3

  inter3 --> |Shuffle|output
  

Expansion Function

$E$ is an expansion function, which expands a block of 32 bits to a block of 48 bits. The expansion is shown in the picture:

Key Schedule

There are a 56-bit master key, and 48-bit sub-key in each round.

Each sub-key takes 24 bits from the left half of the master key, and 24 bits from the right half of the master key.

S-boxes

Each S-box can be viewed as a table of 4 rows and 16 columns, and each cell contains a 4-bit entry.

For a 6-bit input, the first and last bits defines the row number, and the inner four bits define the column number.

DES S-boxes have the following properties:

1. Each S-box is 4-to-1 (4 inputs are mapped to each possible output)
2. Each row contains each 16 possible 4-bit string
3. Changing 1 bit of input changes at least 2 bits of output

Mixing Permutation

The 4 bits of output from any S-box affect the input to 6 S-boxes in the next round. This is possible because of the expansion function.

Security of DES

The key of DES, which is 56-bit, is too short, and brute-force is possible.

To improve the security of DES, 3DES is developed, which runs DES three rounds using two or three keys.