1 of 46

PRNGs, Stream Ciphers and Diffie-Hellman Key Exchange

CS 161 Fall 2021 - Lecture 13

#

Computer Science 161

Popa and Weaver

Popa and Weaver

2 of 46

Announcements

  • Start recording
  • Homework 3 is due Friday, October 1st, 11:59 PM PT
  • Project 1 is due Friday, September 24th, 11:59 PM PT

​

2

Computer Science 161

Popa and Weaver

Popa and Weaver

3 of 46

Last Time: Hashes

  • Map arbitrary-length input to fixed-length output
  • Output is deterministic and unpredictable
  • Security properties
    • One way: Given an output y, it is infeasible to find any input x such that H(x) = y.
    • Collision resistant: It is infeasible to find another any pair of inputs x' ≠ x such that H(x) = H(x').
  • Some hashes are vulnerable to length extension attacks
  • Application: Lowest hash scheme
  • Hashes don’t provide integrity (unless you can publish the hash securely)

3

Computer Science 161

Popa and Weaver

Popa and Weaver

4 of 46

Last Time: MACs

  • Inputs: a secret key and a message
  • Output: a tag on the message
  • A secure MAC is unforgeable: Even if Mallory can trick Alice into creating MACs for messages that Mallory chooses, Mallory cannot create a valid MAC on a message that she hasn't seen before
    • Example: HMAC(K, M) = H((K ⊕ opad) || H((K ⊕ ipad) || M))
  • MACs do not provide confidentiality

4

Computer Science 161

Popa and Weaver

Popa and Weaver

5 of 46

Authenticated Encryption (cont’d)

5

Textbook Chapter 8.7 & 8.8

Computer Science 161

Popa and Weaver

Popa and Weaver

6 of 46

Cryptography Roadmap

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

6

​

Symmetric-key

Asymmetric-key

Confidentiality

  • One-time pads
  • Block ciphers with chaining modes (e.g. AES-CBC)
  • RSA encryption
  • ElGamal encryption

Integrity,�Authentication

  • MACs (e.g. HMAC)
  • Digital signatures (e.g. RSA signatures)
  • Key management (certificates)
  • Password management

Computer Science 161

Popa and Weaver

Popa and Weaver

7 of 46

Authenticated Encryption: Definition

  • Authenticated encryption (AE): A scheme that simultaneously guarantees confidentiality and integrity (and authenticity, depending on your threat model) on a message
  • Two ways of achieving authenticated encryption:
    • Combine schemes that provide confidentiality with schemes that provide integrity
    • Use a scheme that is designed to provide confidentiality and integrity

7

Computer Science 161

Popa and Weaver

Popa and Weaver

8 of 46

Key Reuse

  • First method for authenticated encryption: Combining schemes that provide confidentiality with schemes that provide integrity
  • Key reuse: Using the same key in two different algorithms (e.g. AES-CBC and HMAC)
    • Note: Using the same key for multiple uses of one algorithm (e.g. computing HMACs on different messages with the same key) is not key reuse
  • Reusing keys can cause the underlying algorithms to interfere with each other and affect security guarantees
    • Example: If you use a block-cipher-based MAC algorithm and a block cipher chaining mode, the underlying block ciphers may no longer be secure
    • Thinking about these attacks is hard
  • Simplest solution: Do not reuse keys! One key per algorithm.

8

Computer Science 161

Popa and Weaver

Popa and Weaver

9 of 46

Scratchpad: Let’s design it together

  • You can use:
    • An IND-CPA encryption scheme (e.g. AES-CBC): Enc(K, M) and Dec(K, M)
    • An unforgeable MAC scheme (e.g. HMAC): MAC(K, M)
  • First attempt: Alice sends Enc(K1, M) and MAC(K2, M)
    • Integrity? Yes, attacker can’t tamper with the MAC
    • Confidentiality? No, the MAC is not IND-CPA secure
  • Idea: Let’s compute the MAC on the ciphertext instead of the plaintext:�Enc(K1, M) and MAC(k2, Enc(K1, M))
    • Integrity? Yes, attacker can’t tamper with the MAC
    • Confidentiality? Yes, the MAC might leak info about the ciphertext, but that’s okay
  • Idea: Let’s encrypt the MAC too: Enc(K1, M || MAC(K2, M))
    • Integrity? Yes, attacker can’t tamper with the MAC
    • Confidentiality? Yes, everything is encrypted

