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