Don't get something for nothing
- still need shared secret K
- Leverage 1 shared secret into many shared secrets
One-time pad (only provably secure method)
- A and B generate long string of random bits r0, r1... this is the "one-time pad"
- To encrypt d0, d1, d2... XOR it with one time pad
- d0 XOR r0, d1 XOR r1, etc.
- XOR is a toggle, so to undo it, just apply it again
- To decrypt, just XOR scrambled result with random bits again
- Zeke sees 0 or 1 with 50% chance
- XOR something with random bit, result becomes random (random chance of toggle)
- Z learns nothing about message: perfect confidentiality
Provably secure: Zeke can't guess any better
Huge drawback: consume 1 bit of pad for each bit sent
- Lets you time-shift secret info (get together earlier, make pad)
- Rarely practical (used in Washington-to-Moscow phone line)
- Random data, so won't compress well
- Can't send another pad using a pad: same size, no gain
Obvious "improvement: use pseudorandom numbers. But numbers must look random to adversary.
Worst acronym ever
Important, but often done wrong. Consultant will ask: "Where do you get your numbers from?"
Treat as function that takes small seed and outputs long sequence of bits (deterministic)
- Required property: if adversary watches outputs, still can't guess next bit (do better than random guessing)
- Alg. fails if adv. finds key/seed
- Note: ordinary pseudorandom generators are weak (in UNIX library)
Old principle, accepted as truth
Don't rely on secrecy of alg., rely on secrecy of key
Quantifies probability adv. can guess: he chooses randomly
- Can't quantify chance of guessing alg.
- Modularity: Easier to change key than algorithm (if secret discovered)
- Disclosing alg. allows others to find flaws, tell you it is weak
Needs to be random
- Physical source of randomness
- Cosmic rays, radioactive decays, user mouse movements, TV static, lavarand (picture of lavalamp)
- My thoughts: Use internet? Latencies, ping times? Differences? Number of google hits (google rand?)
- Stock market fluctuations?
Extract randomness
- If bits uncorrelated, just use them or condense bits by hashing
- If have a large value with more than 160 bits of randomness, then SHA-1(value) looks random
seed -----> [ state ] -------> [ f ] --------> output
^ |
| |
|----[g]---|
Have seed and g() go into state. Output of state goes back into g() and f(). Iterative.
Easy method: ith output = MAC(seed, i).
- g() is i++
- f() is MAC
- This is secure, and good enough (recall, can't predict next MAC no matter how many you have seen. So this is secure if MAC is good enough).
Diagram:
seed -> [ seed, i ] ----------> [ MAC ] --------> output
^ |
| |
|--[i++]---|
A, B agree on random secret K
Use K as seed, generate random bits
Use stream of bits as one-time pad
If CPRNG strong, this is a strong cipher
Drawbacks of XOR-based cipher
- Trouble if reuse key. If send x0 XOR r0... and later y0 XOR r0, adv. can XOR these together
- Gets x0 XOR y0. Knows if bits of msg. x and y are the same
- Can use grammatical analysis
- Adversary must know/guess you are reusing key
- Don't use same key in both directions (A to B, and B to A)
- Problem: what if sender/recvr get out of sync in random stream?
Most commonly used cipher; build on a function that encrypts file-size blocks w/ reusable key
Cipher not one-way (need to encrypt and decrypt)
Requirement: can only decrypt (run backwards) if know key
input
|
|
left | right
<-----[ ]----->
| |
| key |
| | v
|---->[f]--->[XOR]
| |
| |
------[ ]------
|
|
|
v
L R
| key |
| | |
encrypt{ |---->[f]---->[XOR] R XOR f(L,key)
| |
| |
. .
. .
. .
L R_scrambled
| key |
| | |
decrypt{ |---->[f]---->[XOR] R XOR f(L,key) XOR f(L,key) = R
| |
| |
. .
. .
. .
L R
Split input into two halves: Left (L) and Right (R)
- F(x,k) is encryption function: encrypts x with key k
- Left half of data passes through (call L1 the new L)
- To decrypt, simply run network again (call L2) the newest L
- L2 = L1, but L1 = L, so L2 = L
- R2 = F(L,k) XOR R1 = F(L,k) XOR [ F(L,k) XOR R ] = R
- The XOR's cancel
- Not good cipher because left half of data passes right through
- Feistel network is its own inverse, no matter F
[ ]
[ L f R ]
| /
--------------
/ |
-------- |
v v
[ ]
[ L f R ]
L output of one network goes to R input of other, and vice versa
Inversion: run backwards (reverse order)
Use different keys for each step
- Why? Makes it harder for adversary (more keys to guess)
- Less points of failure (adv. must guess ALL keys, not just 1)
- Often have a small key "stretched" into a larger one
Tradeoff between goodness of F and number of rounds
- Better F, less rounds needed
