Symmetric-Key Cryptography

CS 161 Fall 2021 - Lecture 10

Computer Science 161

Popa and Weaver

Announcements

• Start recording
• Homework 2 is due Friday, September 24th, 11:59 PM PT
• This was extended from September 17th to give you more time to digest the lecture material.
• Project 1 is due Friday, September 24th, 11:59 PM PT
• Hybrid lectures in Lewis 100 from now on at the normal lecture time
• Professor Popa will still be lecturing on Zoom, but we will stream the Zoom feed to the projector screen, and TAs will be present to pass questions to the instructor

2

Computer Science 161

Popa and Weaver

One-Time Pads

3

• not IND-CPA secure, but a useful tool that will enable us to build an IND-CPA secure scheme

Textbook Chapter 6.2 & 6.3

Computer Science 161

Popa and Weaver

Cryptography Roadmap

• Hash functions
• Pseudorandom number generators
• Public key exchange (e.g. Diffie-Hellman)

4

• Key management (certificates)
• Password management

Computer Science 161

Popa and Weaver

One-Time Pads: Key Generation

5

Alice

K

The key K is a randomly-chosen bitstring.

Recall: We are in the symmetric-key setting, so we’ll assume Alice and Bob both know this key.

Computer Science 161

Popa and Weaver

One-Time Pads: Encryption

6

Alice

K

M

The plaintext M is the bitstring that Alice wants to encrypt.

Idea: Use XOR to scramble up M with the bits of K.

Computer Science 161

Popa and Weaver

One-Time Pads: Encryption

7

Alice

K

M

C

Encryption algorithm: XOR each bit of K with the matching bit in M.

The ciphertext C is the encrypted bitstring that Alice sends to Bob over the insecure channel.

Computer Science 161

Popa and Weaver

One-Time Pads: Decryption

8

Bob

K

C

Bob receives the ciphertext C. Bob knows the key K. How does Bob recover M?

Computer Science 161

Popa and Weaver

One-Time Pads: Decryption

9

Bob

K

C

M

Decryption algorithm: XOR each bit of K with the matching bit in C.

Computer Science 161

Popa and Weaver

One-Time Pad

• KeyGen()
• Randomly generate an n-bit key, where n is the length of your message
• Recall: For today, we assume that Alice and Bob can securely share this key
• For one-time pads, we generate a new key for every message
• Enc(K, M) = K ⊕ M
• Bitwise XOR M and K to produce C
• In other words: XOR the ith bit of the plaintext with the ith bit of the key.
• Ci = Ki ⊕ Mi
• Alice and Bob use a different key for each encryption (this is the “one-time” in one-time pad).
• Dec(K, C) = K ⊕ C
• Bitwise XOR C and K to produce M
• Mi = Ki ⊕ Ci

10

Computer Science 161

Popa and Weaver

One-Time Pad: Correctness

• Correctness: If we encrypt and then decrypt, we should get the original message back

11

Computer Science 161

Popa and Weaver

One-Time Pad: Security

12

Possibility 0: Alice sends Enc(K, M0)

Possibility 1: Alice sends Enc(K, M1)

The ciphertext is C = K ⊕ M0

Therefore, K = C ⊕ M0

The ciphertext is C = K ⊕ M1

Therefore, K = C ⊕ M1

K was chosen randomly, so both possibilities are equally possible

Eve has learned no new information, so the scheme is perfectly secure

Computer Science 161

Popa and Weaver

Two-Time Pads?

13

M0

K

OTP Enc

K ⊕ M0

Alice

Insecure Channel

M1

K

OTP Enc

K ⊕ M1

What if we use the same key K to encrypt two different messages?

Eve sees two ciphertexts over the insecure channel.

Computer Science 161

Popa and Weaver

Two-Time Pads?

14

M0

K

OTP Enc

K ⊕ M0

Alice

Insecure Channel

M1

K

OTP Enc

K ⊕ M1

⊕

(K ⊕ M0) ⊕ (K ⊕ M1)�= M0 ⊕ M1

Eve

If Eve XORs the two ciphertexts, she learns M0 ⊕ M1!

Computer Science 161

Popa and Weaver

Two-Time Pads?

• What if we use the same key twice?
• Alice encrypts M0 and M1 with the same key
• Eve observes K ⊕ M0 and K ⊕ M1
• Eve computes (K ⊕ M0) ⊕ (K ⊕ M1) = M0 ⊕ M1
• Recall the XOR property: the K's cancel out
• Eve has learned M0 ⊕ M1. This is partial information about the messages!
• In words, Eve knows which bits in M0 match bits in M1
• If Eve knows M0, she can deduce M1 (and vice-versa)
• Eve can also guess M0 and check that M1 matches her guess for M0
• Result: One-time pads are not secure if the key is reused
• Alice and Bob must use a different key for every message!

