1 of 50

PRNGs and Diffie-Hellman Key Exchange

CS 161 Spring 2025 - Lecture 10

Computer Science 161

2 of 50

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
Hashes don’t provide integrity (unless you can publish the hash securely)

2

Computer Science 161

3 of 50

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

3

Computer Science 161

So we moved onto MACs! Now MACs were pretty cool because they’re effectively like a digital seal. If you break a seal on an envelope to modify the message inside, it will always look broken (even if you’ve glued the edges together). That’s kind of like a MAC: you can’t forge your way to creating a correct MAC tag–that’s one of it’s properties.

We talked about different types of MACs like NMACs (which utilize two keys) and HMACs, which utilize just one key and have two constant opads and ipads to XOR them.

However, something that’s important to note is that MACs do not provide confidentiality. This means that if I send the same message twice like “Evanbot is a bot”, and I don’t want someone to tamper it to say something like “Evanbot is not a bot” or “Codabot is my favorite bot”, then someone would still know that I sent the message “Evanbot is a bot” twice.

Our cryptographic goals are separate: we have methodologies in separate to figure out ways to provide confidentiality, integrity, and authenticity. But what if I want to achieve these goals together?

4 of 50

Last Time: 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))

Second approach: Use AEAD encryption modes designed to provide confidentiality, integrity, and authenticity

4

Computer Science 161

5 min - 12:45

Authenticated encryption gives us confidentiality and integrity (and sometimes authenticity) on a message, depending on your threat model.

We learned about our two methods to provide authenticated encryption.

Encrypt-then-MAC came out victorious because we determined it’s better because if you MAC-then-encrypt, this means you need to first decrypt before you can check whether any tampering has been done. Well.. this means that you’d always decrypt any tampered input, which could cause side-channel leaks (that problem where we were worried whether if Eve gave Bob a message to decrypt and Bob just willingly did it–well here’s an instance!).

Thus, we just always Encrypt-then-MAC.

The second approach we learned as AEAD encryption (Authenticated encryption with additional data), but a problem here is that if we have one tiny mistake (like reusing an IV), that would mean you’re losing all your cryptographic goals, instead of just one.�

Okay, well on that note, let’s move onto PRNGs and Diffie-Hellman for today!

5 of 50

Today: PRNGs and Diffie-Hellman Key Exchange

Symmetric-key encryption schemes need randomness. How do we securely generate random numbers?
When discussing symmetric-key schemes, we assumed Alice and Bob managed to share a secret key. How can Alice and Bob share a symmetric key over an insecure channel?

5

Computer Science 161

We’re going to solve two problems that we’ve kind of been avoiding for the past week, starting from last Tuesday. Yeah, remember when I kept saying “we’ll talk about it later”? Well, it’s now later, so let’s talk about it!

Our first topic is PRNGs, which will discuss how to securely generate random numbers. Why is that important? Because symmetric-key encryption schemes need randomness. Think IVs, nonces, the generation of keys. What does it mean to generate a random number in a secure way? Surprisingly, it’s not as simple as you think… it might even be more fun than you think!

Our second topic is the Diffie-Hellman Exchange. Remember in our symmetric cryptography unit and even yesterday when talking about MACs, we kept vaguely mentioning “oh, the cryptographic lords blessed Alice and Bob with the same cryptographic key”. Well, today’s the day to learn how to be the cryptographic lord. We’ll be discussing in symmetric-key schemes, how Alice and Bob actually share their symmetric keys over an insecure channel. What’s an insecure channel? One with our adversaries of course! We’ll talk about a method that allows Alice and Bob to somehow create a symmetric key that they both know, but the attackers don’t.

6 of 50

Pseudorandom Number Generators (PRNGs)

6

Textbook Chapter 9

Computer Science 161

7 of 50

Cryptography Roadmap

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

7

	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

8 of 50

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?

8

Computer Science 161

9 of 50

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)

9

Computer Science 161

Let’s define our randomness a bit.

Our scenario seems pretty reasonable, right? No one’s challenging that this isn’t a valid way to generate a secret bit string.

Let’s actually formalize how difficult it is for an attacker to guess a value.

If something has a high entropy, then it is pretty difficult to guess, whereas if something has low entropy, then it’s pretty easy to guess. The higher the entropy, the better in cryptography.

A coin with 50% probability of being heads and 50% of being tails has pretty high entropy because an attacker is going to struggle to correctly guess it. Compare that with a coin that has a 99% probability of being heads and 1% probability of being tails because they can just say “it’s probably heads” and they’d be right 99% of the time. This has low entropy–that’s bad.

Our unit of measurement is usually in bits for entropy. This means if we have 3 bits of entropy, this means that we have three bits to decide and since each bit can either be a 0 or a 1, this gives us a sample space 2^3=8 total possible values). Therefore, we’re working with a uniform, random distribution over 8 values.

10 of 50

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

10

Computer Science 161

What’s a real world scenario with breaking entropy?

This redacted person made an “IMPROV”ment to the random number generator in bitcoin by editing a lot of lines, and apparently this broke the bitcoin protocol for a bit (we’ll talk about this in our bitcoin lecture). But something that you can see if that they edited a lot of lines that effectively reduced the entropy used to generate the private keys. What private keys? Users for bitcoin use randomly-generated private keys to access their accounts (which is literally how they access and maintain their money) and this reduction in entropy made the keys brute-forceable. Uh oh.

Again, another case study showing you how important minor details can have major effects in the real world. A couple of bit shifts and logical operations? Bye bye bitcoin.

11 of 50

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)

However, true randomness is expensive and slow

11

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

