Q6

jimpop1998

Chapter11_DiffieHellman_SeriousCryptography.pdf

Home >Computer Science homework help >Q6

11 DIFFIE–HELLMAN

In November 1976, Stanford researchers Whitfield Diffie and Martin Hellman

published a research paper titled “New Directions in Cryptography” that revolu-

tionized cryptography forever. In their paper, they introduced the notion of pub-

lic-key encryption and signatures, though they didn’t actually have any of those

schemes; they simply had what they termed a public-key distribution scheme, a

protocol that allows two parties to establish a shared secret by exchanging infor-

mation visible to an eavesdropper. This protocol is now known as the Diffie–

Hellman (DH) protocol.

Prior to Diffie–Hellman, establishing a shared secret required performing tedious

procedures such as manually exchanging sealed envelopes. Once communicating

parties have established a shared secret value with the DH protocol, that secret

can be used to establish a secure channel by turning the secret into one or more

symmetric keys that are then used to encrypt and authenticate subsequent com-

munication. The DH protocol—and its variants—are therefore called key agree-

ment protocols.

In the first part of this chapter, I review the mathematical foundations of the

Diffie–Hellman protocol, including the computational problems that DH relies on

to perform its magic. I then describe different versions of the Diffie–Hellman pro-

tocol used to create secure channels in the second part of this chapter. Finally, be-

cause Diffie–Hellman schemes are only secure when their parameters are well

chosen, I conclude the chapter by examining scenarios where Diffie–Hellman can

fail.

https://learning.oreilly.com/home/

NOTE

Diffie and Hellman received the prestigious Turing Award in 2015 for

their invention of public-key cryptography and digital signatures, but

others deserve credit as well. In 1974, two years before the seminal

Diffie–Hellman paper, computer scientist Ralph Merkle introduced the

idea of public-key cryptography with what are now called Merkle’s puz-

zles. Around that same year, researchers at GCHQ (Government

Communications Headquarters), the British equivalent of the NSA, had

also discovered the principles behind RSA and Diffie–Hellman key

agreement, though that fact would only be declassified decades later.

The Diffie–Hellman Function

In order to understand DH key agreement protocols, you must first understand

their core operation, the DH function. The DH function will usually work with

groups denoted Z . Recall from Chapter 9 that these groups are formed of non-

zero integer numbers modulo a prime number, denoted p. Another public param-

eter is the base number, g. All arithmetic operations are performed modulo p.

The DH function involves two private values chosen randomly by the two commu-

nicating parties from the group Z , denoted a and b. A private value a has a pub-

lic value associated with A = g mod p, or g raised to the power a modulo p. This

value is sent to the other party through a message that is visible to eavesdroppers.

The public value associated with b is B = g mod p, or g raised to the power b mod-

ulo p, which is sent to the owner of a through a publicly readable message.

DH works its magic by combining either public value with the other private value,

such that the result is the same in both cases: A = (g ) = g and B = (g ) = g

= g . The resulting value, g , is the shared secret; it is then passed to a key deri-

vation function (KDF) in order to generate one or more shared symmetric keys. A

KDF is a kind of hash function that will return a random-looking string the size of

the desired key length.

And that’s it. Like many great scientific discoveries (gravity, relativity, quantum

computing, or RSA), the Diffie–Hellman trick is terribly simple in hindsight.

p *

b a b ab a b a ba

ab ab

https://learning.oreilly.com/library/view/serious-cryptography/9781492067511/xhtml/ch09.xhtml#ch9

Diffie–Hellman’s simplicity can be deceiving, however. For one thing, it won’t

work with just any prime p or base number g. For example, some values of g will

restrict the shared secrets g to a small subset of possible values, whereas you’d

expect to have about as many possible values as elements in Z , and therefore as

many possible values for the shared secret. To ensure the highest security, safe

DH parameters should work with a prime p such that (p – 1) / 2 is also prime. Such

a safe prime guarantees that the group doesn’t have small subgroups that would

make DH easier to break. With a safe prime, DH can notably work with g = 2,

which makes computations slightly faster. But generating a safe prime p takes