15

Computer Science 161

Popa and Weaver

Impracticality of One-Time Pads

• Problem #1: Key generation
• For security to hold, keys must be randomly generated for every message, and never reused
• Randomness is expensive, as we’ll see later
• Problem #2: Key distribution
• To communicate an n-bit message, we need to securely communicate an n-bit key first
• But if we have a way to securely communicate an n-bit key, we could have communicated the message directly!
• Practical application: Communicate keys in advance
• You have a secure channel now, but you won’t have it later
• Use the secure channel now to communicate keys in advance
• Use one-time pad later to communicate over the insecure channel

16

Computer Science 161

Popa and Weaver

Is one-time pad IND-CPA secure?

​

1. Eve may choose plaintexts to send to Alice and receives their ciphertexts
2. Eve issues a pair of plaintexts M0 and M1 to Alice
3. Alice randomly chooses either M0 or M1 to encrypt and sends the encryption back
1. Alice does not tell Eve which one was encrypted!
4. Eve may again choose plaintexts to send to Alice and receives their ciphertexts
5. Eventually, Eve outputs a guess as to whether Alice encrypted M0 or M1

An encryption scheme is IND-CPA secure if for all polynomial time attackers Eve:

Eve can win with probability <= 1/2 + Ɛ, where Ɛ is negligible.

​

17

M

Enc(K, M)

(repeat)

Alice (challenger)

Eve (adversary)

M0 and M1

Enc(K, Mb)

M

Enc(K, M)

Guess b = 0 or b = 1

(repeat)

pick b

No, because it requires that the scheme is able to reuse a key K without helping the attacker distinguish. In repeat phase, attacker can ask for M₀

Computer Science 161

Popa and Weaver

Traffic Analysis & Side Channels

18

Computer Science 161

Popa and Weaver

Traffic Analysis & Side Channels

• Traffic analysis: Analyzing who is talking to whom and when
• The encryption schemes we’ll be studying do not hide the identity of who you’re talking to
• Side channels: Information about the plaintext revealed as a result of the implementation of the scheme, not the scheme itself
• Modern crypto systems are usually broken through side channels

19

Computer Science 161

Popa and Weaver

Traffic Analysis & Side Channels in Practice: Spies

• In the 1990s, there were some Russian spies in the US
• The TV series “The Americans” was based on this incident
• A Cuban number station had a bug: some nights it never broadcasted “9”
• It turns out this corresponded to when the Russian spies were on vacation
• The FBI used this as part of their investigation
• Side channel: The insecure implementation leaked information

20

Computer Science 161

Popa and Weaver

Summary

• IND-CPA security
• Even if Eve can trick Alice into encrypting some messages of Eve’s choosing, given the encryption of either M0 or M1, Eve cannot distinguish which message was sent with probability greater than 1/2.
• We can use the IND-CPA game to test for IND-CPA security
• Edge cases: IND-CPA secure schemes can leak length. Eve is limited to polynomial-time algorithms, and must have a non-negligible advantage to win.
• One-time pads
• Symmetric encryption scheme: Alice and Bob share a secret key.
• Encryption and decryption: Bitwise XOR with the key.
• No information leakage if the key is never reused.
• Information leaks if the key is reused.
• Impractical for real-world usage, unless you’re a spy.

21

Computer Science 161

Popa and Weaver

Block Ciphers

22

Textbook Chapter 6.4 & 6.5

Computer Science 161

Popa and Weaver

Cryptography Roadmap

• Hash functions
• Pseudorandom number generators
• Public key exchange (e.g. Diffie-Hellman)

• Key management (certificates)
• Password management

Computer Science 161

Popa and Weaver

Block Ciphers: Definition

• Block cipher: An encryption/decryption algorithm that encrypts a fixed-sized block of bits
• EK(M) → C: Encryption
• Inputs: k-bit key K and an n-bit plaintext M
• Output: An n-bit ciphertext C
• Sometimes written as: {0, 1}^k × {0, 1}ⁿ → {0, 1}ⁿ
• DK(C) → M: Decryption
• Inputs: a k-bit key, and an n-bit ciphertext C
• Output: An n-bit plaintext
• Sometimes written as: {0, 1}^k × {0, 1}ⁿ → {0, 1}ⁿ
• The inverse of the encryption function
• Properties
• Correctness: EK is a permutation, DK is its inverse
• Efficiency: Encryption/decryption should be fast
• Security: E behaves like a random permutation