9

Computer Science 161

Popa and Weaver

Popa and Weaver

10 of 46

MAC-then-Encrypt or Encrypt-then-MAC?

  • MAC-then-encrypt
    • First compute MAC(K2, M)
    • Then encrypt the message and the MAC together: Enc(k1, M || MAC(K2, M))
  • Encrypt-then-MAC
    • First compute Enc(K1, M)
    • Then MAC the ciphertext: MAC(K2, Enc(K1, M))
  • Which is better?
    • In theory, both are IND-CPA and EU-CPA secure if applied properly
    • MAC-then-encrypt has a downside: You don’t know if tampering has occurred until after decrypting
      • Attacker can supply arbitrary tampered input, and you always have to decrypt it
      • Passing attacker-chosen input through the decryption function can cause side-channel leaks
  • Always use encrypt-then-MAC because it’s more robust to mistakes

10

Computer Science 161

Popa and Weaver

Popa and Weaver

11 of 46

TLS 1.0 “Lucky 13” Attack

  • TLS: A protocol for sending encrypted and authenticated messages over the Internet (we’ll study it more in the networking unit)
  • TLS 1.0 uses MAC-then-encrypt: Enc(k1, M || MAC(k2, M))
    • The encryption algorithm is AES-CBC
  • The Lucky 13 attack abuses MAC-then-encrypt to read encrypted messages
    • Guess a byte of plaintext and change the ciphertext accordingly
    • The MAC will error, but the time it takes to error is different depending on if the guess is correct
    • Attacker measures how long it takes to error in order to learn information about plaintext
    • TLS will send the message again if the MAC errors, so the attacker can guess repeatedly
  • Takeaways
    • Side channel attack: The algorithm is proved secure, but poor implementation made it vulnerable
    • Always encrypt-then-MAC
    • You’ll try a similar attack in Homework 2!

11

Computer Science 161

Popa and Weaver

Popa and Weaver

12 of 46

AEAD Encryption

  • Second method for authenticated encryption: Use a scheme that is designed to provide confidentiality, integrity, and authenticity
  • Authenticated encryption with additional data (AEAD): An algorithm that provides both confidentiality and integrity over the plaintext and integrity over additional data
    • Additional data is usually context (e.g. memory address), so you can’t change the context without breaking the MAC
  • Great if used correctly: No more worrying about MAC-then-encrypt
    • If you use AEAD incorrectly, you lose both confidentiality and integrity/authentication
    • Example of correct usage: Using a crypto library with AEAD

12

Computer Science 161

Popa and Weaver

Popa and Weaver

13 of 46

AEAD Example: Galois Counter Mode (GCM)

  • Galois Counter Mode (GCM): An AEAD block cipher mode of operation
  • EK is standard block cipher encryption
  • multH is 128-bit multiplication over a special field (Galois multiplication)
    • Don’t worry about the math

13

Computer Science 161

Popa and Weaver

Popa and Weaver

14 of 46

AEAD Example: Galois Counter Mode (GCM)

  • Very fast mode of operation
    • Fully parallel encryption
    • Galois multiplication isn’t parallelizable, but it’s very fast
  • Drawbacks
    • IV reuse leads to loss of confidentiality, integrity, and authentication
    • This wouldn’t happen if you used AES-CTR and HMAC-SHA256
    • Implementing Galois implementation is difficult and easy to screw up

14

Computer Science 161

Popa and Weaver

Popa and Weaver

15 of 46