Okay, well so what is high entropy? How do I actually generate these random numbers?

What I want is something that is truly random and hard to guess like a fair coin toss. In a computer though, you can’t ask a computer to just flip a coin for every random bit. So in order to create our truly random numbers, we use a physical source of entropy. This could mean….

Creating a super unpredictable circuit on a CPU. This could mean creating a circuit with a super high error tolerance and just letting it do whatever and tracking that–it’s out of the scope of this course what that actually means, but that’s a possibility.
Another possibility is to measure very fine time scales. For instance, human activity is an interesting physical source of entropy. For instance, if I clicked the next button on my laptop right now (do it), maybe you knew I pressed it on July 2nd, maybe even that it was near 1PM, maybe that it was at exactly 12:__. But maybe you were measuring the microseconds that that occurred at. Well, that’s much more random than the hour surely, and most definitely the date. Microseconds are a millionth of a second right, so it’s definitely a lot more unpredictable.
Cloudflare uses a wall of lava lamps that are recorded by an HD camera that views the lamps through a rotating prism and the lamps that light up–that’s your physical source of entropy.
Older ssh terminals would ask users to wiggle their mouse in a box to generate a key. And once you wiggle, those wiggles were the randomness that created the key.

If you have multiple random events that you can combine, then you can sum up its entropy to get a rough measure of how difficult is it for an attacker to guess an output value.

We’ve talked about a lot of different ways to create entropy, but these are all fairly costly and slow. You need to wait for the lava lamps to light up, or you need to wait for a key press, or a mouse wiggle, or an unpredictable circuit to spit something out. They’re expensive and slow to generate. Randomness cannot be rushed–it’s random. Furthermore, these physical sources of entropy are often biased. For instance, maybe in the mouse wiggling example, maybe left to right wiggles tend to be stronger than right to left wiggles, and that might bias or affect the outcome key. So if you have a source of entropy that’s biased, then that’s not good enough. Thus, if you have biased entropy, then you’ll want to combine multiple entropy sources. The thought here is that if you have a lot of biased entropy, it’s still entropy (like in a 99% heads coin, there’s still a 1% output of tails). In that case, the total number of bits of entropy is the sum of all the input numbers of bits of entropy.

True randomness is great because it’s that–truly random. But it’s so expensive, I don’t exactly want to be sitting around waiting for a random lava lamp to light up just to make an encryption key just to talk to my friend, let alone also wait for it to spit out an IV, so what’s a cheaper way to get randomness?

12 of 50

Pseudorandom Number Generators (PRNGs)

True randomness is expensive
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

12

Computer Science 161

15 min - 12:55

We don’t rely on randomness, but we rely on pseudorandomness. We’re going to create Pseudorandom Number Generators (PRNGs), which are actually deterministic algorithms that use a little bit of true randomness to generate a lot of random-looking output. They shuffle bits around in some predictable way (kind of like you saw in the code that was edited out in the bitcoin example), but from an attacker’s perspective, it looks random.

This makes it super cheap! We can just implement an algorithm that just takes in an initial value. And that’s cheap because computers are really good at taking input into a program and just running a deterministic program. Computers are also insanely fast, so no more sitting and waiting for a lava lamp to flicker. Then these algorithms do their dirty work to make their output look random.

Again, these algorithms are deterministic–they are not truly random. This means that the output is generated according to a set algorithm. However, for an attacker who can’t see the internal state of the PRNG, the output is computationally indistinguishable from true randomness.

However, I don’t want to have to rely on physical randomness like cosmic noise or lava lamps, but instead just run this algorithm to generate as many random numbers as I want. Instead this is something significantly cheaper and saves a lot more time, and is random looking. Okay, that’s kind of vague, so let’s define it.

13 of 50

PRNG: Definition

A PRNG has three functions:

PRNG.Seed(randomness): Initializes the internal state using some random bits

Input: Some truly random bits

PRNG.Reseed(randomness): Updates the internal state using the existing state and the random bits

Input: More 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
Additional security: Rollback resistance

13

Computer Science 161

In this class, this is what our PRNG is defined as. We’ll kind of use object-oriented programming and define PRNG as an object. This means that the PRNG has three methods:

Seed: What this does is it initializes the internal state using the input entropy. You can think of it as some deterministic algorithm that you feed some true randomness.
Reseed: This allows you to pass in even more randomness into the system. It updates the internal state using the existing state and the entropy. You can kind of think of the internal state value as a black box–we don’t really go in depth on the actual calculations, so bare tight with me.
Generate: Well, now we actually can generate our pseudorandomness. It’s going to take the truly random bits we’ve provided and run some algorithm on them to then output n pseudorandom bits and then update the internal state. Remember, under the hood the algorithm is really just a bunch of bit shuffles.

So what are the properties of our PRNG?

We believe in correctness. What is correctness? The fact that the algorithm (our bit shuffling) is deterministic. This means given I use the same seed twice, the same truly random bits twice, the string of pseudorandom numbers that I get returned are exactly the same. So similar to an IV, we should not be reusing our seeds in PRNGs.
Efficiency: It’s doing some bit shuffling, which we’ll take a look into later.
Then we have two security guarantees:

The first is indistinguishability from random. Now this should be setting off some lightbulbs. Indistinguishability? In cryptography? We must have a game defined. (In fact, we do)
Rollback resistance. This is something that we’ll talk about in depth in a bit, but is the core property of PRNGs.

14 of 50

PRNG: Seeding and Reseeding

A PRNG should be seeded with all available sources of entropy

As long as one source is good, results will be good
If all sources are independent, total entropy is sum of the entropy of each source, so more sources never hurts and can help

