1 of 14

Lec 3: Data Encryption Standard (I)

2 of 14

DES

  • 1973 — call for proposals for block cipher from National Bureau of Standards (NBS)
    • NBS became National Institute of Standards and Technology (NIST) in 1998
    • No suitable submissions
  • 1974 — 2nd call for proposals from NBS
    • IBM submitted internal design “Lucifer”
  • 1975 — Lucifer published for comment
  • 1976 — Lucifer accepted as standard
  • 1977 — Lucifer formally published as Data Encryption Standard

3 of 14

  • 1970s and early 1980s — wide suscept on design idea (esp. S-boxes), no successful attack
  • 1990 — differential cryptanalysis by Biham and Shamir
    • IBM was (internally) aware of it
    • DES optimized against it
  • 1993 — linear cryptanalysis by Matsui
    • Recovered DES key in 1994
    • Requires huge amount of data (impractical)
  • 1997 — DES key recovered by brute force
    • Key length too short
  • 1998 — abandoned as a federal standard

4 of 14

Why do we still study DES?

  • Historical significance
  • Survived in the form of “triple DES (3DES)” variant until 2023
    • 3DES still used in some legacy implementations
  • Clean design idea (Feistel network) that is still widely used in other contexts
    • Easy to analyze theoretically
  • Bolstered research about cryptanalysis
    • AES designed to specifically resist differential/linear cryptanalysis
    • … But to understand differential/linear cryptanalysis, you need to understand DES first

5 of 14

Design of DES

6 of 14

  •  

7 of 14

Feistel cipher

  •  

8 of 14

  •  

9 of 14

  • Decryption identical to encryption
    • … with round keys in reverse order
  • Theoretical study:
    • Assume round function has some ideal behavior
    • Prove Feistel cipher has some ideal behavior
  • Can also do cryptanalysis on this level
    • “Round-reduced DES insecure regardless of round function”

10 of 14

DES low-level details

  • Need to specify:
  • Initial permutation IP (omitted)
    • No security benefit
    • Hardware efficiency concerns
  • Key schedule KS
  • Round function
    • 1. Expansion E: 32 → 48 bits
    • 2. XOR with round key
    • 3. 8 S-boxes, each 6 → 4 bits
    • 4. Permutation P: 32 → 32 bits

11 of 14

Expansion E and permutation P

  • Expansion E (32 → 48 bits):
    • Duplicate 16 bits
    • Each row is an S-box input
    • Any 2 neighboring S-boxes share 2 positions
  • Permutation P (32 → 32 bits)

12 of 14

  • Principle: S-box output bits spread out in next round
  • S-box 1 output → positions 9, 17, 23, 31 after P → positions 12, 14, 24, 26, 34, 46 after E next round → they affect 6 S-boxes
  • General property: any 4 bits of S-box output after P → 6 positions after E next round → they affect 6 S-boxes

13 of 14

  • Middle 6 bits of S-boxes 1, 2 input → positions 2, 3, 4, 5, 6, 7 before E → positions 7, 20, 21, 29, 12, 28 before P in previous round → they belong to 6 S-boxes (2, 5, 6, 8, 3, 7)
  • General property: any middle 6 bits of S-box output before E → 6 positions before P in previous round → they belong to 6 S-boxes

14 of 14

  • Other structural properties of E and P (see book)