07computer and network security--Crypto Concepts

The course is mainly about Crypto Concepts.Generally covered Symmetric encryption, Public key encryption, and TLS;Public key cryptography:Public-key encryption,Building block:trapdoor permutations;A brief sample of advanced crypto:Protocols,Magical applications.

1.Crypto Concepts Symmetric encryption, Public key encryption, and TLS

2.Cryptography Is: A tremendous tool The basis for many security mechanisms Is not: The solution to all security problems Reliable unless implemented and used properly Something you should try to invent yourself

3.Goal 1: Secure communication no eavesdropping no tampering

4.Secure Sockets Layer / TLS Standard for Internet security Goal: “... provide privacy and reliability between two communicating applications” Two main parts 1. Handshake Protocol: Establish shared secret key using public-key cryptography 2. Record Layer: Transmit data using negotiated key Our starting point: Using a key for encryption and integrity

5.Goal 2: protected files Disk File 1 File 2 Alice Alice No eavesdropping No tampering Analogous to secure communication: Alice today sends a message to Alice tomorrow

6.Building block: symmetric cipher E, D: cipher k: secret key (e.g. 128 bits) m, c: plaintext, ciphertext n: nonce (non-repeating) Encryption algorithm is publicly known ⇒ never use a proprietary cipher Alice E m, n E(k,m,n)=c Bob D c, n D(k,c,n)=m k k nonce

7.Use Cases Single use key : (one time key) Key is only used to encrypt one message encrypted email: new key generated for every email No need for nonce (set to 0) Multi use key : (many time key) Key used to encrypt multiple messages SSL: same key used to encrypt many packets Need either unique nonce or random nonce

8.First example: One Time Pad (single use key) Vernam (1917) 0 1 0 1 1 1 0 0 0 1 Key: 1 1 0 0 0 1 1 0 0 0 Plaintext:  1 0 0 1 1 0 1 0 0 1 Ciphertext: Encryption: c = E(k, m) = m ⨁ k Decryption: D(k, c) = c ⨁ k = (m ⨁ k) ⨁k = m

9.One Time Pad (OTP) Security Shannon (1949): OTP is “secure” against one-time eavesdropping without key, ciphertext reveals no “information” about plaintext Problem : OTP key is as long as the message

10.Stream ciphers (single use key) Problem: OTP key is as long as the message Solution : Pseudo random key -- stream ciphers Examples: ChaCha , Sosemanuk , … (one-time if no nonce) key PRG message  ciphertext c  PRG (k)  m

11.Dangers in using stream ciphers One time key !! “Two time pad” is insecure: c 1  m 1  PRG(k) c 2  m 2  PRG(k) Eavesdropper does: c 1  c 2  m 1  m 2 Enough redundant information in English that: m 1  m 2  m 1 , m 2 What if want to use same key to encrypt two files?

12.Block ciphers: crypto work horse E, D CT Block n bits PT Block n bits Key k Bits Canonical examples: 3DES: n= 64 bits, k = 168 bits AES: n=128 bits, k = 128, 192, 256 bits

13.Block Ciphers Built by Iteration R( k,m ): round function for 3DES (n=48), for AES-128 (n=10) key k key expansion k 1 k 2 k 3 k n R(k 1 , ) R(k 2 , ) R(k 3 , ) R( k n , ) m c

14.Example: AES128 input : 128-bit block m, 128-bit key k. output : 128-bit block c. Difficult to design: must resist subtle attacks  differential attacks, linear attacks, brute-force, … key k key expansion k 0 k 1 k 2 k 10 m c ⊕ π ⊕ π ⊕ π ⊕ ’

15.Incorrect use of block ciphers Electronic Code Book (ECB): Problem : if m 1 =m 2 then c 1 =c 2 PT: CT: m 1 m 2 c 1 c 2

16.In pictures

17.CTR mode encryption (eavesdropping security) Counter mode with a random IV: (parallel encryption) m[0] m[1] … E(k,IV) E(k,IV+1) … m[L] E(k,IV+L)  c[0] c[1] … c[L] IV IV ciphertext Why is this secure for multiple messages? See the crypto course (cs255)

18.Performance OpenSSL on Intel Haswell, 2.3 GHz ( Linux) Cipher Block/key size Speed (MB/sec) ChaCha 408 3DES 64/168 30 AES128 128/128 176 AES256 128/256 135 block stream (w/o AES-NI)

19.A Warning eavesdropping security is insufficient for most applications Need also to defend against active (tampering) attacks. CTR mode is insecure against active attacks! Next: methods to ensure message integrity

20.Message Integrity: MACs Goal: provide message integrity. No confidentiality. ex: Protecting public binaries on disk. Alice Bob k k m essage m tag Generate tag: tag  S(k, m) Verify tag: V (k, m, tag) = `yes’ ?

21.Construction: HMAC (Hash-MAC) Most widely used MAC on the Internet. H: hash function. example : SHA-256 ; output is 256 bits Building a MAC out of a hash function: Standardized method: HMAC S( k, msg ) = H ( kopad ‖ H( kipad ‖ msg ) )

22.SHA-256: Merkle-Damgard h(t, m[ i ]): compression function Thm 1: if h is collision resistant then so is H “ Thm 2”: if h is a “PRF” then HMAC is a secure MAC h h h m[0] m[1] m[2] m[3] h IV (fixed) H(m)

23.Why is this MAC construction secure? … see the crypto course (cs255)

24.Combining MAC and ENC (Auth. Enc.) Encryption key k E . MAC key = k I Option 1 : (SSL) Option 2 : ( IPsec ) Option 3 : (SSH) msg m msg m MAC enc k E MAC( k I , m) msg m Enc k E MAC MAC( k I , c) msg m enc k E MAC MAC( k I , m) always correct

25.AEAD : Auth. Enc. with Assoc. Data AES-GCM : CTR mode encryption then MAC (MAC accelerated via Intel’s PCLMULQDQ instruction) AEAD: encrypted data associated data authenticated encrypted

26.Example AES-GCM encryption function int encrypt ( unsigned char * key , // key unsigned char * iv , int iv_len , // nonce unsigned char * plaintext , int plaintext_len , // plaintext unsigned char * aad , int aad_len , // assoc. data unsigned char * ciphertext // output ct )

27.Generating Randomness (e.g. keys, nonces ) Pseudo random generators in practice: (e.g. /dev/random) Continuously add entropy to internal state Entropy sources: Hardware RNG: Intel RdRand inst. (Ivy Bridge). 3Gb/sec. Timing: hardware interrupts (keyboard, mouse)

28.Summary Shared secret key: Used for secure communication and document encryption Encryption : (eavesdropping security) [should not be used standalone] One-time key: stream ciphers, CTR with fixed IV Many-time key: CTR with random IV Integrity : HMAC or CW-MAC Authenticated encryption : encrypt-then-MAC using GCM

29.Crypto Concepts Public key cryptography