Vitaly Shmatikov CS 361S Overview of Symmetric Encryptionslide 2 Reading Assignment Read Kaufman 2.1-4 and 4.2slide 3 Basic Problem ? ----- ----- ----- Given: both parties already know the same secret How is this achieved in practice? Goal: send a message confidentially Any communication system that aims to guarantee confidentiality must solve this problemslide 4 Kerckhoffs's Principle An encryption scheme should be secure even if enemy knows everything about it except the key • Attacker knows all algorithms • Attacker does not know random numbers Do not rely on secrecy of the algorithms (“security by obscurity”) Full name: Jean-Guillaume-Hubert-Victor-François-Alexandre-Auguste Kerckhoffs von Nieuwenhof Easy lesson: use a good random number generator!slide 5 Randomness Matters!slide 6 One-Time Pad (Vernam Cipher) = 10111101… ----- ----- ----- = 00110010… 10001111…  00110010… =  10111101… Key is a random bit sequence as long as the plaintext Encrypt by bitwise XOR of plaintext and key: ciphertext = plaintext  key Decrypt by bitwise XOR of ciphertext and key: ciphertext  key = (plaintext  key)  key = plaintext  (key  key) = plaintext Cipher achieves perfect secrecy if and only if there are as many possible keys as possible plaintexts, and every key is equally likely (Claude Shannon, 1949)slide 7 Advantages of One-Time Pad Easy to compute • Encryption and decryption are the same operation • Bitwise XOR is very cheap to compute As secure as theoretically possible • Given a ciphertext, all plaintexts are equally likely, regardless of attacker’s computational resources • …if and only if the key sequence is truly random – True randomness is expensive to obtain in large quantities • …if and only if each key is as long as the plaintext – But how do the sender and the receiver communicate the key to each other? Where do they store the key?slide 8 Problems with One-Time Pad Key must be as long as the plaintext • Impractical in most realistic scenarios • Still used for diplomatic and intelligence traffic Does not guarantee integrity • One-time pad only guarantees confidentiality • Attacker cannot recover plaintext, but can easily change it to something else Insecure if keys are reused • Attacker can obtain XOR of plaintextsslide 9 No Integrity = 10111101… ----- ----- ----- = 00110010… 10001111…  00110010… =  10111101… Key is a random bit sequence as long as the plaintext Encrypt by bitwise XOR of plaintext and key: ciphertext = plaintext  key Decrypt by bitwise XOR of ciphertext and key: ciphertext  key = (plaintext  key)  key = plaintext  (key  key) = plaintext 0 0slide 10 Dangers of Reuse = 00000000… ----- ----- ----- = 00110010… 00110010…  00110010… =  00000000… P1 C1 = 11111111… ----- ----- ----- = 00110010… 11001101…  P2 C2 Learn relationship between plaintexts C1C2 = (P1K)(P2K) = (P1P2)(KK) = P1P2slide 11 Reducing Key Size What to do when it is infeasible to pre-share huge random keys? Use special cryptographic primitives: block ciphers, stream ciphers • Single key can be re-used (with some restrictions) • Not as theoretically secure as one-time padslide 12 Block Ciphers Operates on a single chunk (“block”) of plaintext • For example, 64 bits for DES, 128 bits for AES • Same key is reused for each block (can use short keys) Result should look like a random permutation Not impossible to break, just very expensive • If there is no more efficient algorithm (unproven assumption!), can only break the cipher by brute-force, try-every-possible-key search • Time and cost of breaking the cipher exceed the value and/or useful lifetime of protected informationslide 13 Permutation 1 2 3 4 1 2 3 4 CODE becomes DCEO For N-bit input, N! possible permutations Idea: split plaintext into blocks, for each block use secret key to pick a permutation, rinse and repeat • Without the key, permutation should “look random”slide 14 A Bit of Block Cipher History Playfair and variants (from 1854 until WWII) Feistel structure • “Ladder” structure: split input in half, put one half through the round and XOR with the other half • After 3 random rounds, ciphertext indistinguishable from a random permutation DES: Data Encryption Standard • Invented by IBM, issued as federal standard in 1977 • 64-bit blocks, 56-bit key + 8 bits for parity • Very widely used (usually as 3DES) until recently – 3DES: DES + inverse DES + DES (with 2 or 3 different keys) Textbook Textbookslide 15 DES Operation (Simplified) Block of plaintext S S S S S S S S S S S S Key Add some secret key bits to provide confusion Each S-box transforms its input bits in a “random-looking” way to provide diffusion (spread plaintext bits throughout ciphertext) repeat for several rounds Block of ciphertext Procedure must be reversible (for decryption)slide 16 Remember SHA-1? Current message block Constant value Buffer contains final hash value Very similar to a block cipher, with message itself used as the key for each roundslide 17 Advanced Encryption Standard (AES) US federal standard as of 2001 Based on the Rijndael algorithm 128-bit blocks, keys can be 128, 192 or 256 bits Unlike DES, does not use Feistel structure • The entire block is processed during each round Design uses some clever math • See section 8.5 of the textbook for a concise summaryslide 18 Basic Structure of Rijndael 128-bit plaintext (arranged as 4x4 array of 8-bit bytes) 128-bit key  S shuffle the array (16x16 substitution table) Shift rows shift array rows (1st unchanged, 2nd left by 1, 3rd left by 2, 4th left by 3) add key for this round  Expand key repeat 10 times Mix columns mix 4 bytes in each column (each new byte depends on all bytes in old column)slide 19 Encrypting a Large Message So, we’ve got a good block cipher, but our plaintext is larger than 128-bit block size Electronic Code Book (ECB) mode • Split plaintext into blocks, encrypt each one separately using the block cipher Cipher Block