Reseeding is used to add even more entropy as it becomes available

Computer Science 161

Your seed can be as long as you want it to be. Remember that the number of bits of entropy should be the sum of all the number of bits in all sources. This means if you have the entropy from cosmic noise, the lava lamps, and from my key press sometime in the distant future, you should use all of that in the seeding of the PRNG.

If later, there’s another lava lamp that comes into play or I press another key, you can reseed to add even more entropy in the system.

If designed well, the PRNG should be able to combine all those sources of entropy. This should be summative even if we have super low entropy items. Namely, if we seed with a source that has 0 entropy, it should not reduce the entropy of the output. Likewise, reseeding with 0 entropy should not reduce the entropy of the internal state or output.

It’s better then to put in all values of entropy that you can into like a mixed salad of entropy to seed your PRNG. This means that if an attacker wants to try to guess the values and figure out what your PRNG values are, they’ll need to guess their way through all of the entropy values you’ve provided. So sure, your 99% heads coin flip isn’t great, but it is a source of low entropy that would still need to technically be guessed, so you might as well toss it in as another thing they need to get through.

15 of 50

PRNG: Security

Can we design a PRNG that is truly random?
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 2^s possible output sequences
Function: {0, 1}^S → {0, 1}^2S has 2^S inputs and 2^S outputs even though the output space is 2^2S

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 > 1/2 + negligible

Equivalent definition: An attacker cannot predict future output of the PRNG

15

Computer Science 161

Okay, but what was that indistinguishable from random property? Well PRNGs cannot be truly random by definition because the output is deterministic given the initial seed. This means that given the same input twice, you’ll get the same output twice. Furthermore, if the initial seed is s bits long, then you know there are only 2^s possible output sequences, even if output strings are 2s bits long. This reason for this is because we have 2^s inputs, and the algorithm itself is deterministic, so there are only really 2^s possible output sequences. This means that these PRNGs will not cover the full output space, and as such, aren’t truly random. There’s a limited number of inputs because there’s a limited number of outputs. This breaks the idea of being truly random because let’s say I, as an attacker, had the ability to find out all the possible 2^s outputs. Well, I’d be able to win more than 50% of the time because if I see a string that isn’t one of the 2^s possible outputs, then I know immediately that the other one must be the PRNG output.

In reality, we don’t care about these theoretical attackers since finding all of these possible outputs takes an exponential amount of time, so we instead discuss attackers who have a practical amount of time. Therefore, even though a PRNG cannot be truly random, a secure PRNG is computationally indistinguishable from random to an attacker. If an attacker does not know what I passed into the PRNG, then what they see as output is basically random. Our model is that the attacker doesn’t know the input into the PRNG, otherwise, they could just run the algorithm on our input, and this would be problematic since they’d see all our random values (remember these values are important–like keys and IVs–they need to be random!).

Now, unlike our IND-CPA and EU-CPA games, we’re not actually going to present this game in all of its gory detail. However, in our cryptographic game, let’s present the attacker with a truly random sequence and sequence outputted from a secure PRNG. The attacker should not be able to determine which is which with probability > 1/2 negligible. As the challenger, I need to generate a truly random sequence whether that be via coin flips, lava lamps, unpredictable circuits, etc. I’m then going to feed that into a secure PRNG, and your job as the attacker is to see whether you can determine whether you can tell the difference between another truly random sequence and the output of this secure PRNG. It is computationally indistinguishable if the attacker’s best guess is to just randomly guess. If you can’t tell the difference between the two, then this is a computationally indistinguishable scheme.

Another way to think of this is that we want to ensure that an attacker cannot predict future output of the PRNG. Okay, what does that mean? It means if I collect some truly random entropy (behind your back) and seed a secure PRNG and then show you the output of my PRNG. If I ask you what comes next in my PRNG, and I call generate again, as an attacker you have no shot at guessing what comes next.

16 of 50

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

16

Computer Science 161

https://www.wired.com/2017/02/russians-engineer-brilliant-slot-machine-cheat-casinos-no-fix/

Well, these numbers are just numbers right. What harm can they perform?

Well… it turns out PRNGs aren’t just used for cryptographic block ciphers or integrity schemes, but in everyone’s favorite slot machines. In St. Louis, there were some pretty sketchy people who would sit at slot machines with their phone out, not really playing, and then suddenly, when they actually pulled the lever, they’d win.

Well, how’d they know that they would win? The slot machines used predictable PRNGs based on the current time so when the the time was right and they knew the PRNG would produce the output they desired, they would pull the lever and more money than I’ve seen in my entire life would fall out.

Again, this is really just another motivation to really be careful when you’re using cryptographic schemes. Even when something might seem inconsequential, it’s not. It’s also a greater lesson that a lot of the world runs on algorithms that you’re used to know.

Luckily for anyone who enjoys Vegas as much as I do (hope you’re over 21), Las Vegas wasn’t affected by the vulnerability because Nevada has standards to ensure this doesn’t happen. I mean when you have an entire strip who earns tons of money off gambling, you’d hope they’d have standards.

17 of 50

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 previous 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 2¹⁵ (32,768) possible process IDs, so the PRNG only has 15 bits of entropy

Impact: Easy to deduce private keys generated with the PRNG

Set the PRNG to each possible starting state and generate a private/public key pair from each
See if the matching public key is anywhere on the Internet

17

Computer Science 161

http://blog.dieweltistgarnichtso.net/Caprica,-2-years-ago

