Lecture 4 - Confidentiality

Overview

• confidentiality - keep the content of the message p secret from an eavesdropper
• let Eve be a passive eavesdropper, who sees everything on the channel but can’t change anything

Terminology

• p - plaintext
• c - ciphertext
• k - secret key
• $E_k()$ - encryption function
• $D_k()$ - decryption function

Historical Cryptography

Caesar Cipher (100-44 BC)

• replace each plaintext letter with a different one, using a fixed offset $k$
  • encryption: $c_i := (p_i + k) \mod 26$
  • decryption: $p_i := (c_i - k) \mod 26$
• not very secure, you can easily brute force it or use frequency analysis (certain keys are used more than others)

Vigenere Cipher (c. 1553)

• encrypts successive letters using a sequence of Caesar ciphers keyed by the letters of a keyword
• for an n-letter “key word” $k$,
  • encryption: $c_i := (p_i + k_{i \mod n}) \mod 26$
  • decryption: $p_i := (c_i - k_{i \mod n}) \mod 26$

Modern Cryptography

One-time Pad (OTP)

• Alice and Bob share a secret, very long string of random bits $k$
  • encryption: $c_i := p_i \oplus k_i$
  • decryption: $p_i := c_i \oplus k_i$
• pros:
  • provably secure
• cons:
  • can only use one time
  • need to securely exchange the pad beforehand

Stream Cipher

• use a PRG instead of a truly random pad
• a PRG $g_k()$ is practically indistinguishable from a random stream of bits, unless you know $k$
• Alice and Bob choose $k()$, share secret key $k$
  • encryption: $s := g_k(); c_i := p_i \oplus s_i$
  • decryption: $s := g_k(); p_i := c_i \oplus s_i$
• can’t reuse keys
• can’t reuse PRG output bits
• no way to prove that secure PRGs even exist

Block Cipher

• consists of a function that encrypts fixed-size (n-bit) blocks with a reusable key $k$:
  • $E_k(p) : \{0,1\}^{|k|} \times \{0,1\}^n \rightarrow \{0,1\}^n$
• and an inverse function that decrypts the blocks w hen used with same key:
  • $D_k(c) = E_k^{-1}(c) : \{0,1\}^{|k|} \times \{0,1\}^n \rightarrow \{0,1\}^n$
• such that $\forall k : D_k(E_k(p)) = p$
• in effect, $k$ selects one permutation from the set of $2^n!$ possible permutations of $E$‘s domain
• pseudorandom permutation (PRP) - a function that cannot practically be distinguished from a truly random permutation unless you know $k$
• like PRFs, we don’t know if PRPs actually exist

AES Block Cipher

• Advanced Encryption Standard
  • today’s most common block cipher
  • standardized by NIST in 2001 after winning a long, public international design competition
  • efficient in both SW and HW
  • widely believed to be a secure PRP
• fixed block size: 128 bits
• variable key size: 128, 192, or 256 bits
• 10, 12, or 14 rounds (based on key size)
• generates $r := \text{ \# rounds}$ subkeys from $k$
• performs same set of operations $r$ times, each with a different subkey

Handling Arbitrary-Length Messages

Padding

• add n bits of padding of value n to get up to the block size (add entire block of padding if message ends exactly at the end of a block)

Cipher Modes

Flawed Approach

• encrypted codebook (ECB) mode
  • simply encrypt each block independently
    • $c_i := E_k(p_i)$
  • every block containing the same plaintext is the same block of ciphertext

Cipher-Block Chaining (CBC) Mode

• “chains” ciphertexts to obscure later ones
• choose a random initialization vector (IV)
  • encrypt: $c_0 := \text{IV}; c_i := E_k(p_i \oplus c_{i - 1})$
  • decrypt: $p_i := D_k(c_i) \oplus c_{i - 1}$

Counter (CTR) Mode

• turns a block cipher into a stream cipher
• generate keystreams $s$ for $k$ and unique nonce:
  • $s := E_k(\text{nonce} \parallel 0) \parallel E_k(\text{nonce} \parallel 1) \parallel E_k(\text{nonce} \parallel 2) \parallel \dots$
  • encrypt: $c := p \oplus s$
  • decrypt: $p := c \oplus s$
• can’t repeat nonce with same key

Getting Both Confidentiality and Integrity

• integrity: use a secure PRF $f()$ as a verifier
  • in practice, something like HMAC-SHA-256
• confidentiality: construct $E()$ and $D()$ from secure PRG (stream cipher) or secure PRP (block cipher) with appropriate padding/cipher mode
  • in practice, something like AES-128 in CTR mode