Recall from last lecture• To a first approximation, attackers control network• Today’s lecture: How to defend against this1. Communicate securely despite insecure networks – cryptography2. Secure small parts of network despite wider InternetCryptography• Crypto important tool for securing communication- But often misused- Have to understand what it guarantees and what it doesn’t[Symmetric] Encryption• Encryption keeps communications secret• An encryption algorithm has two functions: E and D- To communicate secretly, parties share secret key K• Given a message M , and a key K :- M is known as the plaintext- E (K , M ) → C (C known as the ciphertext)- D(K , C ) → M- Attacker cannot efficiently derive M from C without K• Note E and D take same argument K- Thus, also sometimes called symmetric encryptionOne-time pad• Share a completely random key K• Encrypt M by XORing with K :E (K , M ) = M ⊕ K• Decrypt by XORing again:D(K , C ) = C ⊕ K• Advantage: Information-theoretically secure- Given C but not K , any M of same length equally likely• Disadvantage: K must be as long as M- Makes distributing K for each message difficultIdea: Computational security• Distribute small K securely (e.g., 128 bits)• Use K to encrypt far larger M (e.g., 1 MByte file)• Given C = E (K , M ), may be only one possible M- If M has redundancy• But believed computationally intractable to find- E.g., could try every possible K , but 2128keys a lot of work!Types of encryption• Stream ciphers – pseudo-random pad- Generate pseudo-random stream of bits from short key- Encrypt/decrypt by XORing as with one-time pad- But NOT one-time PAD! (People who claim so are frauds!)• Most common algorithm type: Block cipher- Operates on fixed-size blocks (e.g., 64 or 128 bits)- Maps plaintext blocks to same size ciphertext blocks- Today should use AES; other algorithms: DES, Blowfish, . . .Example stream cipher (RC4)• Initialization:- S [0 . . . 255] ← permutation h0, . . . 255i (based on key); i ← 0; j ← 0 ;• Generating pseudo-random bytes:i ← (i + 1) mod 256 ;j ← (j + S [i]) mod 256 ;swap S [i] ↔ S [j ] ;return S [(S [i] + S [j ]) mod 256] ;Example stream cipher (RC4)• Initialization:- S [0 . . . 255] ← permutation h0, . . . 255i (based on key); i ← 0; j ← 0 ;• Generating pseudo-random bytes:i ← (i + 1) mod 256 ;j ← (j + S [i]) mod 256 ;swap S [i] ↔ S [j ] ;return S [(S [i] + S [j ]) mod 256] ;Example stream cipher (RC4)• Initialization:- S [0 . . . 255] ← permutation h0, . . . 255i (based on key); i ← 0; j ← 0 ;• Generating pseudo-random bytes:i ← (i + 1) mod 256 ;j ← (j + S [i]) mod 256 ;swap S [i] ↔ S [j ] ;return S [(S [i] + S [j ]) mod 256] ;Example stream cipher (RC4)• Initialization:- S [0 . . . 255] ← permutation h0, . . . 255i (based on key); i ← 0; j ← 0 ;• Generating pseudo-random bytes:i ← (i + 1) mod 256 ;j ← (j + S [i]) mod 256 ;swap S [i] ↔ S [j ] ;return S [(S [i] + S [j ]) mod 256] ;Example stream cipher (RC4)• Initialization:- S [0 . . . 255] ← permutation h0, . . . 255i (based on key); i ← 0; j ← 0 ;• Generating pseudo-random bytes:i ← (i + 1) mod 256 ;j ← (j + S [i]) mod 256 ;swap S [i] ↔ S [j ] ;return S [(S [i] + S [j ]) mod 256] ;RC4 security• Warning: Lecture goal just to give a feel- May omit critical details necessary to use RC4 and otheralgorithms securely• RC4 Goal: Indistinguishable from random sequence- given part of the output stream, it should be intractable todistinguish it from a truly random string• Problems- Second byte of RC4 is 0 with twice expected probability [MS01]- Bad to use many related keys (see WEP 802.11b) [FMS01]- Recommendation: Discard the first 256 bytes of RC4 output[RSA, MS]Example use of stream cipher• Pre-arrange to share secret s with web vendor• Exchange payment information as follows- Send: E (s, “Visa card #3273. . . ”)- Receive: E (s, “Order confirmed, have a nice day”)• Now an eavesdropper can’t figure out your Visa #Wrong!• Let’s say an attacker has the following:- c1= Encrypt(s, “Visa card #3273. . . ”)- c2= Encrypt(s, “Order confirmed, have a nice day”)• Now compute:- m ← c1⊕ c2⊕ “Order confirmed, have a nice day”• Lesson: Never re-use keys with a stream cipher- Similar lesson applies to one-time pads(That’s why they’re called one-time pads.)Example block cipher (blowfish)FFFP1P2P16P17P1832 bit 32 bit32 bit32 bit32 bitPlaintext64 bit 32 bit32 bit64 bitCiphertext13 More Iterations“Feistel network”• Derive F and 18 subkeysfrom Key—P1. . . P18• Divide plaintext block intotwo halves, L0and R0• Ri= Li −1⊕ PiLi= Ri −1⊕ F (Ri)• R17= L16⊕ P17L17= R16⊕ P18• Output L17R17.(Note: This is just to give an idea; it’s not a complete description)Using a block cipher• In practice, message may be more than one block• Encrypt with ECB (electronic code book) mode:- Split plaintext into blocks, and encrypt separatelyEnc Enc Encc1c2c3m1m2m3- Attacker can’t decrypt any of the blocks; message secure• Note: can re-use keys, unlike stream cipher- Every block encrypted with cipher will be secureWrong!• Attacker will learn of repeated plaintext blocks- If transmitting sparse file, will know where non-zeroregions lie• Example: Intercepting military instructions- Most days, send encryption of “nothing to report.”- On eve of battle, send “attack at dawn.”- Attacker will know when battle plans are being madeAnother example [Preneel]Cipher-block chaining (CBC)• IV = initialization vector- Can be 0 if key only ever used to encrypt one message- Choose randomly for each message if key re-used- Can be publicly known (e.g., transmit openly with ciphertext)• c1= E (K , mi⊕ IV ), ci= E (K , mi⊕ ci −1)• Ensures repeated blocks are not encrypted the sameIVEnc Enc Encm1m2m3c1c2c3Encryption modes• CBC, ECB are encryption modes, but there are others• Cipher Feedback (CFB) mode: ci= mi⊕ E (K , ci −1)- Useful for messages that are not multiple of block size• Output Feedback (OFB) mode:- Repeatedly encrypt IV & use result like stream cipher• Counter (CTR) mode: ci= mi⊕ E (K , i)- Useful if you want to encrypt in parallel• Q: Given a shared key, can you transmit files securelyover net by just encrypting them in CBC mode?Problem: Integrity• Attacker can tamper with messages- E.g., corrupt a block to flip a bit in next• What if you delete original
View Full Document
Unlocking...