Discrete-Log Algorithms#

This chapter introduces the first asymmetric-key algorithms of the course.

The distinguishing property of asymmetric-key algorithms is that instead of using standalone keys, they use key pairs. A key pair consists of a public key and a private key. The private key is known only to whoever generated it: unlike the key for a symmetric cipher, it is never known to anyone else. The public key, by contrast, can be distributed to anyone. The keys of a pair are used for opposite operations: for example, a public key to encrypt, and the corresponding private key to decrypt.

The security of any asymmetric-key algorithm comes from a one-way problem. The algorithms we’re looking at in this chapter both use the discrete-logarithm problem that we saw in the previous chapter. (In the next chapter, we’ll see an algorithm based on a different one-way problem.) The algorithms in this chapter have variants that use the elliptic-curve version of the discrete-logarithm problem; we’ll look at those too.

Roughly speaking, these algorithms randomly generate a value as a private key, and then use the easy direction of the problem (modular exponentiation, or elliptic-curve scalar multiplication) to transform that private key; the result is the public key. The keys are thus mathematically related, but thanks to the one-way problem, it’s infeasible for anyone to compute the private key from the public key.

Diffie-Hellman Key Agreement#

First, we’ll look at is Diffie-Hellman key agreement, or DH1You’ll also see Diffie-Hellman referred to as Diffie-Hellman-Merkle, or DHM. Whitfield Diffie and Martin Hellman are the authors of the paper that first described the protocol, but it was based on an idea from Ralph Merkle. It became known as Diffie-Hellman, but Hellman himself has said it should be called Diffie-Hellman-Merkle. for short[DH76]. Strictly speaking, this is not an algorithm but a protocol, because it involves multiple participants who cooperate.

The DH protocol allows two participants to compute the same number by exchanging messages in public. Anyone observing those messages cannot compute that same number. This allows the participants to create a shared secret, and thus a key for a symmetric-key cipher, without having any way to establish confidentiality beforehand.

It’s hard to overstate how significant the development of DH was in the history of cryptography, and of computing and communication in general. Since cryptography first began to be used in antiquity, it went without saying that two parties wanting to encrypt their communications had to share a secret with each other beforehand. If they didn’t have a way to communicate confidentially without cryptography (for example, by meeting in person), they had no way to start using cryptography to communicate confidentially.

Diffie-Hellman changed that. It was a paradigm shift in cryptography. Without DH, it would be impossible to use cryptography the way we do today. To load this document, your browser did a DH exchange with the web server to set up a secure connection. If DH hadn’t been invented, most Web traffic probably wouldn’t be encrypted at all. Such a world would look very different.

The Protocol#

For such an important invention, DH is amazing in its simplicity. Here are the steps:

  1. Alice and Bob agree, publicly, on a prime modulus \(p\) and a primitive root modulo \(p\), which we call \(g\). (\(g\) must be a primitive root so that all integers in the range \([1, p-1]\) are possible results of the exchange.)

  2. Alice randomly generates an integer \(a\), and Bob randomly generates an integer \(b\). These are their private keys, and they keep them secret. Both \(a\) and \(b\) must be in the range \([2, p-1]\), and they must be large enough that \(g^a > p\) and \(g^b > p\).

  3. Alice computes \(A \leftarrow g^a \Mod p\). Bob computes \(B \leftarrow g^b \Mod p\). Those values, \(A\) and \(B\), are the public keys.

  4. Alice sends \(A\) to Bob, and Bob sends \(B\) to Alice, in public.

  5. Alice computes \(B^a \Mod p\), and Bob computes \(A^b \Mod p\). These computations result in the same value, which is the output of the protocol:

    \[\begin{split} B^a \Mod p = (g^b \Mod p)^a \Mod p = g^{ab} \Mod p \\ A^b \Mod p = (g^a \Mod p)^b \Mod p = g^{ab} \Mod p \end{split}\]

    After this is done, Alice and Bob can forget the private values, \(a\) and \(b\): they aren’t needed anymore.

  6. In practice, applications will put the resulting shared number through a key derivation function before using it as a key for a symmetric cipher. One commonly-used one is called HKDF, based on HMAC[Kra10].

