Andrew Ayer

Cryptography is notorious for its sharp edges. It's easy to make a minor mistake that totally dooms your security. The situation is improving thanks to the development of easier-to-use libraries like libsodium which provide a high-level interface instead of forcing the user to combine basic building blocks. However, you still need to know exactly what security guarantees your cryptographic primitives provide and be sure not to go beyond their guarantees.

As an example of what can go wrong when you assume too much from a primitive, consider the duplicate signature key selection attack which I discovered in ACME, the protocol used by Let's Encrypt. The vulnerability was severe and would have allowed attackers to obtain SSL certificates for domains they didn't control. Fortunately, it was mitigated before Let's Encrypt was publicly trusted, and was definitively fixed a couple weeks ago.

The vulnerability was caused by a misuse of digital signatures. The guarantee provided by digital signatures is the following:

Given a message, a signature, and a public key, a valid digital signature tells you that the message was authored by the holder of the corresponding private key.

This guarantee is handy for many use cases, such as verifying that an email is authentic. If you receive a signed email that claims to be from Bob, you can use Bob's public key to verify the signature. If an attacker, Mallory, alters the email, the signature is no longer valid. It is computationally infeasible for Mallory to compute a valid signature since she doesn't know Bob's private key.

What if Mallory could trick you into using her public key, not Bob's, to verify the message? Clearly, this would doom security. After altering the email, Mallory could replace Bob's signature with a signature from her own private key. When you verify it with Mallory's public key, the message will appear authentic.

But what if Mallory were able to alter the message and trick you into using her public key, but she was not able to replace the signature, perhaps because it was delivered out-of-band? The obvious attack, re-signing the message with her private key, won't work. So is this system secure? Is Mallory stymied?

No. Mallory just needs to find a private key which produces the same signature for her altered message as Bob's private key produced for his original message, and nothing says this can't be done. Digital signatures guarantee that a message came from a particular private key. They do not guarantee that a signature came from a particular private key, and with RSA it's quite easy to find a private key that produces a desired signature for a particular message. This means that a signature does not uniquely identify a message, which is interesting because it's easy to naively think of signatures as "hashes with public key crypto" but in this way they are very unlike hashes. Similarly, a signature alone does not identify a key, which makes digital signatures unlike handwritten signatures, which (theoretically) uniquely identify a person.

A system that gets this wrong may be vulnerable to a duplicate signature key selection attack. Let's see how this works with RSA.

Brief recap of RSA

RSA signatures work using exponentiation modulo an integer. RSA public keys consist of the modulus n (typically a 2048 bit integer that is the product of two random primes) and the public exponent e (typically 65537). Private keys consist of the same modulus n, plus the private exponent d, such that (x^d)^e = x (mod n) for all x. It's easy to calculate d from e if you know the prime factorization of n, which only the person who generated the key pair should know. Without this information, calculating d is considered infeasible.

To sign a message m, you raise it to the power of d (mod n) to produce the signature s:

s

=

md

(mod n)

To verify a message, you take the signature, raise it to the power of e (mod n), and compare it against the message:

se

≟

m

(mod n)

Since s = m^d, and (x^d)^e = x (mod n) for all x, raising s to the power of e should produce m, as long as neither the message nor the signature were altered.

Note that m has to be just the right length, so you never sign the message itself. Instead you sign a cryptographic hash of the message that has been padded using a padding scheme such as PKCS#1 v1.5 or PSS. This detail doesn't matter for understanding the attack so I will henceforth assume that the message to be signed has already been hashed and padded.

Crafting an RSA key

In a duplicate signature key selection attack, the signature s is fixed. The attacker gets to choose the message m, and then has to construct an RSA key under which s is a valid signature for m. In other words, find e, d, and n such that:

se

=

m

(mod n)

and:

(xd)e

=

x

(mod n)

for all x

There's a trivial solution which is silly but works with some RSA implementations. Just set e = 1, d = 1, and n = s - m. Clearly, the second equation is satisfied. It's not hard to see that the first equation is satisfied too:

s	=	m	(mod s - m)
s - m	=	0	(mod s - m)
0	=	0	(mod s - m)

This requires m < s, but since the first byte of PKCS#1 v1.5 padding is always zero, m < s will be true with high probability if you use PKCS#1 v1.5 padding (note that the choice of padding is controlled by the attacker; it doesn't matter what padding the victim's signature uses).

This produces a highly implausible RSA key pair. e and d are 1, which means that signing doesn't do anything, and the modulus n is less than the signature s, which shouldn't happen with modular arithmetic. However, not all RSA implementations are picky with these details. For example, Go's RSA implementation happily validates such signatures (Let's Encrypt's backend is written in Go). Note that this is in not a bug in Go, since these details don't matter when signatures are used properly.

There is a more sophisticated way to pick the RSA key that produces a valid key pair that would be accepted by all RSA implementations. Finding e such that s^e = m (mod n) is an instance of the discrete logarithm problem. Whether or not the discrete logarithm problem is difficult depends on n, which the attacker gets to choose. The attacker can choose n such that it's easy to find the corresponding e and d. Although the resulting key pair will look slightly odd to the human eye (since e is conventionally 3 or 65537), it will be a perfectly valid key pair. For more details about this technique, see page 4 of this paper by Koblitz and Menezes.

Attacking ACME

ACME is a protocol for the automated issuance of SSL certificates. It was developed for and is used by Let's Encrypt, and is currently undergoing standardization at the IETF. In ACME, messages from the client are signed using the client's ACME account key, which is typically an RSA or ECDSA key. When an ACME client asks the server to issue a certificate for a particular domain, the server replies with one or more "challenges" which the client must complete successfully to prove that it controls that domain.

One of the challenges is the DNS challenge. In an earlier draft of ACME, the client signed a "validation object" with its ACME account key, published the signature in a TXT record under the domain, and then sent the validation object and signature to the ACME server. The server would verify the signature using the client's account key and then query the TXT record. If the signature was valid, and the value of the TXT record matched the signature, the challenge would succeed. Since only the administrator of a domain can create DNS records, it was presumed that this challenge was secure.

As we saw above, such a scheme is vulnerable to a duplicate signature key selection attack. A digital signature does not uniquely identify a key or a message. So if Mallory wants to obtain a certificate for Bob's domain, she doesn't need to alter Bob's DNS records if Bob has already published his own signature in the DNS. Mallory just needs to choose her ACME account key so that her validation object has the same signature as Bob's. When Mallory sends her validation object to the ACME server, the server will query Bob's TXT record, see that Bob's signature matches the signature of Mallory's validation object, and conclude incorrectly that Mallory put the signature in Bob's DNS, and is therefore authorized to obtain certificates for Bob's domain.

For a more in-depth description of my attack, see my report to the IETF ACME list.

Resolution

Shortly after I reported the vulnerability to the IETF ACME mailing list on August 11, 2015, Let's Encrypt mitigated the attack by removing the ability to start a challenge with one account key and finish it with a different one, which deprived the attacker of the ability to pick an account key that would produce the right signature for the validation object. Since Let's Encrypt was not yet publicly trusted, at no point was the integrity of the public certificate authority system at risk from this attack. Still, the underlying misuse of signatures remained, so ACME has been redesigned so that a hash of the ACME account public key (plus a random token) is published in the DNS instead of a signature. The old challenges were disabled on November 19, 2015.

Edited (2015-12-04): Remove incorrect mention of modular inverses from my recap of RSA. Thanks to Reader Sam Edwards for pointing out my error.