more time than generating a totally random prime.

For example, the dhparam command of the OpenSSL toolkit will only generate safe

DH parameters, but the extra checks built into the algorithm result increase the

execution time considerably, as shown in Listing 11-1.

$ time openssl dhparam 2048

Generating DH parameters, 2048 bit long safe prime, generator 2

This is going to take a long time

--snip--

-----BEGIN DH PARAMETERS-----

MIIBCAKCAQEAoSIbyA9e844q7V89rcoEV8vd/l2svwhIIjG9EPwWWr7FkfYhYkU9

fRNttmilGCTfxc9EDf+4dzw+AbRBc6oOL9gxUoPnOd1/G/YDYgyplF5M3xeswqea

SD+B7628pWTaCZGKZham7vmiN8azGeaYAucckTkjVWceHVIVXe5fvU74k7+C2wKk

iiyMFm8th2zm9W/shiKNV2+SsHtD6r3ZC2/hfu7XdOI4iT6ise83YicU/cRaDmK6

zgBKn3SlCjwL4M3+m1J+Vh0UFz/nWTJ1IWAVC+aoLK8upqRgApOgHkVqzP/CgwBw

XAOE8ncQqroJ0mUSB5eLqfpAvyBWpkrwQwIBAg==

-----END DH PARAMETERS-----

openssl dhparam 2048 154.53s user 0.86s system 99% cpu 2:36.85 total

Listing 11-1: Measuring the execution time of generating 2048-bit Diffie–Hellman

parameters with the OpenSSL toolkit

As you can see in Listing 11-1, it took 154.53 seconds to generate the DH parame-

ters using the OpenSSL toolkit. Now, for the sake of comparison, Listing 11-2

shows how long it takes on the same system to generate RSA parameters of the

p *

same size (that is, two prime numbers, p and q, each half the size of the p used for

DH).

$ time openssl genrsa 2048

Generating RSA private key, 2048 bit long modulus

...................................................+++

.............................................................+++

e is 65537 (0x10001)

-----BEGIN RSA PRIVATE KEY-----

--snip--

-----END RSA PRIVATE KEY-----

openssl genrsa 2048 0.16s user 0.01s system 95% cpu 0.171 total

Listing 11-2: Generating 2048-bit RSA parameters while measuring the execution

time

Generating DH parameters took about 1000 times longer than generating RSA pa-

rameters of the same security level, mainly due to the extra constraint imposed

on the prime generated to create DH parameters.

The Diffie–Hellman Problems

The security of DH protocols relies on the hardness of computational problems,

especially on that of the discrete logarithm problem (DLP) introduced in Chapter

9. Clearly, DH can be broken by recovering the private value a from its public

value g , which boils down to solving a DLP instance. But we don’t care only

about the discrete logarithm problem when using DH to compute shared secrets.

We also care about two DH-specific problems, as explained next.

The Computational Diffie–Hellman Problem

The computational Diffie–Hellman (CDH) problem is that of computing the shared

secret g given only the public values g and g , and not any of the secret values

a or b. The motivation is obviously to ensure that even if an eavesdropper cap-

tures g and g , they should not be able to determine the shared secret g .

ab a b

a b ab

https://learning.oreilly.com/library/view/serious-cryptography/9781492067511/xhtml/ch09.xhtml#ch9

If you can solve DLP, then you can also solve CDH; to put it simply, if you can solve

DLP, then given g and g , you’ll be able to derive a and b to compute g . In other

words, DLP is at least as hard as CDH. But we don’t know for sure whether CDH is

at least as hard as DLP, which would make the problems equally hard. In other

words, DLP is to CDH what the factoring problem is to the RSA problem. (Recall

that factoring allows you to solve the RSA problem, but not necessarily the

converse.)

Diffie–Hellman shares another similarity with RSA in that DH will deliver the

same security level as RSA for a given modulus size. For example, the DH protocol

with a 2048-bit prime p will get you about the same security that RSA with a 2048-

bit modulus n offers, which is about 90 bits. Indeed, the fastest way we know to

break CDH is to solve DLP using an algorithm called the number field sieve, a