Summary: Authenticated Encryption

  • Authenticated encryption: A scheme that simultaneously guarantees confidentiality and integrity (and authenticity) on a message
  • First approach: Combine schemes that provide confidentiality with schemes that provide integrity and authenticity
    • Encrypt-then-MAC: Enc(K1, M) || MAC(K2, Enc(K1, M))
    • Always use Encrypt-then-MAC because it's more robust to mistakes
  • Second approach: Use AEAD encryption modes designed to provide confidentiality, integrity, and authenticity
    • Drawback: Incorrectly using AEAD modes leads to losing both confidentiality and integrity/authentication

15

Computer Science 161

Popa and Weaver

Popa and Weaver

16 of 46

Pseudorandom Number Generators (PRNGS)

16

Textbook Chapter 9

Symmetric-key encryption schemes need randomness. How do we securely generate random numbers?

Computer Science 161

Popa and Weaver

Popa and Weaver

17 of 46

Cryptography Roadmap

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

17

​

Symmetric-key

Asymmetric-key

Confidentiality

  • One-time pads
  • Block ciphers with chaining modes (e.g. AES-CBC)
  • RSA encryption
  • ElGamal encryption

Integrity,�Authentication

  • MACs (e.g. HMAC)
  • Digital signatures (e.g. RSA signatures)
  • Key management (certificates)
  • Password management

Computer Science 161

Popa and Weaver

Popa and Weaver

18 of 46

Randomness

  • Randomness is essential for symmetric-key encryption
    • A random key
    • A random IV/nonce
    • Universally unique identifiers (we’ll see this shortly)
    • We’ll see more applications later
  • If an attacker can predict a random number, things can catastrophically fail
  • How do we securely generate random numbers?

​

18

Computer Science 161

Popa and Weaver

Popa and Weaver

19 of 46

Entropy

  • In cryptography, “random” usually means “random and unpredictable”
  • Scenario
    • You want to generate a secret bitstring that the attacker can't guess
    • You generate random bits by tossing a fair (50-50) coin
    • The outcomes of the fair coin are harder for the attacker to guess
  • Entropy: A measure of uncertainty
    • In other words, a measure of how unpredictable the outcomes are
    • High entropy = unpredictable outcomes = desirable in cryptography
    • The uniform distribution has the highest entropy (every outcome equally likely, e.g. fair coin toss)
    • Usually measured in bits (so 3 bits of entropy = uniform, random distribution over 8 values)

19

Computer Science 161

Popa and Weaver

Popa and Weaver

20 of 46

Breaking Bitcoin Wallets

  • What happens if we use a poor source of entropy?
  • Bitcoin users use a randomly-generated private key to access their account (and money)
    • An attacker who learns the key can access the money
    • We’ll learn more about Bitcoin later
  • An “improvment” [sic] to the algorithm reduced the entropy used to generate the private keys
    • Any private key created with this “improvment” could be brute-forced

20

Computer Science 161

Popa and Weaver

Popa and Weaver

21 of 46

True Randomness

  • To generate truly random numbers, we need a physical source of entropy
    • An unpredictable circuit on a CPU
    • Human activity measured at very fine time scales (e.g. the microsecond you pressed a key)
  • Unbiased entropy usually requires combining multiple entropy sources
    • Goal: Total number of bits of entropy is the sum of all the input numbers of bits of entropy
      • Many poor sources + 1 good source = good entropy
  • Issues with true randomness
    • It’s expensive and slow to generate
    • Physical entropy sources are often biased

21

Exotic entropy source: Cloudflare has a wall of lava lamps that are recorded by an HD video camera that views the lamps through a rotating prism

Computer Science 161

Popa and Weaver

Popa and Weaver

22 of 46