The security of this scheme depends on the difficulty of the discrete logarithm problem. An eavesdropper knows \(p\), \(g\), \(A\), and \(B\). However, they are unable to compute the shared result without knowing either \(a\) or \(b\). They know \(A = g^a \Mod p\), but computing \(a\) from \(A\) would require solving the discrete logarithm problem.

When we talk about the “key size” of DH, it refers to the length of \(p\) in bits. The current recommended minimum key size is 2048 bits.

Attacks#

Discrete logarithm aside, there are other ways to attack DH.

  • Man-in-the-middle. Suppose Mallory can intercept and modify Alice and Bob’s messages to each other, without being detected. Mallory could interfere with step 4 of the protocol above:

    Alice sends \(A\) to Mallory. Bob sends \(B\) to Mallory. Mallory sends \(M_1\) to Alice. Mallory sends \(M_2\) to Bob.

    Essentially, two separate instances of DH take place, each resulting in a different shared secret: one between Alice and Mallory, and one between Bob and Mallory. Mallory can then intermediate anything Alice and Bob send that’s encrypted or authenticated using those shared secrets.

    The core of the problem is that DH does not help Alice and Bob authenticate each other. Without some external means of authentication, they don’t know whether they’re talking to each other or to an attacker.

    There are several ways to solve this problem, but they all rely on Alice and Bob already having some information from each other that they trust. That could be a shared secret value, or each other’s public keys for some other algorithm.

    If they have a shared secret value2You may wonder: if Alice and Bob already have a shared secret, why would they need to run DH at all, since the whole purpose of DH is to create a shared secret? The answer is a concept called forward secrecy, which we’ll see in a later chapter., they could use it as a MAC key to authenticate the DH protocol messages. If they have each other’s public keys for a signature algorithm, they could sign the DH protocol messages. If they have each other’s public keys for authenticated variants of DH, such as MQV[LMQ+03] or STS[DVOW92], they could use those.

    There’s an obvious chicken-and-egg problem here: how are Alice and Bob supposed to already have this trusted information from each other? Presumably they want to run DH because they don’t already have a way to communicate securely, so how are they supposed to exchange this information securely?

    This is where we run up against the limitations of what technology can solve. You can verify someone’s public key in person, or by phone or video call. You can verify someone’s identity by sight, or by some kind of ID, or something else. (You may not need to be that rigorous, depending on what the purpose of the verification is.) In any case, though, there will need to be a human judgment call.

    All this is to say that DH doesn’t magically solve the key management problem altogether. It’s more accurate to say that it changes the shape of the key management problem.

  • Parameter choice. In step 1, the participants had to agree on a modulus \(p\) and primitive root \(g\), and they do so in public, communicating insecurely. There are many ways for this to go wrong.

    If \(p-1\) has only small prime factors, there is a special-purpose algorithm for solving the discrete logarithm problem modulo \(p\), called the Pohlig-Hellman algorithm. Therefore, \(p\) must be chosen so that \(p-1\) has at least one large prime factor, several hundred bits long.

    If an attacker could (e.g. by a MITM attack) get the participants to use a \(g\) that is not a primitive root modulo \(p\), the range of possible outputs of the protocol is reduced, and the discrete logarithm problem gets easier. Implementations that don’t check the properties of \(p\) and \(g\) are vulnerable to this.

    In practice, to avoid these issues, and to avoid having to find primitive roots, applications use one of a few pre-made sets of parameters. RFC 3526 specifies several of them[dh-03]. (In most of them, \(g = 2\).)

  • Precomputation. Using pre-made sets of parameters introduces a new problem of its own. The current best-known discrete logarithm algorithm is called the number field sieve. The majority of its work can be done knowing only \(g\) and \(p\); that is, without knowing the number to actually take the discrete logarithm of. There is much less work to do that actually uses the target number.

    This means that an attacker with lots of computing power can do number field sieve precomputation ahead of time, for common choices of \(g\) and \(p\). Upon intercepting a DH public key that uses one of these common choices, the attacker can quickly find its discrete logarithm, using the results of their precomputation.

    It is widely believed in the open cryptographic community3This belief comes from circumstantial evidence in the Snowden leaks of 2013. that the NSA has actually done this, and is thus able to compute discrete logarithms for common DH parameters. The defense against this is to use \(p\) of at least 2048 bits (for which this attack isn’t feasible), or to use elliptic-curve Diffie-Hellman instead (see below).

    This attack was discovered publicly in 2015, as part of an attack on TLS called Logjam[A+15b].