method similar but not identical to the fastest one that breaks RSA by factoring its

modulus: the general number field sieve (GNFS).

The Decisional Diffie–Hellman Problem

Sometimes we need something stronger than CDH’s hardness assumption. For ex-

ample, imagine that an attacker can compute the first 32 bits of g given the

2048-bit values of g and g , but that they can’t compute all 2048 bits. Although

CDH would still be unbroken because 32 bits aren’t enough to completely recover

g , the attacker would still have learned something about the shared secret,

which might still allow them to compromise an application’s security.

To ensure that an attacker can’t learn anything about the shared secret g , this

value needs only to be indistinguishable from a random group element, just as an

encryption scheme is secure when ciphertexts are indistinguishable from random

strings. The computational problem formalizing this intuition is called the deci-

sional Diffie–Hellman (DDH) problem. Given g , g , and a value that is either g or

g for some random c (each of the two with a chance of 1/2), the DDH problem

consists of determining whether g (the shared secret corresponding to g and

g ) was chosen. The assumption that no attacker can solve DDH efficiently is

called the decisional Diffie–Hellman assumption.

If DDH is hard, then CDH is also hard, and you can’t learn anything about g . But

if you can solve CDH, you can also solve DDH: given a triplet (g , g , g ), you

a b ab

a b

a b ab

ab a

a b c

would be able to derive g from g and g and check whether the result is equal

to the given g . The bottom line is that DDH is fundamentally less hard than CDH,

yet DDH hardness is a prime assumption in cryptography, and one of the most

studied. We can be confident that both CDH and DDH are hard when Diffie–

Hellman parameters are well chosen.

More Diffie–Hellman Problems

Sometimes cryptographers devise new schemes and prove that they are at least as

hard to break as it is to solve some problem related to CDH or DDH but not identi-

cal to either of these. Ideally, we’d like to demonstrate that breaking a cryptosys-

tem is as hard as solving CDH or DDH, but this isn’t always possible with ad-

vanced cryptographic mechanisms, typically because such schemes involve more

complex operations than basic Diffie–Hellman protocols.

For example, in one DH-like problem, given g , an attacker would attempt to com-

pute g , where 1 / a is the inverse of a in the group (typically Z for some prime

p). In another, an attacker might distinguish the pairs (g , g ) from the pairs (g ,

g ) for random a and b. Finally, in what is called the twin Diffie–Hellman prob-

lem, given g , g , and g , an attacker would attempt to compute the two values g

and g . Sometimes such DH variants turn out to be as hard as CDH or DDH, and

sometimes they’re fundamentally easier—and therefore provide lower security

guarantees. As an exercise, try to find connections between the hardness of these

problems and that of CDH and DDH. (Twin Diffie–Hellman is actually as hard as

CDH, but that isn’t easy to prove!)

Key Agreement Protocols

The Diffie–Hellman problem is designed to build secure key agreement protocols

—protocols designed to secure communication between two or more parties com-

municating over a network with the aid of a shared secret. This secret is turned

into one or more session keys—symmetric keys used to encrypt and authenticate

the information exchanged for the duration of the session. But before studying ac-

tual DH protocols, you should know what makes a key agreement protocol secure

or insecure, and how simpler protocols work. We’ll begin our discussion with a

widely used key agreement protocol that doesn’t rely on DH.

ab a b

1 / a p

a b a

1 / a

a b c ab

An Example of Non-DH Key Agreement

To give you a sense of how a key agreement protocol works and what it means for

it to be secure, let’s look at the protocol used in the 3G and 4G telecommunications

standards to establish communication between a SIM card and a telecom opera-

tor. The protocol is often referred to as AKA, for authenticated key agreement. It

doesn’t use the Diffie–Hellman function, but instead uses only symmetric-key op-

erations. The details are a bit boring, but essentially the protocol works as shown

in Figure 11-1.

Figure 11-1: The authenticated key agreement protocol in 3G and 4G

telecommunication

In this implementation of the protocol, the SIM card has a secret key, K, that the

operator knows. The operator begins the session by selecting a random value, R,