Not just in slot machines, issues with predictable or insecure PRNGs come up in cryptography as well (which is expected). In OpenSSL, without enough entropy, basically it was really easy to deduce private keys that were generated with the PRNG because in cleaning up a Debian bug, the PRNG was only seeded with the process ID, which means there were only 15 bits of entropy: about 32000 possible inputs, and thus only 32000 possible PRNG.

In order to brute force deduce all the private keys, you just needed to set up the PRNG to every possible starting state and generate a few private/public key pairs (we’ll talk about this in the asymmetric cryptography section starting tomorrow) and based on those keys, see if you could find the matching public key anywhere on the internet and now you had someone’s private key. Uh oh…

18 of 50

PRNG: Rollback Resistance

Rollback resistance: If the attacker learns the internal PRNG state (e.g., by hacking into the machine and dumping its memory), they cannot learn anything about previous states or outputs
Rollback resistance is not required in a secure PRNG, but it is a useful property

Consider:

Alice uses the same PRNG to generate her Bitcoin secret key and other stuff, and stores the Bitcoin secret key offline in "cold storage"
Mallory hacks Alice's machine and learns the internal state of the PRNG
If the PRNG is not rollback resistant, Mallory can derive previous PRNG output… such as the secret key

18

Computer Science 161

"...but it should be" ~Nick Weaver

30 min - 1:10

Now we’re getting to the part that we were alluding to when we first introduced PRNGs half an hour ago: Rollback resistance. This is not actually a required property of PRNGs, but rather a nice one to have. What this property says is that if the attacker learns the internal PRNG state, they cannot learn anything about previous states or outputs.

This means let’s say there’s an unfortunate situation where an attacker hacks your laptop and has leaked the internal state of the PRNG (which is what is used to define its next generated values). Will they be able to generate the previous PRNG values by running it back? If so, then this PRNG is not rollback resistant. The way that this game works is since the attacker knows the current internal state, they’re now given a choice to see whether they can differentiate between a sequence of truly random bits and a sequence of previous output from the PRNG, maybe from 10 minutes ago, an hour ago, yesterday, etc. If they can determine which one is which with probability greater than one half then this PRNG is not rollback resistant.

Remember one of our previous definitions of PRNGs was that An attacker cannot predict future output of the PRNG. Well, it would also be nice if an attacker couldn’t learn anything about previous states or outputs as well! The only security requirement of PRNGs is that you shouldn’t be able to predict future outputs. Therefore, while rollback resistance is a nice feature to have, it’s not required. Nick Weaver, one of our former longtime lecturers of 161 believes it should be (and we probably agree!). Why?

Well, here’s a great example. Let’s consider… (read slide)

So we’ve formulated games for the actual security of PRNGs (indistinguishable from randomness) and for rollback resistance (games that are effectively the reverse from one another).

19 of 50

CTR-DRBG

AES in CTR mode generates m pseudo random bits by applying AES m/128 times and concatenating the result
Generate(m) = E_k(IV || 1) | E_k(IV || 2) | E_k(IV || 3) … E_k(IV || ceil(m/128))

19

Pseudorandomness,

PRNG output

Computer Science 161

(get through this quickly)

Now that we’ve deeply discussed all the properties of PRNGs, we can actually dive into what a PRNG actually looks like. An interesting thing is this is counter mode of AES from last Thursday. Counter mode is effectively a pseudorandom number generator.

If we set the seed to the K concatenated with the IV, this works as a pseudorandom number generator. Why? Well, because we can effectively utilize the output of the encryption cipher (no xoring of plaintext since there isn’t any here) and that’s our PRNG output. If you were to be able to figure this out, well you’d actually be breaking the CTR mode encryption scheme (so no one’s figured that out, which is why this is secure).

Without the key, like in our encryption schemes, you’d be lost.

Therefore, this is secure because the attacker cannot predict outputs because that would break the unpredictability of the block cipher’s random permutation. However, this scheme is not rollback resistant because if an adversary learns the key (the internal state), they can encrypt previous counters to learn previous output!

So, to quote Nicholas Weaver, “this is great, unless it fails. And then it fails catastrophically.”

20 of 50

HMAC-DRBG

Idea: HMAC output looks unpredictable. Let’s use HMAC to build a PRNG!
HMAC takes two arguments (key and message). Let’s keep two values, K (key) and V (value) as internal state

20

Computer Science 161

So there’s something that’s relatively similar, but a LOT better. Something cool is yesterday, we were talking about HMACs, right? Well, this PRNG utilizes HMACs.

Since HMACs utilize hashes, right? So outputs of an HMAC should look pretty unpredictable since one of our core properties of hashes was that it was Random/unpredictable, which meant there was no predictable patterns for how changing the input affects the output. As a reminder, this means that changing 1 bit in the input causes the output to be completely different. Let’s utilize this property to build out a PRNG.

We were previously discussing that PRNGs are like objects that store internal states. Well, we know that HMACs take in two arguments: a key and a message. Let’s then keep two values, K (a key) and V (a value) as an internal state. Okay, let’s get into the nitty gritty of the math.

21 of 50

HMAC-DRBG

Seed(s):

K := 0

V := 0

Reseed(s)

Reseed(s):

K := HMAC(K, V || 0x00 || s)

V := HMAC(K, V)

K := HMAC(K, V || 0x01 || s)

V := HMAC(K, V)

21

Initialize internal state

Update internal state with provided entropy

Computer Science 161

Okay, so before we explain what’s happening here, I want to note that on exams and in homework, we’re not going to ask you, “hey! Walk me through the HMAC-DRBG algorithm works” I know these technically aren’t on blue slides, but we’re not going to ask you to reconstruct it.