Static and Ephemeral#

The terms static and ephemeral Diffie-Hellman refer to the nature of the key pairs that the DH participants use. In static DH, one of the participants uses a key pair that is generated and published ahead of time, and that other participants already trust. That key pair is used repeatedly, in many runs of DH.

In ephemeral DH, by contrast, both participants generate a new key pair every time they run the protocol, and forget the key pair immediately after using it.

Static DH automatically authenticates the participant who is using the static key pair (let’s say Alice). Bob knows that he’s talking to Alice (and not a man-in-the-middle) because he already knows that the static key pair really belongs to Alice, and he trusts that only Alice has the private value. But Alice can’t be sure she’s really talking to Bob, because he generates a new key pair every time.

One way to solve that problem is for both participants to have a static key pair, shared ahead of time, and to run two separate instances of DH: one with Alice’s static and Bob’s ephemeral key pair, and one with Alice’s ephemeral and Bob’s static key pair. This will result in two different shared secrets, which can then be combined somehow (using a KDF, for example).

Elliptic-Curve Diffie-Hellman#

Elliptic-curve Diffie-Hellman, or ECDH for short, simply replaces the modular exponentiation at the heart of DH with an elliptic-curve scalar multiplication. Note that its structure is identical to plain DH:

  1. Alice and Bob agree, publicly, on an elliptic curve: the curve equation itself, as well as the modulus \(p\). They must also agree on a base point: some point on the curve, which we’ll call \(G\), and they must know the order of \(G\), which we’ll call \(n\). These values are collectively called parameters.

  2. Alice randomly generates an integer \(a\), and Bob randomly generates an integer \(b\). These numbers must be greater than zero and less than \(n\), and must be kept secret.

  3. Alice computes \(A \leftarrow a \cdot G\). Bob computes \(B \leftarrow b \cdot G\).

  4. Alice sends \(A\) to Bob, and Bob sends \(B\) to Alice, in public. The difficulty of the elliptic-curve discrete logarithm problem means that attackers cannot compute \(a\) or \(b\) from \(A\), \(B\), and \(G\).

  5. Alice computes \(a \cdot B\), and Bob computes \(b \cdot A\). These are the same point: \(a \cdot B = (a \times b) \cdot G\), and \(b \cdot A = (b \times a) \cdot G\).

  6. The shared secret, the output of ECDH, is the \(x\)-coordinate of this point that both have computed.

Like plain DH, ECDH is not authenticated, allowing for MITM attacks. However, ECDH is not known to be vulnerable to precomputation attacks like plain DH is.

Also like plain DH, the parameter choices Alice and Bob make in step 1 — the curve equation, modulus, and base point — are crucial to the security of ECDH. See the section on named curves from the previous chapter.

You may see references to X25519, which is ECDH that specifically uses Curve25519.

Digital Signature Algorithm#

Signature algorithms are a general class of algorithm that provides authentication and non-repudiation. They are asymmetric-key algorithms. A signature algorithm consists of two operations:

  • Signing, which takes as input a private key and a message to be signed. It produces a small piece of data, the signature, as output.

  • Verification, which takes as input a public key, a message, and a signature. It determines whether the signature was produced from that message and the private key corresponding to the public key.

Signatures are the asymmetric-key equivalent of MACs, which we saw in a previous chapter. Like MACs, signature algorithms must be unforgeable to be secure: it must be infeasible for a signer to produce a signature that is accepted by a verifier using a particular public key, if the signer does not know the corresponding private key. Additionally, it must be infeasible to compute a private key from a public key and signatures. The same attack models apply: known-message and chosen-message.