and then computes two values, SK and V , based on two pseudorandom functions,

PRF0 and PRF1. Next, the operator sends a message to the SIM card containing

the values R and V , which are visible to attackers. Once the SIM card has R, it has

what it needs in order to compute SK with PRF0, and it does so. The two parties in

this session end up with a shared key, SK, that attackers are unable to determine

by simply looking at the messages exchanged between the parties, or even by

modifying them or injecting new ones. The SIM card verifies that it’s talking to the

operator by recomputing V with PRF1, K, and R, and then checking to make sure

that the calculated V matches the V sent by the operator. The SIM card then

computes a verification value, V , with a new function, PRF2, with K and R as in-

put, and sends V to the operator. The operator verifies that the SIM card knows K

1 1

by computing V and checking that the computed value matches the V it

received.

But this protocol is not immune to all kinds of attacks: in principle there’s a way

to fool the SIM card with a replay attack. Essentially, if an attacker captures a pair

(R, V ), they may send it to the SIM card and trick the SIM into believing that the

pair came from a legitimate operator that knows K. To prevent this attack, the

protocol includes additional checks to ensure that the same R isn’t reused.

Problems can also arise if K is compromised. For example, an attacker who com-

promises K can perform a man-in-the-middle attack and listen to all cleartext

communication. Such an attacker could send messages between the two parties

while pretending to be both the legitimate SIM card operator and the SIM card.

The greater risk is that an attacker can record communications and any messages

exchanged during the key agreement, and later decrypt those communications by

using the captured R values. An attacker could then determine the past session

keys and use them to decrypt the recorded traffic.

Attack Models for Key Agreement Protocols

There is no single definition of security for key agreement protocols, and you can

never say that a key protocol is completely secure without context and without

considering the attack model and the security goals. You can, for example, argue

that the previous 3G/4G protocol is secure because a passive attacker won’t find

the session keys, but you could also argue that it’s insecure because once the key K

leaks, then all previous and future communications are compromised.

There are different notions of security in key agreement protocols as well as three

main attack models that depend on the information the protocol leaks. From

weakest to strongest, these are the eavesdropper, the data leak, and the breach:

The eavesdropper This attacker observes the messages exchanged between the

two legitimate parties running a key agreement protocol and can record, modify,

drop, or inject messages. To protect against an eavesdropper, a key agreement

protocol must not leak any information on the shared secret established.

2 2

The data leak In this model, the attacker acquires the session key and all tempo-

rary secrets (such as SK in the telecom protocol example discussed previously)

from one or more executions of the protocol, but not the long-term secrets (like K

in that same protocol).

The breach (or corruption) In this model, the attacker learns the long-term key

of one or more of the parties. Once a breach occurs, security is no longer attain-

able because the attacker can impersonate one or both parties in subsequent ses-

sions of the protocol. Nonetheless, the attacker shouldn’t be able to recover se-

crets from sessions executed before gathering the key.

Now that we’ve looked at the attack models and seen what an attacker can do,

let’s explore the security goals—that is, the security guarantees that the protocol

should offer. A key agreement protocol can be designed to satisfy several security

goals. The four most relevant ones are described here, in order from simplest to

most sophisticated.

Authentication Each party should be able to authenticate the other party. That is,

the protocol should allow for mutual authentication. Authenticated key agreement

(AKA) occurs when a protocol authen ticates both parties.

Key control Neither party should be able to choose the final shared secret or co-

erce it to be in a specific subset. The 3G/4G key agreement protocol discussed ear-

lier lacks this property because the operator chooses the value for R that entirely

determines the final shared key.

Forward secrecy This is the assurance that even if all long-term secrets are ex-

posed, shared secrets from previous executions of the protocol won’t be able to be

computed, even if an attacker records all previous executions or is able to inject

or modify messages from previous executions. A forward-secret protocol guaran-

tees that even if you have to deliver your devices and their secrets to some au-

thority or other, they won’t be able to decrypt your prior encrypted communica-

tions. (The 3G/4G key agreement protocol doesn’t provide forward secrecy.)

Resistance to key-compromise impersonation (KCI) KCI occurs when an at-