The specifics of HMAC aren’t super important here, the important thing here is that there’s nothing fancy. I’m simply just calling HMAC over and over again, which is creating our random-looking output over and over again.

So in our seeding operation, what we do is we first initialize our internal state of K to 0 and V to 0, and then start to call HMAC to generate and update K and V. Notice how we lace in the seed s into our generation of K, so our key itself gets more and more entropy. Now, we have our key and value initialized as desired.

22 of 50

HMAC-DRBG

Generate(n):

output := ''

while len(output) < n do

V := HMAC(K, V)

output := output || V

end while�

K := HMAC(K, V || 0x00)

V := HMAC(K, V)

return output[:n]

22

Call HMAC repeatedly to generate random-looking output

Update internal state, without adding extra entropy

Computer Science 161

23 of 50

HMAC-DRBG: Security

Assuming HMAC is secure, HMAC-DRBG is a secure, rollback-resistant PRNG

Secure: If you can distinguish PRNG output from random, then you’ve distinguished HMAC from random
Rollback-resistant: If you can derive old output from the current state, then you’ve reversed the hash function or HMAC
The full proof is out of scope
In other words: if you break HMAC-DRBG, you’ve either broken HMAC or the underlying hash function

23

Computer Science 161

"HMAC-DRBG is the best PRNG construction: accept no substitutes!" ~Nick Weaver [TODO Nick]

Here are some nice security guarantees of HMAC-DRBG:

We know that HMAC-DRBG is secure because if you can distinguish the PRNG generated outputs from random, then you’ve distinguished HMAC from random

This isn’t possible if the key K is secure (which we’ve defined via entropy)

HMAC-DRBG is rollback resistant because if you can derive old output from the current state, this means you’re able to reverse the hash function or HMAC

Okay, why? Well if someone’s hacked in my HMAC-DRBG internal state, they can see my key and values–they know the entropy. Well, they can definitely see what my next outputted PRNG values will be in the forward direction (that’s never up for contention, since giving up your key gives up the forward values of your system so change your key!!!). But that’s not actually what rollback resistance is back right? Rollback resistance is about whether seeing your current internal state will give up previous PRNG outputs? So like outputs from yesterday, last Friday? Well, HMAC-DRBG is rollback resistant because hashes are one-way, so in order to see previous values, you’d have to be able to reverse an HMAC to see what the input of an HMAC was, but then that means you’d have to be able to reverse a hash since an HMAC is a hash, so you’d be effectively breaking hashes. And if you broke SHA-3, we’d be a deeeeep trouble right now.

This means that if you break HMAC-DRBG, you’ve either broken the HMAC algorithm itself (which, first congrats, second remember me when you’re writing up your paper on that) or the underlying hash function (again, congrats, please write a paper on that).

What’s the speed? Well, this is pretty fast because HMAC is pretty fast. For each of seed and reseed, we’re making four HMAC calls. For generate, 1 HMAC call per block of bits plus 2 HMAC calls per call, so it does scale with the number of bits you need in your generated random number, but it’s still not too bad.

Nicholas Weaver, our former esteemed lecturer, believes that you should accept no substitutes. Even if your machine uses a PRNG, if you’re ever building a system, use that to seed HMAC-DRBG. It relies on the hash functions that have stood the test of time thus far.

The last statement is the contrapositive of the first.

24 of 50

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!

24

Computer Science 161

40 min - 1:20

Okay more insecure uses of PRNGs? Well yes! Surprisingly, broken and insecure usage of PRNGs shows up everywhere because a lot of people spend a lot of time setting up a strong, secure cryptographic scheme and neglect the random inputs it needs–and that, unfortunately breaks their system. This is again a lesson in knowing that you can make a super strong fortress, but letting one crack in will destroy it all.

Okay, well let’s say you wrote an app in JHipster before 2019 and you forgot your password, oops! When you receive the email with the special link to reset your password in your email, that link usually has some randomly-generated code that the system generated so the attacker can’t make their own link.

You can see where I”m going right… well the PRNG was bad so somehow attackers could figure out the PRNG’s internal state from the reset link and request password reset links for other people’s accounts and knowing what the randomly-generated code was allowed them to take over the accounts they wanted to.

25 of 50

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?

25

Computer Science 161

Nick got in a Twitter fight over this (2020)

https://twitter.com/ncweaver/status/1308178039755350018

Here’s another one. Nicholas Weaver (mentioned throughout this lecture) actually got in a twitter fight about this in 2020). There’s a lot going on here, but the main takeaway is to always use a secure PRNG. Please do not design your own PRNG–use a secure library! I know that sounds boring and lame right now, but don’t blame me if you cause a data leak years down the road because of one tiny misstep.

For PRNGs in specific, this is what our randomness is in cryptography. If you design a great system, but neglect to use a good PRNG, well, you’re busted. For instance, if an attacker can guess all your future randomness, this actually breaks a few schemes: one of which is CBC. In Homework 2, a question actually discussed something similar to this–so feel free to review this.

26 of 50

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 a long enough value, 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

26

Computer Science 161

Here’s a sneak peak into Project 2–you’ll need to use randomness to define your universally unique identifiers (UUIDs). Wow, say that five times fast.