The main difference from MACs is that signatures provide non-repudiation: if you produce a signature with your private key, you cannot later claim that you did not produce that signature, since no one else knows your private key. MACs can’t provide non-repudiation because the verifier knows the same secret key as the signer.

Here, we’ll look at the Digital Signature Algorithm (DSA), which was published in 1991. DSA has an elliptic-curve variant that simply replaces the classical modular exponentiation with an elliptic-curve scalar multiplication.

NIST recommends that DSA no longer be used, but its elliptic-curve variant is still recommended, and very widely used.

The Algorithm#

The algorithm has four parameters, which participants must agree on beforehand. All this can be done in public.

  • \(H\), a hash function.

  • \(q\), a prime number. Its length in bits must be at least the bit length of \(H\)’s output.

  • \(p\), a prime number such that \(p-1\) is a multiple of \(q\). The “key length” of DSA refers to the length of \(p\) in bits. It should be at least 2048 bits, while \(q\) is at least 256 bits. In practice, \(q\) is randomly generated, and an appropriate \(p\) is computed from it. Note that because \(q\), a large prime, is a factor of \(p-1\), the Pohlig-Hellman algorithm can’t be used to compute discrete logarithms under the modulus \(p\).

  • \(g\), computed as \(h^{\frac{p-1}{q}} \Mod p\), where \(h\) is a randomly generated integer greater than 1 and less than \(p-1\).

To generate a key pair:

  1. Randomly generate an integer \(x\), greater than zero and less than \(q\). This is the private key.

  2. Compute \(y \leftarrow g^x \Mod p\). This is the public key.

Anyone who only knows the public key and the parameters \(g\) and \(p\) cannot compute the private key: that’s the discrete logarithm problem.

To sign a message \(m\) with private key \(x\):

  1. Randomly generate an integer \(k\), greater than zero and less than \(q\). This is called the nonce.

  2. Compute \(r \leftarrow (g^k \Mod p) \Mod q\). If \(r = 0\), start over with a different \(k\).

  3. Compute \(s \leftarrow k^{-1}(H(m) + x\cdot r) \Mod q\). If \(s = 0\), start over with a different \(k\).

    \(k^{-1}\) is the multiplicative inverse of \(k\) modulo \(q\). \(H(m)\) is the hash of the message, treated as a single number.

  4. The two numbers \((r, s)\) are the signature.

To verify a signature \((r, s)\) of a message \(m\) with public key \(y\):

  1. Check that \(0 < r < q\) and \(0 < s < q\). If either is not true, the signature is not valid.

  2. Compute \(w \leftarrow s^{-1} \Mod q\).

  3. Compute \(u_1 \leftarrow H(m) \cdot w \Mod q\).

  4. Compute \(u_2 \leftarrow r \cdot w \Mod q\).

  5. Compute \(v \leftarrow (g^{u_1}\cdot y^{u_2} \Mod p) \Mod q\).

  6. The signature is valid if and only if \(v = r\).

We’ll omit the proof of correctness here; you can find it in the NIST document that describes DSA[fip13].

The intuition behind the algorithm is as follows. Across the whole signing and verification process, the same value, \(r\), is computed twice in two different ways. First, the signer computes the value directly. Then the signer feeds \(r\) into another computation that requires both the correct message hash and the correct public key to reverse; the result of that is \(s\). Finally, the verifier uses the public key and message hash to reverse the computation that produced \(s\), extracting \(r\) from it. The verifier checks that this \(r\) matches the directly-computed \(r\) from the signer.

Attacks#

The main vulnerability of DSA is the nonce (\(k\) in the algorithm specification above). It is crucial to the security of DSA.

If the attacker knows the nonce that was used to produce a signature, they can trivially recover the private key. This means the nonce must be secret, and it must be unpredictable.

In addition, the nonce must be unique for a given private key and message. If a nonce is ever reused with a private key, this is trivial to detect, and an attacker can trivially recover the nonce, and therefore the private key.

Both of these attacks are devastating, and only require a few modular arithmetic operations that can be completed in a few milliseconds.