24

E

K

k bits

n bits

plaintext

n bits

ciphertext

D

K

k bits

n bits

ciphertext

n bits

plaintext

Computer Science 161

Popa and Weaver

Block Ciphers: Intuition

• Remember Enigma?
• Set the rotors and plugboard, and then type in plaintext. The machine lights up the ciphertext
• Inputs: the rotors and plugboard settings (the key), and the plaintext
• Output: the ciphertext
• Once the rotor and plugboard are set, you have a mapping of plaintexts to ciphertexts
• If you don’t know the rotor and plugboard settings, you can’t encrypt or decrypt
• Block ciphers are similar
• Once the key is set, you have a function mapping n-bit plaintexts to n-bit ciphertexts (E) and vice-versa (D)
• If you don’t know the key, you can’t encrypt or decrypt

25

Computer Science 161

Popa and Weaver

Block Ciphers: Correctness

• EK(M) must be a permutation (bijective function) on n-bit strings
• Each input must correspond to exactly one unique output
• Intuition
• Suppose EK(M) is not bijective
• Then two inputs might correspond to the same output: E(K, x1) = E(K, x2) = y
• Given ciphertext y, you can’t uniquely decrypt. D(K, y) = x1? D(K, y) = x2?

26

00

01

10

11

00

01

10

11

00

01

10

11

00

01

10

11

Not bijective: Two inputs encrypt to the same output

Bijective: Each input maps to exactly one unique output

Computer Science 161

Popa and Weaver

Block Ciphers: Security

• A secure block cipher behaves like a randomly chosen permutation permutation from the set of all permutations on n-bit strings
• A random permutation: Each n-bit input is mapped to one randomly-chosen n-bit output
• Defined by a distinguishing game
• Eve gets two boxes: One is a randomly chosen permutation, and one is EK with a randomly chosen key K
• Eve should not be able to tell which is which with probability > 1/2

27

00

01

10

11

00

01

10

11

00

01

10

11

00

01

10

11

One of these is EK and the other one is a random permutation. Eve can’t distinguish them.

Computer Science 161

Popa and Weaver

Block ciphers: Brute-force attacks?

• How hard is it to run a brute-force attack on a 128-bit key?
• We have to try 2¹²⁸ possibilities. How big is 2¹²⁸?
• Handy approximation: 2¹⁰ ≈ 10³
• 2¹²⁸ = 2^10*12.8 ≈ (10³)^12.8 ≈ (10³)¹³ = 10³⁹
• Suppose we have massive hardware that can try 10⁹ (1 billion) keys in 1 nanosecond (a billionth of a second). That’s 10¹⁸ keys per second
• We’ll need 10³⁹ / 10¹⁸ = 10²¹ seconds. How long is that?
• One year ≈ 3×10⁷ seconds
• 10²¹ seconds / 3×10⁷ ≈ 3×10¹³ years ≈ 30 trillion years
• Takeaway: Brute-forcing a 128-bit takes astronomically long

28

Computer Science 161

Popa and Weaver

Block ciphers: Brute-force attacks?

• How hard is it to run a brute-force attack on a 256-bit key?
• We need 10⁵² of the brute-force devices from before
• If each brute-force device from before is 1 cubic millimeter, this would take 10⁴³ cubic meters of space
• That’s the volume of 7×10¹⁵ suns!
• Takeaway: Brute-force attacks on modern block ciphers are not possible, assuming the key is random and secret

29

Computer Science 161

Popa and Weaver

Block Ciphers: Efficiency

• Encryption and decryption should be computable in microseconds
• Block cipher algorithms typically use operations like XOR and bit-shifting
• Very fast on modern processors
• Modern CPUs provide dedicated hardware support for block ciphers

30

Computer Science 161

Popa and Weaver

Example: DES (Data Encryption Standard)

• Designed in late 1970s
• Block size 64 bits (n = 64)
• Key size 56 bits (k = 56)
• NSA influenced two facets of its design
• Altered some subtle internal workings in a mysterious way
• Reduced key size from 64 bits to 56 bits
• Made brute force attacks feasible for an attacker with massive computational resources (by 1970s standards)
• The algorithm remains essentially unbroken 40 years later
• The NSA’s tweaking hardened it against an attack publicly revealed a decade later
• However, modern computer speeds make it completely unsafe due to small key size

31

Computer Science 161

Popa and Weaver

Example: AES (Advanced Encryption Standard)