Pseudorandom Number Generators (PRNGs)

  • True randomness is expensive and biased
  • Pseudorandom number generator (PRNGs): An algorithm that uses a little bit of true randomness to generate a lot of random-looking output
    • Also called deterministic random bit generators (DRBGs)
  • Usage
    • Generate some expensive true randomness (e.g. noisy circuit on your CPU)
    • Use the true randomness as input to the PRNG
    • Generate random-looking numbers quickly and cheaply with the PRNG
  • PRNGs are deterministic: Output is generated according to a set algorithm
    • However, for an attacker who can’t see the internal state, the output is computationally indistinguishable from true randomness

22

Computer Science 161

Popa and Weaver

Popa and Weaver

23 of 46

PRNG: Definition

  • A PRNG has two functions:
    • PRNG.Seed(randomness): Initializes the internal state using the entropy
      • Input: Some truly random bits
    • PRNG.Generate(n): Generate n pseudorandom bits
      • Input: A number n
      • Output: n pseudorandom bits
      • Updates the internal state as needed

Properties

    • Correctness: Deterministic
    • Efficiency: Efficient to generate pseudorandom bits
    • Security: Indistinguishability from random

23

Computer Science 161

Popa and Weaver

Popa and Weaver

24 of 46

PRNG: Security

  • Can we design a PRNG that is truly random?

​

24

  • A PRNG cannot be truly random
    • The output is deterministic given the initial seed
    • If the initial seed is s bits long, there are only 2s possible output sequences
  • A secure PRNG is computationally indistinguishable from random to an attacker
    • Game: Present an attacker with a truly random sequence and a sequence outputted from a secure PRNG
    • An attacker should not be able to determine which is which with probability > ½+negl
  • Equivalence: An attacker cannot predict future output of the PRNG

Computer Science 161

Popa and Weaver

Popa and Weaver

25 of 46

Insecure PRNGs: Breaking Slot Machines

  • What happens if PRNGs are used improperly?
  • A casino in St. Louis experienced unusual bad “luck”
    • Suspicious players would hover over the lever and then spin at a specific time to win
  • Vulnerability: Slot machines used predictable PRNGs
    • The PRNG output was based on the current time
  • Strategy:
    • Use a smartphone to alert you to when to pull the lever for the best chance of winning
  • Las Vegas was not affected by the vulnerability
    • Nevada slot machines must follow evaluation standards designed to address this sort of issue

25

Computer Science 161

Popa and Weaver

Popa and Weaver

26 of 46