The mitigation for this is not to generate the nonce randomly, but rather to derive it deterministically from the message hash and private key (e.g. using an HMAC-like scheme)[det13].

Elliptic-Curve DSA#

Just as with DH and ECDH, ECDSA has exactly the same structure as plain DSA, with elliptic-curve scalar multiplication instead of modular exponentiation. Again, compare the below description with the above description of DSA.

In ECDSA, the participants must first agree on parameters: a curve and a base point \(G\) with a known order, \(n\). They must also agree on a hash function, \(H\).

Key generation is simple:

  1. Randomly generate an integer \(d\), greater than 0 and less than \(n\). This is the private key.

  2. Compute \(Q \leftarrow d \cdot G\). This is the public key.

To sign a message \(m\) with private key \(d\):

  1. Randomly generate an integer \(k\), greater than 0 and less than \(n\). This is the nonce.

  2. Compute the point \((x, y) \leftarrow k \cdot G\).

  3. Compute \(r \leftarrow x \Mod n\). If \(r = 0\), start over with a different \(k\).

  4. Compute \(s \leftarrow k^{-1}(H(m) + r\cdot d) \Mod n\). If \(s = 0\), start over with a different \(k\). (Just as in classical DSA, \(k^{-1}\) is the multiplicative inverse of \(k\) modulo \(n\), and \(H(m)\) is the hash of \(m\) treated as a single number.)

  5. The two numbers \((r, s)\) are the signature.

To verify a signature \((r, s)\) with public key \(Q\) and message \(m\):

  1. Check that \(0 < r < n\) and \(0 < s < n\). If either is not true, the signature is not valid.

  2. Compute \(w \leftarrow s^{-1} \Mod n\).

  3. Compute \(u_1 \leftarrow H(m) \cdot w \Mod n\).

  4. Compute \(u_2 \leftarrow r \cdot w \Mod n\).

  5. Compute the point \((x, y) \leftarrow (u_1 \cdot G) + (u_2 \cdot Q)\). If the point is \(O\), the point at infinity, the signature is not valid.

  6. The signature is valid if and only if \(x = r\).

Checking that \(r\) and \(s\) are not zero is crucial. If that check isn’t done, it can lead to any signature being accepted. Oracle Java was found to have this bug very recently[ora22].

Like DSA, the nonce in ECDSA is crucial to security. Knowing a nonce allows an attacker to recover the private key, and a reused nonce allows an attacker to recover that nonce.

EdDSA#

EdDSA is a signature algorithm that uses twisted Edwards curves. It is based on the elliptic-curve discrete-logarithm problem, but despite the name, its structure is not the same as ECDSA’s. We won’t go into the details here.

EdDSA is most commonly used with Curve25519; when it is, it’s called Ed25519. You may recall that Curve25519 is a Montgomery curve, not a twisted Edwards curve. There are ways to transform curve equations from one form to another, and Ed25519 uses a version of Curve25519 thusly transformed into a twisted Edwards curve.

You may also, less commonly, see Ed448, which is EdDSA with a named curve called Curve448.

Key Takeaways#

  • Diffie-Hellman key agreement allows two parties, communicating insecurely, to agree on a shared secret value that no eavesdropper can compute. Its security is based on the discrete-logarithm problem.

  • DH should not be used in new applications, but if you must use it, its key length (the length of the prime modulus) should be at least 2048 bits.

  • ECDH is DH but with elliptic-curve scalar multiplication instead of modular exponentiation. It should be used instead of plain DH if at all possible.

  • Signature algorithms use a private key to create signatures of data, so that the signatures can be verified using the corresponding public key. No one without the private key can compute a verifiable signature.

  • DSA is a signature algorithm based on the discrete-logarithm problem. It should not be used anymore.

  • ECDSA is DSA but with elliptic-curve scalar multiplication instead of modular exponentation. It is considered secure.

  • EdDSA is another signature algorithm, based on a slightly different type of curve. Ed25519 is EdDSA with Curve25519, and is a popular alternative to ECDSA.

  • All algorithms in this chapter are very sensitive to parameter selection. Only ever use named elliptic curves, and be somewhat suspicious of NIST’s named curves.