Chris's Wiki :: blog/tech/CryptographySignatureSurprise

A surprise about cryptographic signatures

December 9, 2015

I won't say that I know a lot about cryptography, but I know a certain amount. What this really means is that every so often I get the opportunity to be really surprised about something in cryptography. The most recent incident came about from reading Andrew Ayer's Duplicate Signature Key Selection Attack in Let's Encrypt. I had to read the article more than once before I really understood the problem, but here is the cryptographic thing that really startled me, boiled down:

A digital signature is not necessarily tied to a message.

As Ayer puts it:

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, [...]

By extension (and Ayer mentions this later), a signature does not uniquely identify a message; many pairs of messages and keys may result in the same signature. The specific vulnerability that Ayer exploited is that in RSA, if you have a message and a signature, you can quite easily generate a private key that produces the given signature for the message. The original Let's Encrypt protocol was vulnerable to this issue because it had you basically publish your signature of their validation message to you. Since this signature was on its own, an attacker could arrange a situation where it was also a valid signature for a different message signed with the attacker's key.

(The article is well worth reading in full, just to absorb the details of both how this works in RSA and how the specific attack worked against Let's Encrypt's original protocol.)

Until I read this article, I would not have expected this result at all. Had I been in a situation where it mattered, I wouldn't even have thought about the assumptions I was making about how a message, a signature, and a private key were connected; I probably would have just assumed that a signature was inextricably tied to both the message and the private key. Nope. Not so at all.

The direct lesson I take away from this is that anything involving a signature floating around on its own is dangerous, and if I ever design any sort of validation protocol I should avoid it. The indirect lesson is yet another useful reminder that I do not know enough about cryptography to be designing anything involving cryptography. If I try to do this in any non-toy context, the things I don't even know I don't know will probably eat me for breakfast without breaking a sweat.

Comments on this page:

By Durval Menezes at 2015-12-12 00:30:09:

Hello Chris,
  A digital signature is not necessarily tied to a message.
Correct. But any signed message should include (directly in the message body, if nothing else) the public key corresponding to the private key it's being signed with. A well-designed cryptosystem (like PGP/GPG) will include it in the signature itself; in PGP/GPG only the lower 64 bits of the public key -- called KeyID -- is included; I would have preferred having the full public key, but even these lower 64 bits are probably enough, as they will make the attack 2^64 times harder.

I haven't checked, but it seems that the original ACME protocol didn't include the public key in the signed message; that was what made the attack viable.

Cheers, --
  Durval.

By cks at 2015-12-12 15:12:16:

The problem exists in any situation where the signature is detached from the message, even if the message includes the public key that is supposed to be used. You might think that such situations are unusual, but a detached signature is exactly what you may have any time you say 'sign this message I'm giving you with your key to prove that you have your key'. As far as I can see without reading the old ACME protocol itself for the details, the protocol went:

register your key

ACME gives you a challenge message for a domain

you sign the challenge message and publish the signature in the DNS for the domain to prove both that you have your key and that you control the domain's DNS

An attacker exploits this by finding an existing domain with a published signature, registering with ACME, initiating a challenge for the domain, getting the message, and then finding a new key that can sign their challenge message to get the already-published signature.

At the abstract protocol level I think the only way around this attack is to include both the key and some strong random content in the challenge message. You need the key to bind the mesage to a verifier key, and you need the strong random content so that an attacker can't predict the message when they are generating their key and so pick a key that will still result in the signature.

(It's obviously a much harder attack if the key is in the message without the random content, but I believe it's still theoretically possible.)

ACME's protocol fix is to switch to publishing a completely different sort of verifier in DNS. I don't know why they didn't just change the published DNS information to also include the key hash as well as the raw signature, but presumably they had good reason to switch. (Perhaps they decided that having made one crypto mistake, they weren't going to risk another.)

Written on 09 December 2015.

«	What I like web templating languages for

Goroutines, network IO streams, and the resulting synchronization problem