Insecure PRNGs: OpenSSL PRNG bug

  • What happens if we don’t use enough entropy?
  • Debian OpenSSL CVE-2008-0166
    • Debian: A Linux distribution
    • OpenSSL: A cryptographic library
    • In “cleaning up” OpenSSL (Debian “bug” #363516), the author “fixed” how OpenSSL seeds random numbers
    • The existing code caused Purify and Valgrind to complain about reading uninitialized memory
    • The cleanup caused the PRNG to only be seeded with the process ID
    • There are only 215 (32,768) possible process IDs, so the PRNG only has 15 bits of entropy
  • Easy to deduce private keys generated with the PRNG
    • Set the PRNG to every possible starting state and generate a few private/public key pairs
    • See if the matching public key is anywhere on the Internet

26

Computer Science 161

Popa and Weaver

Popa and Weaver

27 of 46

Example construction of PRNG

  • Using block cipher in CTR mode:
  • If you want m random bits, and a block cipher with Ek has n bits, apply the block cipher m/n times and concatenate the result:
  • PRNG.Seed(K | IV) = Ek(IV|1) | Ek(IV| 2) | Ek(IV|3) … Ek(IV| ceil(m/n)),
    • | is concatenation

​

27

Randomness,

PRNG output

Computer Science 161

Popa and Weaver

Popa and Weaver

28 of 46

Insecure PRNGs: Rust Rand_Core

  • A Rust library has an interface for “secure” random number generators… but it isn’t actually secure!
  • Example: ChaCha8Rng
    • A stream cipher PRNG
    • No reseed function: no way of adding extra entropy after the initial seed
    • Seed only takes 32 bits: no way to combine entropy
    • No rollback resistance
  • None of the “secure” RNGs are cryptographically secure
    • None have a reseed function to add extra entropy
    • None take arbitrarily long seeds
  • Takeaway: Always make sure you use a secure PRNG
    • Consider human factors? Use fail-safe defaults?

28

Computer Science 161

Popa and Weaver

Popa and Weaver

29 of 46

Insecure PRNGs: CVE-2019-16303

  • Relevant if you wrote an app in JHipster before 2019
  • Password reset functions
    • When you forget your password, receive an email with a special link to reset your password
    • The special link should contain a randomly-generated code (so attackers can't make their own link)
  • Vulnerability: Bad PRNG
    • You can figure out the PRNG’s internal state from the reset link
    • Request password reset links for other people's accounts
    • Predict the “random” reset link and take over any account you want!

29

Computer Science 161

Popa and Weaver

Popa and Weaver

30 of 46

Application: Universally Unique Identifiers (UUIDs)

  • Scenario
    • You have a set of objects (e.g. files)
    • You need to assign a unique name to every object
    • Every name must be unique and unpredictable
  • Solution: choose a random value
    • If you use enough randomness, the probability of generating the same random value twice are astronomically small (basically 0)
  • Universally Unique Identifiers (UUIDs)
    • 128-bit unique values
    • To generate a new UUID, seed a secure PRNG properly, and generate a random value
    • Often written in hexadecimal: 00112233-4455-6677-8899-aabbccddeeff
    • You’ll work with UUIDs in Project 2

30

Computer Science 161

Popa and Weaver

Popa and Weaver

31 of 46

PRNGs: Summary

  • True randomness requires sampling a physical process
    • Slow, expensive, and biased (low entropy)
  • PRNG: An algorithm that uses a little bit of true randomness to generate a lot of random-looking output
    • Seed(entropy): Initialize internal state
    • Generate(n): Generate n bits of pseudorandom output
  • Security: computationally indistinguishable from truly random bits
  • Example using AES in CTR mode
  • Application: UUIDs

31

Computer Science 161

Popa and Weaver

Popa and Weaver

32 of 46

Stream Ciphers

32

Textbook Chapter 9.5

Computer Science 161

Popa and Weaver

Popa and Weaver

33 of 46

Stream Ciphers

  • Another way to construct symmetric key encryption schemes
  • Idea
    • A secure PRNG produces output that looks indistinguishable from random
    • An attacker who can’t see the internal PRNG state can’t learn any output
    • What if we used PRNG output as the key to a one-time pad?
  • Stream cipher: A symmetric encryption algorithm that uses pseudorandom bits as the key to a one-time pad

33

Computer Science 161

Popa and Weaver

Popa and Weaver

34 of 46

Stream Ciphers

  • Protocol: Alice and Bob both seed a secure PRNG with their symmetric secret key, and then use the output as the key for a one-time pad

34

⊕

Generate(n)

Seed(k)

Seed(k)

Generate(n)

⊕

Plaintext

Ciphertext

Plaintext

Alice

Bob

Computer Science 161

Popa and Weaver

Popa and Weaver

35 of 46

Stream Ciphers: Encrypting Multiple Messages

  • Recall: One-time pads are insecure when the key is reused. How do we encrypt multiple messages without key reuse?

35

⊕

Generate(n)

Seed(k)

Alice

Bob

Seed(k)

Generate(n)

⊕

Plaintext

Ciphertext

Plaintext

Computer Science 161

Popa and Weaver

Popa and Weaver

36 of 46

Stream Ciphers: Encrypting Multiple Messages

  • Solution: For each message, seed the PRNG with the key and a random IV, concatenated(“|”). Send the IV with the ciphertext

36

⊕

Generate(n)

Seed(k | IV)

Alice

Bob

Seed(k | IV)

Generate(n)

⊕

Plaintext

Ciphertext

Plaintext

IV

IV

Computer Science 161

Popa and Weaver

Popa and Weaver

37 of 46

Application of PRNG: Stream ciphers

  • Similar in spirit to one-time pad: it XORs the plaintext with some random bits
  • But random bits are not the key (as in one-time pad) but are output of a pseudorandom generator PRG

​

37

Computer Science 161

Popa and Weaver

Popa and Weaver

38 of 46

Stream ciphers

Enc(K, M):

  • Choose a random value IV
  • PRNG.Seed(K|IV)
  • C = PRNG.Generate(|M|) XOR M
  • Output (IV, C)

Q: How to decrypt?

A: Compute PRG sequence using K and IV and XOR with ciphertext C

Q: What is advantage over OTP?

A: Can encrypt any message length because PRG can produce any number of random bits, and multiple times because IV is chosen at random in Enc

​

38

Computer Science 161

Popa and Weaver

Popa and Weaver

39 of 46

Stream Ciphers: Security

  • Stream ciphers are IND-CPA secure, assuming the pseudorandom output is secure
  • In some stream ciphers, security is compromised if too much plaintext is encrypted
    • Example: In AES-CTR, if you encrypt so many blocks that the counter wraps around, you’ll start reusing keys
    • In practice, if the key is n bits long, usually stop after 2n/2 bits of output
    • Example: In AES-CTR with 128-bit counters, stop after 264 blocks of output

39

Computer Science 161

Popa and Weaver

Popa and Weaver

40 of 46

Stream Ciphers: Encryption Efficiency

  • Stream ciphers can continually process new elements as they arrive
    • Only need to maintain internal state of the PRNG
    • Keep generating more PRNG output as more input arrives
  • Compare to block ciphers: Need modes of operations to handle longer messages, and modes like AES-CBC need padding to function, so doesn’t function well on streams

40

Computer Science 161

Popa and Weaver

Popa and Weaver

41 of 46

Stream Ciphers: Decryption Efficiency

  • Suppose you received a 1 GB ciphertext (encryption of a 1 GB message) and you only wanted to decrypt the last 128 bytes
  • Benefit of some stream ciphers: You can decrypt one part of the ciphertext without decrypting the entire ciphertext
    • Example: In AES-CTR, to decrypt only block i, compute EK(nonce || i) and XOR with the ith block of ciphertext
    • Example: ChaCha20 (another stream cipher) lets you decrypt arbitrary parts of ciphertext
    • What about HMAC-DRBG? You have to generate all the PRNG output up until the block you want to decrypt

41

Computer Science 161

Popa and Weaver

Popa and Weaver

42 of 46

Diffie-Hellman Key Exchange

42

Textbook Chapter 10

Computer Science 161

Popa and Weaver

Popa and Weaver

43 of 46

Cryptography Roadmap

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

43

​

Symmetric-key

Asymmetric-key

Confidentiality

  • One-time pads
  • Block ciphers with chaining modes (e.g. AES-CBC)
  • RSA encryption
  • ElGamal encryption

Integrity,�Authentication

  • MACs (e.g. HMAC)
  • Digital signatures (e.g. RSA signatures)
  • Key management (certificates)
  • Password management

Computer Science 161

Popa and Weaver

Popa and Weaver

44 of 46

A quick “physical” game: keys are not shared/symmetrical!

44

Alice:

Bob:

Eve:

msg

Computer Science 161

Popa and Weaver

Popa and Weaver

45 of 46

Option 1: similar to Diffie Hellman key exchange

45

Alice:

Bob:

Eve:

msg

  1. Alice sends

2. Bob sends back

msg

3. Alice removes her lock and sends to Bob

msg

Like Diffie-Hellman key exchange

Computer Science 161

Popa and Weaver

Popa and Weaver

46 of 46

Option 2: similar to public-key encryption

46

Alice:

Bob:

Eve:

  1. Bob sends Alice the open lock

2. Alice locks down msg with Bob’s lock

msg

Computer Science 161

Popa and Weaver

Popa and Weaver