One-Time Pad & Block Ciphers

CS 161 Spring 2024 - Lecture 6

Computer Science 161

Project 1 Parties

Project 1 is due this Friday, February 9, 11:59pm.

• Project 1 Party this Wednesday, February 7th 5-6:30pm in Cory 540AB.
• Project 1 Party this Thursday, February 8th 5-7pm in Cory 540AB.

​

My office hours: Monday 2-3pm, Soda 729

​

2

Computer Science 161

Recall the IND-CPA security definition

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
• 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.

3

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

Keygen()

Computer Science 161

One-Time Pads

4

Textbook Chapter 6.2 & 6.3

Computer Science 161

Cryptography Roadmap

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

5

• Key management (certificates)
• Password management

Computer Science 161

Review: XOR

6

The XOR operator takes two bits and outputs one bit:

Useful properties of XOR:

Computer Science 161

Review: XOR Algebra

• Algebra works on XOR too

​

7

Computer Science 161

One-Time Pads: Key Generation

8

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

One-Time Pads: Encryption

9

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

One-Time Pads: Encryption

10

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

One-Time Pads: Decryption

11

Bob

K

C

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

Computer Science 161

One-Time Pads: Decryption

12

Bob

K

C

M

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

Computer Science 161

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

13

Computer Science 161

One-Time Pad: Correctness

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

14

Computer Science 161

One-Time Pad: Security

• Recall our definition of confidentiality: The ciphertext should not give the attacker any additional information about the plaintext
• Recall our preliminary experiment (before IND-CPA) to test confidentiality from earlier:
• If the probability that Eve correctly guesses

which message was sent is 1/2, then the

encryption scheme is confidential

15

Alice (challenger)

Eve (adversary)

M0 and M1

Enc(K, Mb)

Guess b = 0 or b = 1

pick b

15

KeyGen():K

Computer Science 161

One-Time Pad: Security

16

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

By “perfectly” we mean that any attacker has chance of winning the security game exactly ½ (not ½+epsilon)

Computer Science 161

Two-Time Pads?

17

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

Two-Time Pads?

18

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

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 other 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!

19

Computer Science 161

OTP does not offer IND-CPA

• What is an attack strategy?
• Many possible, e.g.
• In the trial phase and the challenge phase, ask for “00” and “11”, it is deterministic.

20

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

Keygen()

Computer Science 161

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!
• 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
• And people can compute this by hand without computers!

21

Computer Science 161

Is one-time pad IND-CPA secure?

​

• Eve may choose plaintexts to send to Alice and receives their ciphertexts
• Eve issues a pair of plaintexts M0 and M1 to Alice
• Alice randomly chooses either M0 or M1 to encrypt and sends the encryption back
1. Alice does not tell Eve which one was encrypted!
• Eve may again choose plaintexts to send to Alice and receives their ciphertexts
• 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.

​

22

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

A: 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

One-Time Pads in Practice: Spies

• At home base, the spy obtains a large amount of key material (e.g. a book of random bits)
• In the field, the spy listens for secret messages from their home country
• There are shortwave and terrestrial radio “number stations”
• At a regular time, a voice gets on the air and reads a series of numbers
• If you don’t know the key, this looks like a meaningless sequence of random numbers
• If you know the key, you can decrypt the spy message!
• What if you don’t want to send anything to any spies?
• Read out a list of random numbers anyway
• Because one-time pad leaks no information, an eavesdropper can’t distinguish between an encrypted message and random numbers!

23

Computer Science 161

Two-Time Pads in Practice: VENONA

• Soviet spies used one-time pads for communication from their spies in the US
• During WWII, the Soviets started reusing key material
• Uncertain whether it was just the cost of generating pads or what…
• VENONA was a US cryptanalysis project designed to break these messages
• Included confirming/identifying the spies targeting the US Manhattan project
• Project continued until 1980!
• Not declassified until 1995!
• So secret even President Truman wasn’t informed about it
• The Soviets found out about it in 1949 through their spy Ken Philby, but their one-time pad reuse was fixed after 1948 anyway
• Takeaway: Otherwise-secure cryptographic systems can fail very badly if used improperly!

24

Computer Science 161

Summary for 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.

25

Computer Science 161

Block Ciphers

26

Textbook Chapter 6.4 & 6.5

Computer Science 161

Cryptography Roadmap

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

• Key management (certificates)
• Password management

Computer Science 161

Block Ciphers: Definition

• Block cipher: A cryptographic scheme consisting of encode/decode algorithms for a fixed-sized block of bits:
• EK(M) → C: Encode
• 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: Decode
• 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: Encode/decode should be fast
• Security: E behaves like a random permutation

28

E

K

k bits

n bits

plaintext

n bits

ciphertext

D