tacker compromises a party’s long-term key and is able to use it to impersonate

another party. For example, the 3G/4G key agreement protocol allows trivial key-

compromise impersonation because both parties share the same key K. A key

agreement protocol should ideally prevent this kind of attack.

Performance

To be useful, a key agreement protocol should be not only secure but also effi-

cient. Several factors should be taken into account when considering a key agree-

ment protocol’s efficiency, including the number of messages exchanged, the

length and number of messages, the computational effort to implement the proto-

col, and whether precomputations can be made to save time. A protocol is gener-

ally more efficient if fewer, shorter messages are exchanged, and it’s best if inter-

activity is kept minimal so that neither party has to wait to receive a message be-

fore sending the next one. A common measure of a protocol’s efficiency is its du-

ration in terms of round trips, or the time it takes to send a message and receive a

response.

Round-trip time is usually the main cause of latency in protocols, but the amount

of computation to be carried out also counts; the fewer the computations required

the better, and the more precomputations that can be done in advance, the better.

For example, the 3G/4G key agreement protocol discussed earlier exchanges two

messages of a few hundred bits each, which must be sent in a certain order. Pre-

computation can be used with this protocol to save time since the operator can

pick many values of R in advance; precompute the matching values of SK, V , and

V ; and store them all in a database. In this case, precomputation has the advan-

tage of reducing the exposure of the long-term key.

Diffie–Hellman Protocols

The Diffie–Hellman function is the core of most of the deployed public-key agree-

ment protocols. However, there is no single Diffie–Hellman protocol, but rather a

variety of ways to use the DH function in order to establish a shared secret. We’ll

review three of those protocols in the sections that follow. In each discussion, I’ll

stick to the usual crypto placeholder names and call the two parties Alice and

Bob, and the attacker Eve. I’ll write g as the basis of the group used for arithmetic

operations, a value fixed and known in advance to Alice and Bob.

Anonymous Diffie–Hellman

Anonymous Diffie–Hellman is the simplest of the Diffie–Hellman protocols. It’s

called anonymous because it’s not authenticated; the participants have no identity

that can be verified by either party, and neither party holds a long-term key. Alice

can’t prove to Bob that she’s Alice, and vice versa.

In anonymous Diffie–Hellman, each party picks a random value (a for Alice and b

for Bob) to use as a private key, and sends the corresponding public key to the

other peer. Figure 11-2 shows the process in a bit more detail.

Figure 11-2: The anonymous Diffie–Hellman protocol

As you can see, Alice uses her exponent a and the group basis g to compute A = g ,

which she sends to Bob. Bob receives A and computes A , which is equal to (g ) .

Bob now obtains the value g and computes B from his random exponent b and

the value g. He then sends B to Alice and she uses it to compute g . Alice and Bob

end up with the same value, g , after performing similar operations, which in-

volve raising both g and the value received to their private exponent’s power.

Pure, simple, but only secure against the laziest of attackers.

Anonymous DH can be taken down with a man-in-the-middle attack. An eaves-

dropper simply needs to intercept messages and pretend to be Bob (to Alice) and

pretend to be Alice (to Bob), as shown in Figure 11-3.

b a b

Figure 11-3: A man-in-the-middle attack on the anonymous Diffie–Hellman protocol

As in the previous exchange, Alice and Bob pick random exponents, a and b. Alice

now computes and sends A, but Eve intercepts and drops the message. Eve then

picks a random exponent, c, and computes C = g to send to Bob. Because this pro-

tocol has no authentication, Bob believes he is receiving C from Alice and goes on

to compute g . Bob then computes B and sends that value to Alice, but Eve inter-

cepts and drops the message again. Eve now computes g , picks a new exponent,

d, computes g , computes D from g , and sends D to Alice. Alice then computes

g as well.

As a result of this attack, the attacker Eve ends up sharing a secret with Alice (g )

and another secret with Bob (g ), though Alice and Bob believe that they’re shar-

ing a single secret with each other. After completing the protocol execution, Alice

will derive symmetric keys from g in order to encrypt data sent to Bob, but Eve