• 1997–2000: NIST (National Institute of Standards and Technology) in the US held a competition to pick a new block cipher standard
• One of the finalists, Twofish, was designed by Berkeley professor and occasional 161 instructor David Wagner!
• Out of the 5 finalists:
• Rijndael, Twofish, and Serpent had really good performance
• RC6 had okay performance
• Mars had ugly performance
• On any given computing platform, Rijndael was never the fastest
• But on every computing platform, Rijndael was always the second-fastest
• Twofish and Serpent each had at least one compute platform they were bad at
• Rijndael was selected as the new block cipher standard

32

Computer Science 161

Popa and Weaver

Example: AES (Advanced Encryption Standard)

• Key size 128 bits (k = 128)
• These days better use 256-bit keys
• Sometimes written as AES-128, AES-256
• Block size 128 bits (n = 128)
• Note: The block size is still always 128 bits, regardless of key size
• You do not need to understand or know the AES algorithm
• here’s a comic

​

33

Computer Science 161

Popa and Weaver

AES Algorithm

• 14 cycles of repetition for 256-bit keys

34

Computer Science 161

Popa and Weaver

AES Algorithm: Sub Bytes

• Each byte in the state matrix is replaced with a SubByte using an 8-bit substitution box
• bij = S(aij)

35

Computer Science 161

Popa and Weaver

AES Algorithm: Shift Rows

• Cyclically shifts the bytes in each row by a certain offset
• The number of places each byte is shifted differs for each row

36

Computer Science 161

Popa and Weaver

Example: AES (Advanced Encryption Standard)

• There is no formal proof that AES is secure (indistinguishable from a random permutation)
• However, in 20 years, nobody has been able to break it, so it is assumed to be secure
• The NSA uses AES-256 for secrets they want to keep secure for the 40 years (even in the face of unknown breakthroughs in research)
• Takeaway: AES is the modern standard block cipher algorithm
• The standard key size (128 bits) is large enough to prevent brute-force attacks

37

Computer Science 161

Popa and Weaver

Are Block Ciphers IND-CPA Secure?

• Consider the following adversary:
• Eve sends two different messages M0 and M1
• Eve receives either EK(M0) or EK(M1)
• Eve requests the encryption of M0 again
• Strategy: If the encryption of M0 matches what she received, guess b = 0. Else, guess b = 1.
• Eve can win the IND-CPA game with probability 1!
• Block ciphers are not IND-CPA secure

38

M

Enc(K, M)

(repeat)

Alice (challenger)

Eve (adversary)

M0 and M1

Enc(K, Mb)

M

Enc(K, M)

Guess b = 0 or b = 1

(repeat)

pick b

Computer Science 161

Popa and Weaver

Issues with Block Ciphers

• Block ciphers are not IND-CPA secure, because they’re deterministic
• A scheme is deterministic if the same input always produces the same output
• No deterministic scheme can be IND-CPA secure because the adversary can always tell if the same message was encrypted twice
• Block ciphers can only encrypt messages of a fixed size
• For example, AES can only encrypt-decrypt 128-bit messages
• What if we want to encrypt something longer than 128 bits?

39

Computer Science 161

Popa and Weaver

Block Ciphers: Summary

• Encryption: input a k-bit key and n-bit plaintext, receive n-bit ciphertext
• Decryption: input a k-bit key and n-bit ciphertext, receive n-bit plaintext
• Correctness: when the key is fixed, EK(M) should be bijective
• Security
• Without the key, Ek(m) is computationally indistinguishable from a random permutation
• Brute-force attacks take astronomically long and are not possible
• Efficiency: algorithms use XORs and bit-shifting (very fast)
• Implementation: AES is the modern standard
• Issues
• Not IND-CPA secure because they’re deterministic
• Can only encrypt n-bit messages

40

Computer Science 161

Popa and Weaver

Block Cipher Modes of Operation

41

Textbook Chapter 6.6–6.9

Computer Science 161

Popa and Weaver

Scratchpad: Let’s design it together

42

Here’s an AES block. Remember that it can only encrypt 128-bit messages.

How can we use AES to encrypt a longer message (say, 256 bits?)

Computer Science 161

Popa and Weaver

Scratchpad: Let’s design it together

43

Idea: Let’s use AES twice!

Computer Science 161

Popa and Weaver

Scratchpad: Let’s design it together

44

Note that we are using the same key twice. We want to avoid a situation like one-time pads where we need very long keys.

Computer Science 161

Popa and Weaver

ECB Mode

