Cryptographic Signatures, Surprising Pitfalls, and LetsEncrypt posted March 2020

The Let's Encrypt Accident

On August 11th, 2015, Andrew Ayer posted the following email to the IETF mailing list:

I recently reviewed draft-barnes-acme-04 and found vulnerabilities in the DNS, DVSNI, and Simple HTTP challenges that would allow an attacker to fraudulently complete these challenges.

(The author has since then written a more complete explanation of the attack.)

The draft-barnes-acme-04 mentioned by Andrew Ayer is a document specifying ACME, one of the protocols behind the Let's Encrypt Certificate Authority. The thing that your browser trust and that signs the public keys of websites you visit.

The attack was found merely 6 weeks before major browsers were supposed to ship with Let's Encrypt's public keys in their trust store. The draft has since become RFC 8555: Automatic Certificate Management Environment (ACME), mitigating the issues. Since then no cryptographic attacks are known on the protocol.

But how did we get there? What's the deal with signature schemes these days? and are all of our protocols doomed? This is what this blog post will answer.

Let's Encrypt Use Of Signatures

Let's Encrypt is a pretty big deal. Created in 2014, it is a certificate authority ran as a non-profit, and currently providing trust to ~200 million of websites. (You can read my article Let's Encrypt Overview to learn more about it.)

The key to Let's Encrypt's success are two folds:

• It is free. Before Let's Encrypt most certificate authorities charged fees from webmasters who wanted to obtain certificates.
• It is automated. If you follow their standardized protocol, you can request, renew and even revoke certificates via an API. Contrast that to other certificate authorities who did most processing manually, and took time to issue certificates.

If a webmaster wants her website example.com to provide a secure connection to her users (via HTTPS), she can request a certificate from Let's Encrypt, and after proving that she owns the domain example.com and getting her certificate issued, she will be able to use it to negotiate a secure connection with any browser trusting Let's Encrypt.

That's the theory.

In practice the flow is the following:

1. Alice registers on Let's Encrypt with an RSA public key.
2. Alice asks Let's Encrypt for a certificate for example.com.
3. Let's Encrypt asks Alice to prove that she owns example.com, for this she has to sign some data and upload it to example.com/.well-known/acme-challenge/some_file.
4. Once Alice has signed and uploaded the signature, she asks Let's Encrypt to go check it.
5. Let's Encrypt checks if it can access the file on example.com, if it successfully downloaded the signature and the signature is valid then Let's Encrypt issues a certificate to Alice.

I recapitulate some of this flow in the following figure:

Now, you might be wondering, what if Alice does not own example.com and manage to man-in-the-middle Let's Encrypt in step 5? That's a real issue that's been bothering me ever since Let's Encrypt launched, and turns out a team of researchers at Princeton demonstrated exactly this in Bamboozling Certificate Authorities with BGP:

We perform the first real-world demonstration of BGP attacks to obtain bogus certificates from top CAs in an ethical manner. To assess the vulnerability of the PKI, we collect a dataset of 1.8 million certificates and find that an adversary would be capable of gaining a bogus certificate for the vast majority of domains

The paper continues and proposes two solutions to sort of remediate, or at least reduce the risk of these attacks:

Finally, we propose and evaluate two countermeasures to secure the PKI: 1) CAs verifying domains from multiple vantage points to make it harder to launch a successful attack, and 2) a BGP monitoring system for CAs to detect suspicious BGP routes and delay certificate issuance to give network operators time to react to BGP attacks.

Recently Let's Encrypt implemented the first solution multi-perspective domain validation, which changes the way step 5 of the above flow is performed: now Let's Encrypt downloads the proof from example.com from multiple places.

How Did The Let's Encrypt Attack Worked

But let's get back to what I was talking about, the attack that Andrew Ayer found in 2015.

In it, Andrew proposes a way to gain control of a Let's Encrypt account that has already validated a domain (let's say example.com)

The attack goes like this:

1. Alice registers and goes through the process of verifying her domain example.com by uploading some signature over some data on example.com/.well-known/acme-challenge/some_file. She then successfully manages to obtain a certificate from Let's Encrypt.
2. Later, Eve signs up to Let's Encrypt with a new account and new RSA public key, and request to recover the example.com domain
3. Let's Encrypt asks Eve to sign some new data, and upload it to example.com/.well-known/acme-challenge/some_file (note that the file is still lingering there from Alice's previous domain validation)
4. Eve crafts a new malicious keypair, and updates her public key on Let's Encrypt. She then asks Let's Encrypt to check the signature
5. Let's Encrypt obtains the signature file from example.com, the signature matches, Eve is granted ownership of the domain example.com.

