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.

Written on 09 December 2015.
« What I like web templating languages for
Goroutines, network IO streams, and the resulting synchronization problem »

Page tools: View Source, Add Comment.
Login: Password:
Atom Syndication: Recent Comments.

Last modified: Wed Dec 9 01:18:27 2015
This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.