• We’ve just designed electronic code book (ECB) Mode
• Enc(K, M) = C1 || C2 || … || Cm
• Assume m is the number of blocks of plaintext in M, each of size n
• AES-ECB is not IND-CPA secure. Why?
• Because ECB is deterministic

45

Computer Science 161

Popa and Weaver

ECB Mode: Penguin

Original image

46

Computer Science 161

Popa and Weaver

ECB Mode: Penguin

Encrypted with ECB

47

Computer Science 161

Popa and Weaver

Scratchpad: Let’s design it together

48

Here’s ECB mode. It’s not IND-CPA secure because it’s deterministic.

Let’s fix that by adding some randomness.

Computer Science 161

Popa and Weaver

Scratchpad: Let’s design it together

49

The Initialization Vector (IV) is different for every encryption. Now the first ciphertext block will be different for every encryption!

Okay, but the other blocks are still deterministic...

Computer Science 161

Popa and Weaver

Scratchpad: Let’s design it together

50

Idea: The first ciphertext block was computed with some randomness. Let’s use it to add randomness to the second block.

Computer Science 161

Popa and Weaver

Scratchpad: Let’s design it together

51

Now the second ciphertext block has some randomness in it. Let’s use it to add randomness to the third block.

Computer Science 161

Popa and Weaver

CBC Mode

• We’ve just designed cipher block chaining (CBC) mode
• Ci = EK(Mi ⊕ Ci-1); C0 = IV
• Enc(K, M):
• Split M in m plaintext blocks P₁ … P_m each of size n
• Choose a random IV
• Compute and output (IV, C₁, …, C_m) as the overall ciphertext
• How do we decrypt?

52

P₁

P₂

P_m

Computer Science 161

Popa and Weaver

CBC Mode: Decryption

• How do we decrypt CBC mode?
• Parse ciphertext as (IV, C₁, …, C_m)
• Decrypt each ciphertext and then XOR with IV or previous ciphertext

53

Computer Science 161

Popa and Weaver

CBC Mode: Decryption

54

Computer Science 161

Popa and Weaver

CBC Mode: Efficiency & Parallelism

• Can encryption be parallelized?
• No - we have to wait for block i to finish before encrypting block i+1
• Can decryption be parallelized?
• Yes - decryption only requires ciphertext as input

55

Computer Science 161

Popa and Weaver

CBC Mode: Padding

• What if you want to encrypt a message that isn’t a multiple of the block size?
• AES-CBC is only defined if the plaintext length is a multiple of the block size
• Solution: Pad the message until it’s a multiple of the block size
• Padding: Adding dummy bytes at the end of the message until it’s the proper length

56

Computer Science 161

Popa and Weaver

CBC Mode: Padding

• What padding scheme should we use?
• Padding with 0’s?
• Doesn’t work: What if our message already ends with 0’s?
• Padding with 1’s?
• Same problem
• We need a scheme that can be unpadded without ambiguity
• One scheme that works: Append a 1, then pad with 0’s
• If plaintext is multiple of n, you still need to pad with an entire block
• Another scheme: Pad with the number of padding bytes
• So if you need 1 byte, pad with 01; if you need 3 bytes, pad with 03 03 03
• If you need 0 padding bytes, pad an entire dummy block
• This is called PKCS #7

57

Computer Science 161

Popa and Weaver

CBC Mode: Security

• AES-CBC is IND-CPA secure. With what assumption?
• The IV must be randomly generated and never reused
• What happens if you reuse the IV?
• The scheme becomes deterministic: No more IND-CPA security

58

Computer Science 161

Popa and Weaver

CBC Mode: IV Reuse

• Consider two three-block messages: P1P2P3 and P1P2P4
• The first two blocks are the same for both messages, but the last block is different
• What if we encrypt them with the same IV?
• When the IV is reused, CBC mode reveals when two messages start with the same plaintext blocks, up to the first different plaintext block

59

Computer Science 161

Popa and Weaver

CBC Mode is IND-CPA (when used correctly)

• Enc(K, M):
• Split M in m plaintext blocks P₁ … P_m each of size n
• Choose random IV, compute and output (IV, C₁, …, C_m) as the overall ciphertext
• Why IND-CPA?
• If there exists an attacker that wins in the IND-CPA game, then there exists an attacker that breaks the block cipher security. Proof is out of scope.

60

P₁

P₂

P_m

Computer Science 161

Popa and Weaver

CBC Mode: Penguin

Original image

61

Computer Science 161

Popa and Weaver

CBC Mode: Penguin

Encrypted with CBC, with random IVs

62

Computer Science 161

Popa and Weaver