will intercept the encrypted messages, decrypt them, and re-encrypt them to Bob

using another set of keys derived from g —after potentially modifying the cleart-

ext. All of this happens with Alice and Bob unaware. That is, they’re doomed.

To foil this attack, you need a way to authenticate the parties so that Alice can

prove that she’s the real Alice and Bob can prove that he’s the real Bob.

ad d

Fortunately, there is a way to do so.

Authenticated Diffie–Hellman

Authenticated Diffie–Hellman was developed to address the sort of man-in-the-

middle attacks that can affect anonymous DH. Authenticated DH equips the two

parties with both a private and a public key, thereby allowing Alice and Bob to

sign their messages in order to stop Eve from sending messages on their behalf.

Here, the signatures aren’t computed with a DH function, but a public-key signa-

ture scheme such as RSA-PSS. As a result, in order to successfully send messages

on behalf of Alice, an attacker would need to forge a valid signature, which is im-

possible with a secure signature scheme.

Figure 11-4 shows how authenticated DH works.

Figure 11-4: The authenticated Diffie–Hellman protocol

The Alice (priv , pub ) label on the first line means that Alice holds her own pri-

vate key, priv , as well as Bob’s public key, pub . This sort of priv/pub key pair is

called a long-term key because it’s fixed in advance and remains constant through

consecutive runs of the protocol. Of course, these long-term private keys should

be kept secret, while the public keys are considered to be known to an attacker.

Alice and Bob begin by picking random exponents, a and b, as in anonymous DH.

Alice then calculates A and a signature sig based on a combination of her signing

function sign, her private key priv , and A. Now Alice sends A and sig to Bob,

who verifies sig with her public key pub . If the signature is invalid, Bob knows

that the message didn’t come from Alice, and he discards A.

A B

A A

If the signature is correct, Bob will compute g from A and his random exponent

b. He would then compute B and his own signature from a combination of the

sign function, his private key priv , and B. Now he sends B and sig to Alice, who

attempts to verify sig with Bob’s public key pub . Alice will only compute g if

Bob’s signature is successfully verified.

Security Against Eavesdroppers

Authenticated DH is secure against eavesdroppers because attackers can’t learn

any bit of information on the shared secret g since they ignore the DH expo-

nents. Authenticated DH also provides forward secrecy: even if an attacker cor-

rupts any of the parties at some point, as in the breach attack model discussed

earlier, they would learn the private signing keys but not any of the ephemeral

DH exponents; hence, they’d be unable to learn the value of any previously

shared secrets.

Authenticated DH also prevents any party from controlling the value of the

shared secret. Alice can’t craft a special value of a in order to predict the value of

g because she doesn’t control b, which influences g as much as a does. (One

exception would be if Alice were to choose a = 0, in which case we’d have g = 1

for any b. But 0 isn’t an authorized value and should be rejected by the protocol.)

That said, authenticated DH isn’t secure against all types of attack. For one thing,

Eve can record previous values of A and sig and replay them later to Bob, in or-

der to pretend to be Alice. Bob will then believe that he’s sharing a secret with

Alice when he isn’t, even though Eve would not be able to learn that secret. This

risk is eliminated in practice by adding a procedure called key confirmation,

wherein Alice and Bob prove to each other that they own the shared secret. For

example, Alice and Bob may perform key confirmation by sending respectively

Hash(pub || pub , g ) and Hash(pub || pub , g ) for some hash function

Hash; when Bob receives Hash(pub || pub , g ) and Alice receives Hash(pub

|| pub , g ), both can verify the correctness of these hash values using pub ,

pub , and g . The different order of public keys (pub || pub and pub || pub )

ensures that Alice and Bob will send different values, and that an attacker can’t

pretend to be Alice by copying Bob’s hash value.

Security Against Data Leaks

B B

B B ab

ab ab

A B ab

B A ab

A B ab

A ab

B ab

A B B A

Authenticated DH’s vulnerability to data leak attackers is of greater concern. In

this type of attack, the attacker learns the value of ephemeral, short-term secrets

(namely, the exponents a and b) and uses that information to impersonate one of