K

k bits

n bits

ciphertext

n bits

plaintext

Computer Science 161

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 decode. D(K, y) = x1? D(K, y) = x2?

29

00

01

10

11

00

01

10

11

00

01

10

11

00

01

10

11

Not bijective: Two inputs encode to the same output

Bijective: Each input maps to exactly one unique output

Computer Science 161

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 > ½+negl

30

00

01

10

11

00

01

10

11

00

01

10

11

00

01

10

11

One of these is EK with a randomly chosen K, and the other one is a randomly chosen permutation. Eve can’t distinguish them.

??

Computer Science 161

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 key takes astronomically long.�Don’t even try.

31

Computer Science 161

Block ciphers: Brute-force attacks?

• How hard is it to run a brute-force attack on a 256-bit key in the same time?
• 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!
• For reference, the Milky Way galaxy has just 10¹¹ stars
• Takeaway: Brute-force attacks on modern block ciphers are not possible, assuming the key is random and secret
• 128-bit key? Definitely not happening.
• 256-bit key? Lol no.

32

Computer Science 161

Block Ciphers: Efficiency

• Encryption and decryption should be computable in microseconds
• Formally: KeyGen(), Enc(), and Dec(), should not take exponential time
• Block cipher algorithms typically use operations like XOR, bit-shifting, and small table lookups
• Very fast on modern processors
• Modern CPUs provide dedicated hardware support for block ciphers

33

Computer Science 161

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
• ~6.4 × 10¹⁶, say 10¹⁰ tries per second on my single desktop computer's Nvidia graphics card: Takes ~6.4 × 10⁶ seconds or ~70 days

34

Computer Science 161

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 CS 161 instructor David Wagner!
• Out of the 5 finalists:
• Rijndael, Twofish, and Serpent had really good performance
• RC6 had okay performance
• Mars had bad 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

35

Computer Science 161

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 because they are deterministic

36

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

AES (Advanced Encryption Standard)

• Key size 128, 192, or 256 bits (k = 128, 192, or 256)
• Use key size 256 these days
• Block size 128 bits (n = 128)
• Note: The block size is still always 128 bits, regardless of key size
• You don’t need to know how AES works, but you do need to know its parameters
• here’s a comic

37

Computer Science 161

AES Algorithm

• Different key sizes use different numbers of rounds
• 10 rounds for 128-bit keys
• 12 rounds for 192-bit keys
• 14 rounds for 256-bit keys
• Each round uses its own “round key” derived from the cipher key
• Each round:
• SubBytes()
• ShiftRows()
• MixColumns() (if not last round)
• AddRoundKey()

38

Computer Science 161

AES Algorithm: SubBytes()

• Replace each byte in the block with another byte using an 8-bit substitution box

39

Computer Science 161

AES Algorithm: ShiftRows()

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

40

Computer Science 161

AES Algorithm: MixColumns()

• Treats the 16-byte block as a 4 × 4 matrix and multiply it by by another matrix

41

Computer Science 161

AES Algorithm: AddRoundKey()

• XOR the 16-byte block with the 16-byte round key

42

Computer Science 161

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

43

Computer Science 161

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?
• To address these problems, we’ll add modes of operation that use block ciphers as a building block!

44

Computer Science 161

Summary: Block Ciphers

• 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

45

Computer Science 161

Block Cipher Modes of Operation

46

Textbook Chapter 6.6–6.9

Computer Science 161

Scratchpad: Let’s design it together

47

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

Scratchpad: Let’s design it together

48

Idea: Let’s use AES twice!

Computer Science 161

Scratchpad: Let’s design it together

49

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

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

50

Computer Science 161

ECB Mode: Penguin

Original image

51

Computer Science 161

ECB Mode: Penguin

Encrypted with ECB

52

Computer Science 161

Scratchpad: Let’s design it together

53

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

Scratchpad: Let’s design it together

54

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

Scratchpad: Let’s design it together

55

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

Computer Science 161

Scratchpad: Let’s design it together

56

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

Computer Science 161

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?

57

P₁

P₂

P_m

Computer Science 161

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

58

Computer Science 161

CBC Mode: Decryption

59

Computer Science 161

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

60

Computer Science 161

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

61

Computer Science 161

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

62

Computer Science 161

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

63

Computer Science 161

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

64

Computer Science 161

CBC Mode is IND-CPA (when used correctly)

• Enc(K, M):
• Split M in m plaintext blocks P1 … Pm each of size n
• Choose random IV, compute and output (IV, C1, …, Cm) 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.

65

P₁

P₂

P_m

Computer Science 161

CBC Mode: Penguin

Original image

66

Computer Science 161

CBC Mode: Penguin

Encrypted with CBC, with random IVs

67

Computer Science 161