I recapitulate the attack in the following figure:

Wait what?

What happened there?

Key Substitution Attack With RSA

In the above attack Eve managed to create a valid public key that validates a given signature and message.

This is because, as Andrew Ayer wrote:

A digital signature does not uniquely identify a key or a message

If you remember how RSA works, this is actually not too hard to understand.

For a fixed signature and (PKCS#1 v1.5 padded) message, a public key (e, N) must satisfy the following equation to validate the signature:

\(\text{signature} = \text{message}^e \pmod{N}\)

One can easily craft a public key that will (most of the time) satisfy the equation:

• \(e = 1\)
• \(N = \text{signature} - \text{message}\)

You can easily verify that the validation works:

$$ \begin{align} &\text{signature} = \text{message}^e \pmod{N}\\ \iff&\text{signature} = \text{message} \pmod{\text{signature} - \text{message}}\\ \iff&\text{signature} - \text{message} = 0 \pmod{\text{signature} - \text{message}} \end{align} $$

By definition the last line is true.

Security of Cryptographic Signatures

Is this issue surprising?

It should be.

And if so why?

This is because of the gap that exists between the theoretical world and the applied world, between the security proofs and the implemented protocol.

Signatures in cryptography are usually analyzed with the EUF-CMA model, which stands for Existential Unforgeability under Adaptive Chosen Message Attack.

In this model YOU generated a key pair, and then I request YOU to sign a number of arbitrary messages. While I observe the signatures you produce, I win if I can at some point in time produce a valid signature over a message I hadn't requested.

Unfortunately, even though our modern signature schemes seem to pass the EUF-CMA test fine, they tend to exhibit some surprising properties.

Subtle Behaviors of Signature Schemes

The excellent paper Seems Legit: Automated Analysis of Subtle Attacks on Protocols that Use Signatures by Dennis Jackson, Cas Cremers, Katriel Cohn-Gordon, and Ralf Sasse attempts to list these surprising properties and the signature schemes affected by them (and then find a bunch of these in protocols using formal verification, it's a cool paper read it).

Let me briefly describe each properties:

Conservative Exclusive Ownership (CEO)/Destructive Exclusive Ownership (DEO). This refers to what Koblitz and Menezes used to call Duplicate Signature Key Selection (DSKS). In total honesty, I don't think any of these terms are self-explanatory. I find these attacks easier to remember if thought of as the following two variants:

1. key substitution attacks (CEO), where a different keypair or public key is used to validate a given signature over a given message.
2. message key substitution attacks (DEO), where a different keypair or public key is used to validate given signature over a new message.

To recap: the first attack fixes both the message and the signature, the second one only fixes the signature.

Malleability. Most signature schemes are malleable, meaning that if you give me a valid signature I can tamper with it so that it becomes a different but still valid signature. Note that if I'm the signer I can usually create different signatures for the same message, but here malleability refers to the fact that someone who has zero knowledge of the private key can also create a new valid signature for the same signed message. It is not clear if this has any impact on any real world protocol, eventhough the bitcoin MtGox exchange blamed their loss of funds on this one. From the paper Bitcoin Transaction Malleability and MtGox:

In February 2014 MtGox, once the largest Bitcoin exchange, closed and filed for bankruptcy claiming that attackers used malleability attacks to drain its accounts.

Note that a newer security model called SUF-CMA (for strong EUF-CMA) attempts to include this behavior in the security definition of signature schemes, and some recent standards (like RFC 8032 that specifies Ed25519) are mitigating malleability attacks on their signature schemes.

Re-signability. This one is simple to explain. To validate a signature over message you often don't need the message itself but its digest. This would allow anyone to re-sign the message with their own keys without knowing the message itself. How is this impactful in real world protocols? Not sure, but we never know.

Collidability. This is another not-so-clear if it'll bite you one day: some schemes allow you to craft signatures that will validate under several messages. Worse, Ed25519 as designed allows one to craft a public key and a signature that would validate any message with high probability. (This has been fixed in some implementations like libsodium.)

I recapitulate the substitution attacks in the diagram below:

What to do with all of this information?

Well, for one signature schemes are definitely not broken, and you probably shouldn't worry if your use of them are mainstream.

But if you're designing cryptographic protocols, or if you're implementing something that's more complicated than the every day use of cryptography you might want to keep these in the back of your mind.

Did you like this content? This is part of a book about how to apply modern cryptography in real world applications. Check it out!