the communicating parties. If Eve is able to learn the value of an exponent a

along with the matching values of A and sig sent to Bob, she could initiate a new

execution of the protocol and impersonate Alice, as shown in Figure 11-5.

Figure 11-5: An impersonation attack on the authenticated Diffie–Hellman protocol

In this attack scenario, Eve learns the value of an a and replays the corresponding

A and its signature sig , pretending to be Alice. Bob verifies the signature and

computes g from A and sends B and sig , which Eve then uses to compute g ,

using the stolen a. This results in the two having a shared secret. Bob now be-

lieves he is talking to Alice.

One way to make authenticated DH secure against the leak of ephemeral secrets is

to integrate the long-term keys into the shared secret computation so that the

shared secret can’t be determined without knowing the long-term secret.

Menezes–Qu–Vanstone (MQV)

The Menezes–Qu–Vanstone (MQV) protocol is a milestone in the history of DH-

based protocols. Designed in 1998, MQV had been approved to protect most criti-

cal assets when the NSA included it in its Suite B, a portfolio of algorithms de-

signed to protect classified information. (NSA eventually dropped MQV, allegedly

because it wasn’t used. I’ll discuss the reasons why in a bit.)

A ab

B ab

MQV is Diffie–Hellman on steroids. It’s more secure than authenticated DH, and it

improves on authenticated DH’s performance properties. In particular, MQV al-

lows users to send only two messages, independently of each other, in arbitrary

order. Other benefits are that users can send shorter messages than they would

be able to with authenticated DH, and they don’t need to send explicit signature

or verification messages. In other words, you don’t need to use a signature

scheme in addition to the Diffie–Hellman function.

As with authenticated DH, in MQV Alice and Bob each hold a long-term private

key as well as the long-term public key of the other party. The difference is that

the MQV keys aren’t signing keys: the keys used in MQV are composed of a private

exponent, x, and a public value, g . Figure 11-6 shows the operation of the MQV

protocol.

Figure 11-6: The MQV protocol

The x and y in Figure 11-6 are Alice and Bob’s respective long-term private keys,

and X and Y are their public keys. Bob and Alice start out with their own private

keys and each other’s public keys, which are g to the power of a private key. Each

chooses a random exponent, and then Alice calculates A and sends it to Bob. Bob

then calculates B and sends it to Alice. Once Alice gets Bob’s ephemeral public key

B, she combines it with her long-term private key x, her ephemeral private key a,

and Bob’s long-term public key Y by calculating the result of (B × Y ) , as de-

fined in Figure 11-6. Developing this expression, we obtain the following:

(B × Y ) = (g × (g ) ) = (g ) = g

Meanwhile, Bob calculates the result of (A × X ) , and we can verify that it’s

equal to the value calculated by Alice:

B a + xA

B a + xA b y B a + xA b + yB a + xA (b + yB)(a + xA)

A b + yB

(A × X ) = (g × (g ) ) = (g ) = g = g

As you can see, we get the same value for both Alice and Bob, namely g

. This tells us that Alice and Bob share the same secret.

Unlike authenticated DH, MQV can’t be broken by a mere leak of the ephemeral

secrets. Knowledge of a or b won’t let an attacker determine the final shared se-

cret because they would need the long-term private keys to compute it.

What happens in the strongest attack model, the breach model, where a long-term

key is compromised? If Eve compromises Alice’s long-term private key x, the pre-

viously established shared secrets are safe because their computation also in-

volved Alice’s ephemeral private keys.

However, MQV doesn’t provide perfect forward secrecy because of the following

attack. Say, for example, that Eve intercepts Alice’s A message and replaces it with

her A = g for some a that Eve has chosen. In the meantime, Bob sends B to Alice

(and Eve records B’s value) and computes the shared key. If Eve later compro-

mises Alice’s long-term private key x, she can determine the key that Bob had

computed during this session. This breaks forward secrecy, since Eve has now re-

covered the shared secret of a previous execution of the protocol. In practice,

however, the risk can be eliminated by a key-confirmation step that would have

Alice and Bob realize that they don’t share the same key, and they would there-