Imagine you have a bunch of objects, and you need every object to have a unique name. Well, what if you also want the names to be unpredictable (you don’t want people to know that Bob has a filename called “secret.txt”. Well, you can choose a random value.

Well Ashley, hang on, isn’t it possible that we choose the same random number twice? It’s possible, but exceedingly rare. UUIDs are 128-bit unique values, so our output space is 2^128 bits. This means the probability of getting the same value twice is 1/2^128. Is that going to happen? Probably not. Especially not in Project 2. We always get questions about whether IDs in project 2 will collide. Well, the practical possibility of this occurring is basically 0.

27 of 50

PRNGs: Summary

True randomness requires sampling a physical process

Slow and expensive (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
Reseed(entropy): Add additional entropy to the internal state
Generate(n): Generate n bits of pseudorandom output
Security: Computationally indistinguishable from truly random bits

CTR-DRBG: Use a block cipher in CTR mode to generate pseudorandom bits
HMAC-DRBG: Use repeated applications of HMAC to generate pseudorandom bits
Application: UUIDs

27

Computer Science 161

The TL;DR of PRNGs is that we strive for true randomness, but that ends up being too slow, expensive, and sometimes has too low entropy for us. What we do then, is utilize a small bit of this physical true randomness and entropy and feed it into a deterministic algorithm that we call our PRNG that then has the ability to generate a lot of random looking output.

PRNGs have three core functions: seed (initialize internal state), reseed (add more entropy later on), and generate (generate n bits of pseudorandom output).

There is a security guarantee that in PRNGs that they are computationally indistinguishable from truly random bits, which means if I give you output from a PRNG and then truly random bits, you have around a 50% success rate guessing which is which (basically like blindly guessing).

Then we talked about rollback resistance, which is the concept that if the internal state of a PRNG is leaked, then we don’t want attackers to be able to see the previous output of the PRNG (since that could leak sensitive information like a key).

We discussed two practical PRNGS:

CTR-DRBG, which is built off CTR mode, but lacks rollback resistance because leaking the key leaks all the past values outputted from the encryption cipher
HMAC-DRBG, which is both a secure PRNG and has rollback resistance because if you could see past values, then you’d be breaking the one-wayness of hashes

28 of 50

Stream Ciphers

28

Textbook Chapter 9.5

Computer Science 161

29 of 50

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

29

Computer Science 161

30 of 50

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

30

⊕

Generate(n)

Seed(K)

Generate(n)

⊕

Plaintext

Ciphertext

Plaintext

Alice

Bob

Computer Science 161

31 of 50

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?

31

⊕

Generate(n)

Seed(K)

Alice

Bob

Seed(K)

Generate(n)

⊕

Plaintext

Ciphertext

Plaintext

Computer Science 161

32 of 50

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

32

⊕

Generate(n)

Seed(K || IV)

Alice

Bob

Seed(K || IV)

Generate(n)

⊕

Plaintext

Ciphertext

Plaintext

IV

Computer Science 161

33 of 50

Stream Ciphers: AES-CTR

If you squint carefully, AES-CTR is a type of stream cipher
Output of the block cipher is pseudorandom and used as a one-time pad

Computer Science 161

34 of 50

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 2ⁿ^/2 bits of output
Example: In AES-CTR with 128-bit counters, stop after 2⁶⁴ blocks of output

34

Computer Science 161

35 of 50

Stream Ciphers Support Streaming

Stream ciphers can continually process new data as it arrives

Only need to maintain internal state of the PRNG
Keep generating more PRNG output as more input arrives

35

Computer Science 161

36 of 50

Stream Ciphers Support Seeking

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
With HMAC-DRBG, you have to generate all the PRNG output up until the block you want to decrypt

36

Computer Science 161

Some stream ciphers have this extra benefit. Let’s say that you’re given an encrypted 1 GB file, maybe of a movie, and maybe you’re short on time and you just want to know how it ends–we’ve all been there. Well, some stream ciphers like AES-CTR allow you to decrypt individual blocks–potentially even out of order. Well, in other modes of encryption like AES-CBC, you’d need to decrypt the entire thing to get to the end, not even discussing the padding that would be needed, which doesn’t bode well on streams.

In contrast, streams work in blocks or bits, so you can just skip directly to the end. You don’t need to decrypt all the bytes–just the ones that you need to.

However, this doesn’t hold for all stream ciphers because for instance, for HMAC-DRBG, you’d need to generate all the PRNG output (basically performing HMAC over and over again) until you get to the block you want to decrypt.

37 of 50

Next: Diffie-Hellman Key Exchange

When discussing symmetric-key schemes, we assumed Alice and Bob managed to share a secret key. How can Alice and Bob share a symmetric key over an insecure channel?

37

Computer Science 161

38 of 50

Diffie-Hellman Key Exchange

38

Textbook Chapter 10

Computer Science 161

39 of 50

Cryptography Roadmap

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

39

	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

40 of 50

Secure Color Sharing

Computer Science 161

Use the laser

Here’s an analogy. Let’s say Alice and Bob are painting and really want to create a secret color that no one else knows but they both know. It’s this like poopy brown color at the bottom. They’re the epitome of gaslight gatekeep girlboss. But they can only share their colors over an insecure channel, where all the other paint gossipers and pantone live (ugh pantone). Eve and Mallory are part of the paint gossipers. So they can’t just send their secret colors (the red, blue, or brown) over the channel or else everyone will see and it won’t be secret anymore.

So what they do instead is they’ll each decide on whatever secret color they want mixed in. Alice picks this red and Bob picks this teal. They’ll disguise what secret color each of them are using by deciding on a common color (which everyone can know), which is this neon yellow and then mixing their individual secret colors with yellow. This means Alice ends up with this orange and Bob ends up with this blue. Now, they pass these disguised combined colors across the insecure channel (notice how this is technically the only place where anything passes the insecure channel).

Now add back their own. So on Alice’s side, she has the mixed disguised Yellow and Teal from Bob and adds in her own Red to create the poopy brown color (from yellow, teal, and red). On Bob’s side, he has Alice’s mixed yellow and red and adds back in his own teal to get the same poopy brown color.

Now that’s their common secret.

Okay, so why does this work? The thought here is that trying to mix out the yellow from these disguised combined paints is expensive–far too expensive for any paint gossiper or heaven forbid pantone. We’re going to just make an assumption (for the sake of the analogy) that these paint gossipers don’t actually know color theory. This means that if we look at this orange alone and we knew yellow paint went into it, we had no way of guessing that Alice’s secret color is red. Likewise, looking at the blue alone from Bob’s disguised mixed solution, we’d never be able to deduce that Bob’s secret color is teal (I promise the math version is going to be a lot more convincing).

Even if Eve just mixed the two disguised colors, she’d get like a yellow x 2 + red + teal, which is like a slightly lighter poopy brown? Still not the secret color, so Alice and Bob’s secret is still safe!

41 of 50

Secure Color Sharing

Alice

Bob

Computer Science 161

Use the laser

Here’s an analogy. Let’s say Alice and Bob are painting and really want to create a secret color that no one else knows but they both know. It’s this like poopy brown color at the bottom. They’re the epitome of gaslight gatekeep girlboss. But they can only share their colors over an insecure channel, where all the other paint gossipers and pantone live (ugh pantone). Eve and Mallory are part of the paint gossipers. So they can’t just send their secret colors (the red, blue, or brown) over the channel or else everyone will see and it won’t be secret anymore.

So what they do instead is they’ll each decide on whatever secret color they want mixed in. Alice picks this red and Bob picks this teal. They’ll disguise what secret color each of them are using by deciding on a common color (which everyone can know), which is this neon yellow and then mixing their individual secret colors with yellow. This means Alice ends up with this orange and Bob ends up with this blue. Now, they pass these disguised combined colors across the insecure channel (notice how this is technically the only place where anything passes the insecure channel).

Now add back their own. So on Alice’s side, she has the mixed disguised Yellow and Teal from Bob and adds in her own Red to create the poopy brown color (from yellow, teal, and red). On Bob’s side, he has Alice’s mixed yellow and red and adds back in his own teal to get the same poopy brown color.

Now that’s their common secret.

Okay, so why does this work? The thought here is that trying to mix out the yellow from these disguised combined paints is expensive–far too expensive for any paint gossiper or heaven forbid pantone. We’re going to just make an assumption (for the sake of the analogy) that these paint gossipers don’t actually know color theory. This means that if we look at this orange alone and we knew yellow paint went into it, we had no way of guessing that Alice’s secret color is red. Likewise, looking at the blue alone from Bob’s disguised mixed solution, we’d never be able to deduce that Bob’s secret color is teal (I promise the math version is going to be a lot more convincing).

Even if Eve just mixed the two disguised colors, she’d get like a yellow x 2 + red + teal, which is like a slightly lighter poopy brown? Still not the secret color, so Alice and Bob’s secret is still safe!

42 of 50

Secure Color Sharing

Suppose Alice and Bob want a secret paint color, but Eve can see paint colors sent between Alice and Bob
Alice generates a secret color amber A, and Bob generates a secret color blue B
Alice and Bob agree on a common, public color green G
They both mix their secret colors with G, so Alice has green-amber GA, and Bob has green-blue GB
Alice sends GA to Bob, and Bob sends GB to Alice

Note: Eve now knows the colors GA and GB! Assume that it is hard to separate colors.

Alice knows GB, so she can mix in A to form green-amber-blue GAB. Bob knows GA, so he can mix in B to form GAB, as well!

Eve only knows G, GA, and GB, so she can only form green-amber-green-blue GAGB, which is not the same!

Computer Science 161

43 of 50

Discrete Log Problem and Diffie-Hellman Problem

There is a mathematical version of this
Assume everyone knows a large prime p (e.g. 2048 bits long) and a number g
Discrete logarithm problem (discrete log problem): Given g, p, g^a mod p for random a, it is computationally hard to find a
Diffie-Hellman assumption: Given g, p, g^a mod p, and g^b mod p for random a, b, no polynomial time attacker can distinguish between a random value R and g^ab mod p.

Intuition: The best known algorithm is to first calculate a and then compute (g^b)^a mod p, but this requires solving the discrete log problem, which is hard!
Note: Multiplying the values doesn’t work, since you get g^a⁺^b mod p ≠ g^ab mod p

43

Computer Science 161

44 of 50

Discrete Log Problem

44

Plot of g^a mod p

Plot of g^a

Computer Science 161

45 of 50

Diffie-Hellman Key Exchange

45

Alice

Mallory

Bob

Generate a

Calculate g^a mod p

Receive g^b mod p

Calculate (g^b)^a mod p

Generate b

Calculate g^b mod p

Receive g^a mod p

Calculate (g^a)^b mod p

g^amod p

g^bmod p

a, g^a, g^b ⇒ g^a^b

b, g^a, g^b ⇒ g^a^b

g^a, g^b ⇒ g^a^b

Eve

Public: g, p

Shared symmetric key is g^a^b

Secret key

Public key

Computer Science 161

1 hr - 1:40 (this is so optimistic)

Here is the math version of our original paint slide. Unfortunately, since computers can’t mix paint, we have to deal with math.

Let’s build up our system, so everything on the left is Alice’s domain and what she sees and knows. Everything on the right is Bob’s domain and what he sees and knows, and everything passed through the middle is what Eve, our eavesdropper can see and know.

First up, Alice generates a, her secret key, and then calculates g^a mod p–this is equivalent to the disguised, mixed value that she created in the paint analogy. Remember, this works because although it’s public what g and p are, it is computationally impossible to determine a. Bob does the same thing on his side, generating his secret key b and calculating g^b mod p.

Now, they exchange: Alice sends g^a mod p and Bob sends g^b mod p.

Now, they need to generate their final secret key.

Okay, let’s look at Alice’s side. Alice received g^b mod p from Bob and Alice also has a (since that was her own secret key). Therefore, she can calculate (g^b)^a mod p, which is the secret key between Alice and Bob.

The same thing happens on Bob’s side. Bob received g^a mod p from Alice and Bob also had b (since that was his secret key). Therefore, he calculates (g^a)^b mod p, which is the secret key between Alice and Bob.

What about Eve in the middle? Eve doesn’t know a or b. She knows g^a mod p and g^b mod p. If she multiplied them together, that doesn’t actually get g^ab mod p.

46 of 50

Ephemeral Diffie-Hellman

Diffie-Hellman can be used to generate a symmetric key whenever Alice and Bob want to communicate (called Diffie-Hellman ephemeral, or DHE)

Ephemeral: Short-term and temporary, not permanent
Alice and Bob discard a, b, and K = g^ab mod p when they’re done
Sometimes K is called a session key, because it’s only used for a single session

Benefit of DHE: Forward secrecy

Suppose Alice and Bob use DHE to agree on a key K = g^ab mod p, then encrypt messages with K, and after they’re done, discard a, b, and K
If Eve records everything sent over the public channel, and Eve later steals all of Alice and Bob’s secrets, Eve still can’t decrypt any messages she recorded: Nobody saved a, b, or K, and her recording only has g^a mod p and g^b mod p!

46

Computer Science 161

47 of 50

Diffie-Hellman: Security

47

Alice

Bob

Generate a

Calculate g^a mod p

Receive g^m mod p

Calculate (g^m)^a mod p

Generate b

Calculate g^b mod p

Receive g^m mod p

Calculate (g^m)^b mod p

a, g^a, g^m ⇒ g^a^m

b, g^b, g^m ⇒ g^b^m

m, g^m, g^a ⇒ g^a^m

Mallory

Public: g, p

Generate m

Calculate g^m mod p

Receive g^a mod p

Calculate (g^a)^m mod p

Receive g^b mod p

Calculate (g^b)^m mod p

m, g^m, g^b ⇒ g^b^m

Computer Science 161

The one problem that we’ve been neglecting. Ah, Mallory. So remember our distinction between Eve and Mallory is that Eve only has the ability to read messages, but Mallory can tamper. Can Mallory do anything weird?

Well, let’s proceed like in our previous example. First up, Alice generates a, her secret key, and then calculates g^a mod p–this is equivalent to the disguised, mixed value that she created in the paint analogy. Remember, this works because although it’s public what g and p are, it is computationally impossible to determine a. Then she sends this to Bob, except wait, Mallory’s there. So Mallory’s the one that receives g^a mod p and decides, I don’t want Bob to receive that and now generates her own secret key m, sending g^m mod p to Bob. The same thing happens when Bob tries to send g^b mod p, so likewise Alice receives g^m mod p. So Alice and Bob, instead of receiving each other’s disguised secrets, now both receive Mallory’s secrets.

This means that the key that Alice ends up creating is g^am mod p and the key that Bob ends up creating is g^bm mod p. So they can’t even create the same keys to communicate anymore. But it gets worse because Mallory actually knows these two keys since she was part of that exchange! She can take Alice’s g^a mod p to the power of m to calculate her shared key with Alice and then take BOb’s g^b mod p to the power of m to calculate her shared key with Bob.

This means that we’ve effectively set up two Diffie-Hellman exchanges where Mallory is the “man in the middle”. This is a “man in the middle” attack as she can intercept both Alice and Bob and create her own handshakes with them separately. This means Mallory can read every message that Alice is sending to Bob and can change it and vice versa.

48 of 50

Diffie-Hellman: Issues

Diffie-Hellman is not secure against a MITM adversary
DHE is an active protocol: Alice and Bob need to be online at the same time to exchange keys

What if Bob wants to encrypt something and send it to Alice for her to read later?
Next time: How do we use public-key encryption to send encrypted messages when Alice and Bob don’t share keys and aren’t online at the same time?

Diffie-Hellman does not provide authentication

You exchanged keys with someone, but Diffie-Hellman makes no guarantees about who you exchanged keys with; it could be Mallory!

48

Computer Science 161

49 of 50

Elliptic-Curve Diffie-Hellman (ECDH)

This can be generalized to other multiplication operations

The discrete-log problem seems hard because exponentiating integers in modular arithmetic “wraps around”
Diffie-Hellman can be generalized to any mathematical group that has this cyclic property

Elliptic curves: A funky way to "multiply"

You don’t need to understand the math behind elliptic curves

Elliptic-curve Diffie-Hellman: A variation of Diffie-Hellman that uses elliptic curves instead of modular arithmetic

Benefit of ECDH: The underlying problem is harder to solve, so we can use smaller keys (3072-bit DHE is about as secure as 384-bit ECDHE)

Computer Science 161

50 of 50

Summary: Diffie-Hellman Key Exchange

Algorithm:

Alice chooses a and sends g^a mod p to Bob
Bob chooses b and sends g^b mod p to Alice
Their shared secret is (g^a)^b = (g^b)^a = g^a^b mod p

Diffie-Hellman provides forwards secrecy: Nothing is saved or can be recorded that can ever recover the key
Issues

Not secure against MITM
Both parties must be online
Does not provide authenticity

50

Computer Science 161