Author : Paulus Gandung Prakosa (syn1988@sdf.lonestar.org)

Credits : - Ronald L. Rivest (csail.mit.edu)
          - Whitfield Diffie (csail.mit.edu)
          - Martin Hellman (www-ee.stanford.edu)

Symmetric Cryptography

- Secure communication has two parts:
  - Establish a key (public key methods)
  - Encrypt message symmetrically using key
- Symmetric encryption is faster
- Cryptographic scheme is only as good as it's weakest link
- We need to understand strengths and weaknesses of symmetric encryption

DES (Data Encryption Standard)

- 1972 : National Bureau of Standards begins search
- 1975 : DES : Lucifer by IBM, modified by NSA (key reduced from 128 to
  56 bits)
- Approved by NBS '76, ANSI '81
- Renewed every years by NIST
- Now considered obsolete

Flash look deeper about DES (Data Encryption Standard)

- Secure : hard to attack
  - Classic case : given ciphertext, get plaintext
  - Also : given both, get key
  - Achieved through diffusion, confusion

- Easy to implement (in hardware, software)
  - Use a few fast subroutines
  - Decryption uses same routines

- Easy to analyze
  - Prove that certain attacks fail

Flash overview about DES algorithm

- Block cipher : 64-bits at a time
- Initial permutation rearranges 64 bits (no cryptographic effect)
- Encoding is in 16 rounds

Figure 1.0 : Here's the diagram

		[ plaintext ]
		      |
	   [ initial permutation ]
                      |
                 [ round 1 ]
                      |
                 [ round 2 ]
                      |
                 [   ...   ]
                      |
                 [ round 16 ]
                      |
        [  initial permutation ^ -1 ]
                      |
           [ produced ciphertext ]

DES operation every "one round"

- 64-bits divided into left, right halves
- Right half goes through function "f", mixed with key
- Right half added to left half
- Halves swapped (except in one round)

Figure 1.1 : Here the diagram

[ Li-1 ]		[ Ri-1 ]
    |                       |
    |                       |
 [ XOR ]<----[ f ]-----[ append ]
    |                       |
    |                       |
 [ R1 ]                  [ L1 ]

DES description : Inside DES

- Expand right size from 21 to 48 bits (some get reused)
- Add 48 bits of key (chosen by schedule)
- S-boxes : each set of 6 bits reduced by 4
- P-box permutes 32-bits

Figure 1.2 : Here the diagram

	[ Ri-1 ]
            |
      [ expansion ]
            |
         [ XOR ]<---------[ Ki ]
            |
    [ Eight S-boxes ]
            |
        [ P-box ]
            |
        [ Output ]

DES design principles : inversing DES

- Equations for round 'i' : 
  L1 = Ri-1
  R1 = Li-1 XOR f(Ri-1)
- In other words :
  Ri-1 = L1
  Li-1 = R1 XOR f(L1)
- So decryption is th same as encryption
- Last round, no swap, really is the same

Figure 1.3 : DES Inverse diagram (same as Fig. 1.1)

List of DES operation

- ECB = Electronic CodeBook Mode
  - Encrypt each 64-bit block independently
  - Attacker could build codebook
- CBC = Cipher Block Chaining mode
  - Encryption : Ci = Ek(Pi XOR Ci-1)
  - Decryption : Pi = Ci-1 XOR Dk(Ci)
- CFB, OFB : allow byte-wise encryption
  - Cipher FeedBack, Output FeedBack

DES pedestrian attacks : 

- Obvious attack : guess the key (2 ^ 56 keys)
- Complementation property : 2 ^ 55 keys
- 1 million per second : 1100 years
- Time / Memory Tradeoff (Hellman, Martin 1980) :
  - 1 terabyte
  - 5 days

How to destroying DES method :

- Differential cryptanalysis (1990)
- Say you know plaintext, ciphertext pairs
- Difference Dp = P1 XOR P2, Dc = C1 XOR C2
- Distribution of Dc's given Dp may reveal key
- Need lots of pairs to get lots of good Dp's
- Look at pairs, build up key in pieces
- Could find some bits, brute-force for rest

Serving of Praise of DES

- Against 8 round of DES, attack requires : 
  - 2 ^ 14 = 16384 chosen plaintexts
  - 2 ^ 38 known plaintext-ciphertext pairs
- Against 16 round DES, attack requires : 
  - 2 ^ 47 chosen plaintexts, or
  - Roughly 2 ^ 55.1 known plaintext-ciphertext pairs
- Differential cryptanalysis not effective
- Designers knew about it