Alice Zeke Bob
plaintext -> [ E ] -------------/\/\/\/\-------- [ D ] ---> plaintext
| (ciphertext) |
key key
|-- assumed secure-| |--assumed secure --|
Review of model
- Alice snds msg to Bob, Zeke can spy.
- E_k(x) is encryption of x with key k
- D_k(y) is decrtyption of y with key k
- E_k, D_k are inverses: D_k( E_k(x) ) = x
When encryption fails, usually because plaintext gets leaked; find bug in encryption program
Speces
- Block size: 64 bits
- Key size: 56 bits
- Issue: adv. can search space for $50k in hardware in a few weeks
- Expensive, but doable
- Moore's law; becomes easier to break as CPUs get faster
- Feistel network, 16 rounds
History:1978, NSA (Nat'l Security Agency) and IBM design
- US govt standard, adopted around the world
- Others worried about "backdoor"... why would NSA let other countries use it?
- There was no backdoor
- NSA knew of attacks no one else did; secrecy prevented non-publicly known attacks
- Designed to be slow in software (bit operations, masking, shifting)
- Fast in hardware
- However, almost always implemented in sw
Making DES keys bigger
- Triple-DES, encrypt with 3 keys
- Step 1: E_k1 [encrypt with first key]
- Step 2: D_k2 [decrypt with second key]
- Step 3: E_k3 [encrypt with third key]
- If use same key, k1 = k2 = k3
- Same as DES with k1 [first and second steps cancel]
- Backwards compatible with old DES
- Sometimes k1 = k3, but doesn't weaken cipher (explained next)
Meet in the middle attack (M-I-M).
- c = E_k2( E_k1(p) )
- c = ciphertext, p = plaintext
Attack: Assume you have a few plaintext/ciphertext pairs
- c = E_k2( E_k1(p) )
- Thus, look for pairs where D_k2(c) = E_k1(p)
- This is true for 2^48 key pairs
- Looking for keys that decrypt each other
Attacker's Method
- Attacker has access to pairs of plaintext p and ciphertext c
- Wants to find k1 and k2
- 1: Decrypt c with every possible key. Make table of k2 and D_k2(c).
- 2^56 possible keys
- 2^64 possible values for decryption
Table:
k_2 D_k2(c)
0 b_blah1
1 c_blah2
2 a_blah3
- 2: invert table (index by decrypted text). Sort by D_k2(c), takes linear time (use hash table)
Table:
D_k2(c) k_2
a_blah3 2
b_blah1 0
c_blah2 1
- 3: For each possible k1 (2^56 possible)
- x = E_k1(p)
- Use inverted table to find k_2 such that D_k2(c) = x
- Might find one, might not
- If do, have k1, k2 pairs such that E_k1(p) = x = D_k2(c)
- Get about 2^48 candidates (possible k1, k2 pairs)
- 4: Exhaustive search over all 2^48 (k1, k2) pairs
Result
- M-I-M breaks double-DES in ~2^56 steps
- Takes ~2^56 steps to generate tables, find pairs (only 2^48 to test pairs)
- Assumes adv. has 2 or more plaintext/ciphertext pairs
- Similar attack "breaks" triple-DES in 2^112 time
- Idea: you approach from both sides, meet in middle. Each stage has 2^56 bits of protection.
- Much easier to do 2 runs of 2^56 than one run of 2^112.
- So, double-DES falls in ~2^56 time. Triple in 2^112.
- Thus, having k1 = k3 doesn't matter.
Double
| |
| |
| | 2^56 protection
[...] V
|
|
[...] ^
| | 2^56 protection
| |
| |
Triple
|
[ ] | 2^56
|
|
V
[ ] ^
|
| 2^112
|
[ ] |
|
|
Like tunneling through from both sides... 2 * 2^56 is much much easier than 2^112. Likewise, 2^56 + 2^112 is easier than 2^168
By number of bits
- 40: possible with PC, month or two
- 50: possible with $100k in hardware
- 60: large corporation (like MS) or the government
- 70: more than enough for now.
Every bit doubles search space
- But computers get twice as fast in 18 months! (Moore's law)
- So, each 18 months, lose 1 bit of protection
Why 160 bits for SHA-1?
- Some attacks use birthday paradox
- After 2^(k/2) tries, find coincidence. Takes sqrt(N) time to find coincidence in hashing.
- Coincidence: Hash(x1) = Hash(x2) and x1, x2 not equal
- Find coincidence in SHA-1 in 2^(160/2) = 2^80 time. More than enough security for now
Security worries
- Quantum computing: get a 2^30 improvement in codebreaking
- Moore's law: lose 1 bit of security every 18 months
- DES: want cipher with more bits, faster
US govt standard, 2001
- Open competition for best cipher
- Winner: Rijndael, designed by Belgians
- Interesting: US using non-US cipher
Specs
- Variable key size and block size, 128 - 256 bits
- Ten rounds, not Feistel design (this is unorthodox)
- Pro: simple, each step does 1 thing
How it works
- Make a 4x4 square, 8-bit value in each cell (256 bits)
- Each round
- 1: run each byte throughnon-linear function (a lookup table)
- If linear, break cipher with linear algebra
- 2: mix step
- a) circular shift ith row to the right by i. First row shifts one, second row shifts 2, etc. Wraps around.
- b) multiply each column by a 4x4 matrix (linear function of 4 bytes to 4 bytes)
- 3: XOR in the key
- Decrypt: run backwards
- Much, much faster than DES
- Uses lookup tables, and operates on bytes, not bits
How to encrypt large data, given block cipher?
Electronic code book (ECB)
- Obvious: encrypt each block of plaintext. p1 -> c1, p2 -> c2...
- BAD
- Same plaintext, get same ciphertext.
- Gives adversary info (if you sent same msg twice, or patterns in input, etc.)
- Subject to rearrangement attacks
- Don't want adversary to make controlled changes
- Want completely random changes to plaintext if ciphertext change