fore abort the protocol before deriving any session keys.

Despite its elegance and security, MQV is rarely used in practice. One reason is be-

cause it used to be encumbered by patents, which hampered its widespread adop-

tion. Another reason is that it’s harder than it looks to get MQV right in practice.

In fact, when weighed against its increased complexity, MQV’s security benefits

are often perceived as low in comparison to the simpler authenticated DH.

How Things Can Go Wrong

Diffie–Hellman protocols can fail spectacularly in a variety of ways. I highlight

some of the most common ones in the next sections.

Not Hashing the Shared Secret

A b + yB a x A b + yB a + xA b + yB (a + xA)(b + yB) (b + yB)(a + xA)

(b + yB)(a +

xA)

I’ve alluded to the fact that the shared secret that concludes a DH session ex-

change (g in our examples) is taken as input to derive session keys but is not a

key itself. And it shouldn’t be. A symmetric key should look random, and each bit

should either be 0 or 1 with the same probability. But g is not a random string;

it’s a random element within some mathematical group whose bits may be biased

toward 0 or 1. And a random group element is different from a random string of

bits.

Imagine, for example, that we’re working within the multiplicative group Z =

{1, 2, 3, . . . , 12} using g = 2 as a generator of the group, meaning that g spans all

values of Z for i in 1, 2, . . . 12: g = 2, g = 4, g = 8, g = 3, and so on. If g’s expo-

nent is random, you’ll get a random element of Z , but the encoding of a Z ele-

ment as a 4-bit string won’t be uniformly random: not all bits will have the same

probability of being a 0 or a 1. In Z , seven values have 0 as their most signifi-

cant bit (the numbers from 1 to 7 in the group), but only five have 1 as their most

significant bit (from 8 to 12). That is, this bit is 0 with probability 7 / 12 ≈ 0.58,

whereas, ideally, a random bit should be 0 with probability 0.5. Moreover, the 4-

bit sequences 1101, 1110, and 1111 will never appear.

To avoid such biases in the session keys derived from a DH shared secret, you

should use a cryptographic hash function such as BLAKE2 or SHA-3—or, better

yet, a key derivation function (KDF). An example of KDF construction is HKDF, or

HMAC-based KDF (as specified in RFC 5869), but today BLAKE2 and SHA-3 feature

dedicated modes to behave as KDFs.

Legacy Diffie–Hellman in TLS

The TLS protocol is the security behind HTTPS secure websites as well as the

Simple Mail Transfer Protocol (SMTP). TLS takes several parameters, including

the type of Diffie–Hellman protocol it will use, though most TLS implementations

still support anonymous DH for legacy reasons, despite its insecurity.

Unsafe Group Parameters

In January 2016, the maintainers of the OpenSSL toolkit fixed a high-severity vul-

nerability (CVE-2016-0701) that allowed an attacker to exploit unsafe Diffie–

Hellman parameters. The root cause of the vulnerability was that OpenSSL al-

13 *

13 * 1 2 3 4

13 *

lowed users to work with unsafe DH group parameters (namely, an unsafe prime

p) instead of throwing an error and aborting the protocol altogether before per-

forming any arithmetic operation.

Essentially, OpenSSL accepted a prime number p whose multiplicative group Z

(where all DH operations happen) contained small subgroups. As you learned at

the beginning of this chapter, the existence of small subgroups within a larger

group in a cryptographic protocol is bad because it confines shared secrets to a

much smaller set of possible values than if it were to use the whole group Z .

Worse still, an attacker can craft a DH exponent x that, when combined with the

victim’s public key g , will reveal information on the private key y and eventually

its entirety.

Although the actual vulnerability is from 2016, the principle the attack used dates

back to the 1997 paper “A Key Recovery Attack on Discrete Log-based Schemes

Using a Prime Order Subgroup” by Lim and Lee. The fix for the vulnerability is

simple: when accepting a prime p as group modulus, the protocol must check that

p is a safe prime by verifying that (p – 1) / 2 is prime as well in order to ensure

that the group Z won’t have small subgroups, and that an attack on this vulnera-

bility will fail.