Skip to main content

Data Encryption Standard (DES)

Block Ciphers​

Encrypt whole block at a time Size varies, often 64 or 128 More common than stream ciphers

Pseudorandom Permutations​

  • Pseudorandom permutation is a function that cannot be distinguished from a random permutation
  • Maps a set of values {0,1}n×{0,1}8→{0,1}n\{0,1\}^n \times \{0,1\}^8 \to \{0,1\}^n
    • For any key, the function F is a bijection
    • There is an efficient algorithm to calculate F(x) for all keys and all messages

Confusion: Obscure the relationship between plaintext, key and ciphertext (lookup table) Diffusion: Influence of each plaintext and key bit is distributed throughout the ciphertext

Where to begin​

  • Confusion is often achieved through substitution
  • Diffusion is usually achieved via permutation. Swapping or otherwise mixing bits or bytes

Feistel Networks​

  • One mechanism used to create block ciphers
  • Developed by Horst Feistel while he worked at IBM
  • Underpins DES, GOST, Blowfish, Twofish and numerous other ciphers

Single Feistel Round​

ADD IMAGE

  • During each round, only half of the block is encrypted
  • F is pseudorandom function

About Feistel Networks​

  • 1 or 2 rounds is not sufficient

That if f is a cryptographically secure pseudorandom function then:

  • 3 rounds are sufficient to make a pseudorandom permutation
  • 4 rounds are sufficient to make a strong pseudorandom permutation

Balanced Feistel networks: L and R are equal sizes Unbalanced Feistel networks: L and R can be different sizes

DES​

1972: NBS (now NIST) put out a call for a US standard for encryption 1974: IBM propose DES, built upon a previous family of ciphers developed by Horst Feistel called Lucifer 1976: NBS accepts an altered version of DES following consultation with NSA

64-bit block size 56-bit key 16 rounds

The f() Function​

Expansion​

Adds diffusion. Increases from 32 to 48 bits to match the round key

Substitution Boxes​

Adds confusion The S-boxes map 6-bit inputs to 4-bit outputs There are 8 S-boxes in total, each in different

S-boxes need to be highly non-linear The previous simple systems of linear equations such as we saw in LFSRs Key design principles

  1. No output bit should be too close to a linear combination of input bits
  2. 1 bit change input should lead to at least 2 bit output
  3. If only the 4 middle bits change, each output must occur exactly once
  4. If the first two bits are different but the last two are identical, the output must differ
  5. For any non-zero difference in input, no more 8/32 inputs exhibiting this difference should share the same output difference
  6. A collision (Zero difference) is only .....

At the end of f(.) is a permutation This moves bits between S-boxes on the next round