Perfect forward secrecy in PGP with time-based ratcheting

Standard disclaimer: This is probably a bad idea in some way, and I am almost certainly not the first one to come up with it. However, I do not have any kind of training in cryptography, and so I would not know how or by whom.

Update 2021-11-09: opmsg seems like it does some of what I want with the deniable signatures, and does stateful ratcheting in a semi-interesting way. I haven’t looked into it much, but at least it clearly disproves my point that nobody is trying to innovate.

PGP is an encryption software from the 1990s. Like many other things from that time period, it has various problems and serious cryptography people do not like it. However, they do not like anything that has anything to do with e-mail, and so they are not going to invent anything better:

Encrypting email is asking for a calamity. Recommending email encryption to at-risk users is malpractice. Anyone who tells you it’s secure to communicate over PGP-encrypted email is putting their weird preferences ahead of your safety.

The logical result of this situation is that we are stuck with a terrible piece of software that nobody actually likes, because it is ugly, but that nobody wants to replace, because the replacement would also be ugly.

The root cause of the problem is that PGP is stateless. To encrypt a message to someone, I need only their public key. To sign them, I need only my private key. This is opposed to something like Signal, where I need a smart external third-party server and lots of state, or OTR, where I have to be on-line at the same time as my conversation partner and exchange keys with them and stuff.

The pros of this approach? In PGP, I can just touch and go, no need for handshakes.
The cons of this approach? In PGP, I can just touch and go, no need for handshakes.

Astute observers will notice this as a textbook example of the so-called “New Jersey style,” also known as “Worse Is Better”: it is often undesirable to go for the right thing first. It is better to get half of the right thing available so that it spreads like a virus. Once people are hooked on it, take the time to improve it to 90% of the right thing.

In PGP’s case, they neglected to do the second half, and this is where the fun starts.

Perfect forward secrecy

Let’s picture the simplest possible way to do e-mail encryption: each e-mail address has a public key associated to it. To send an e-mail to someone, you encrypt it with their public key. If you want to prove you sent it, you also sign it with your private key.

Since PGP does things in the simplest way imaginable¹, you are currently picturing PGP.

The downside of this system is that anyone who obtains their private key can decrypt the message, and anyone who has a copy of the message can see it’s signed.

Naively, this would maybe not seem like a terrible problem. We expect secret keys to remain secret. If they don’t, that is outside of the threat model. And surely the purpose of a signature is to verify who sent the message?

The devil is in the details: the secret keys are supposed to stay secret, but for how long? If someone is monitoring your e-mail and taking copies of all your (encrypted) messages, you’re deleting all your e-mails after two weeks, and your key is compromised, what happens?

1. The messages of the last two weeks are compromised
   
2. All the messages I have sent with that key, ever, are compromised
3. None of the messages are compromised

You guessed it. The answer is, of course, B.

This problem is further compounded by the lack of deniability. When the e-mails inevitably leak, there will be a cryptographic record that links the sender to his e-mail.

So, the PGP developers foresaw this problem. And being ardent adherents of simple and robust design philosophies (after all, it got them to where they are now), they applied the principle of “it is more important for the implementation to be simple than the interface”. If it causes problems when old keys are compromised, users will either have to make sure that never happens or rotate them every now and then. And so PGP was built with this assumption in mind, and users who fail to rotate their keys are outside the threat model.

In practice, what happens is people forget to rotate their keys. Even when they don’t, they’ll still keep the old ones around “for good measure”. And whenever their key gets compromised, that’s that.

So how would a good encryption system work? One that follows the “MIT style”, and writes genuinely good software, that sacrifices simplicity for correctness? Let’s take a look at a hypothetical protocol² which actually would be secure:

1. Obtain your interlocutor’s public key.
2. Send them your public key.
3. Use their public key and your private key to generate a shared secret. Because of the nature of the algorithm that is used, the shared secret will be the same whether generated with their private key and your public key, or with their public key and your private key (that’s why it’s shared and that’s why it’s secret).
4. Generate an “ephemeral” (temporary) key pair based on random data.
5. Sign its public key with a message authentication code, using the shared secret you derived in step 3. Basically, calculate signature = SHA-256(ephemeral public key || shared secret)³ and send ephemeral public key + signature over the wire.
6. Receive their signed ephemeral public key in the same way.
7. Generate a new shared secret using those two, and use this⁴ to communicate using authenticated encryption.
8. Every now and then, generate a new ephemeral keypair and throw away the old one.

The magic happens in step four. Since our master keys - the keys from step 1-2 - are only ever used for signatures, they can be totally compromised after the fact, without loss of privacy. Even if he has them, all he can do is use them to sign ephemeral keys. But he can’t go back in time and actually make us use those keys. The keys that we used to actually encrypt the material have already been discarded. In this way, we have forward secrecy: session keys will not be compromised even if long-term secrets used in the session key exchange are compromised.

Now, if PGP users did rotate their keys every three months or whatever happens to be the latest guidance, they, too, would enjoy this. The problem is that nobody ever does. For one, that would require them to change their key, which would require them to redistribute it again, and key exchange is always the weak point.

There is also another interesting property here, deniable (“repudiable”) authentication. During the conversation, all the messages are authenticated, and a third party can’t forge messages so they look like my interlocutor sent them. However, if my interlocutor is logging the conversation to leak it to the press afterwards, there’s no signatures there that actually binds me to the conversation.

How is this accomplished? Simple - messages are signed with the shared secret. During the conversation, I obviously know which messages I’m sending and which ones I amn’t. But for someone looking at the transcript afterwards, he only knows they were signed by one of the two.

Actually, it is possible to accomplish this in PGP too. First, use a separate key for signatures. Second, post its private key online after you’re done. The problem is that nobody actually does this, because it would - if nothing else - require them to do key rotation.

The proposal: deniable signatures

If I’m sending something to someone and signing it with my key, I actually already have everything I need for a deniable signature. I’ll take their public key and my private key, compute a shared secret, and then use this to compute a MAC over the whole message. If a third party then gets ahold of this MAC, one of two things will be true:

1. They do not have either private key, in which case they will not be able to verify anything.
2. They have at least one private key, in which case they can forge any signature they want.

Replacing old PGP signatures with this would actually be very easy. Since nobody checks them anyway, you could just replace them all tomorrow and nobody would notice. Whoever did want to verify signatures could just install a version of PGP with support for them. Because they’ve already bolted on so much crap, another half-baked encryption scheme would hardly even be noticed.

Another advantage of these signatures is that they would be considerably shorter. HMAC-SHA256 produces “signatures” of 32 bytes. Here’s what that would look like when encoded in base64:

-----BEGIN PGP SIGNATURE-----
47DEQpj8HBSa+/TImW+5JCeuQeRkm5NMpJWZG3hSuFU=
-----END PGP SIGNATURE-----

The downside of this is that it would require PGP users to standardize on a single public key format. Oh, the horrors!

The proposal: forward secrecy

Now, if you’re a nice protocol, there’s a simple way you can get forward secrecy. Ratcheting. Each message, you take your old key, you hash it, and now you have a new key. Because hashes are irreversible - you can’t turn the hamburger back into a cow - the compromise of the new key doesn’t lead to the compromise of the old key. That way, you have forward secrecy. (You do not have “backward secrecy”, because the old key still leads to the new key.)

This system basically resembles HOTP. You have a common counter which is synchronized, and then the HMAC over our secret key and the counter is used to generate an authentication key. The problem with this is that it isn’t stateless. For PGP-like systems, we can’t really keep a synchronized counter like that. So what can we do?

Well, there’s one thing that we still have access to, without any advanced synchronization. Time. That’s why everyone switched to the much simpler TOTP protocol instead. Instead of using a counter, it just uses your clock. As long as your clock is somewhat accurate, you can agree on the same number as the device without needing to coordinate anything.

TOTP, however, doesn’t have forward secrecy. For that, we need to look at an even older protocol, S/KEY. Here’s how S/KEY works:

1. Take your password, $W$.
2. Let $H^n(W)$ denote a hash chain $n$ times, e.g. $H^3(W) = H(H(H(W)))$ - “hash W thrice”.
3. Keep a synchronized counter between the server and the client. Initiate it at, say, $n = 1000$.
4. Store on the server $P = H^n(W)$.
5. To log in the first time, calculate $p = H^999(W)$ and send this to the server. The server checks that $H(p) = P$, i.e. that $H(H^999(W)) = H^1000(W)$. If so, the login was successful, both parties decrement W by 1, and the server replaces $P$ with the succesful $p$. Note that the server doesn’t actually know what $p$ is supposed to be in advance.
6. The next time, the client has to calculate $p = H^998(W)$ instead. Note that, even though no encryption is used, an attacker can’t glean any useful information from monitoring the connection - after it’s been used to log in once, $H^999(W)$ no longer grants you any access.

My⁵ idea, then, is that we basically do this for keys, but using the time instead of a synchronized counter. All we need is a hash function⁶ that works on keys. Ideally, it would have these properties (k is a private key and K is its corresponding public key):

0. There exists $N(k)$ such that $N(k) = K$ (e.g. $N(k) = kG = K$ for ECC), but no $f_x(K)$ such that $f_x(K) = k$.
1. There exists $f_1(k)$ such that $f_1(k_i) = f_1(k_{i+1})$
2. There exists $f_2(K)$ such that $f_2(K_i) = f_2(K_{i+1})$
3. There does not exist $f_3(k)$ such that $f_3(k_i) = f_3(k_{i-1})$
4. There does not exist $f_4(K)$ such that $f_4(K_i) = f_4(K_{i-1})$
5. $f_0(f_1(k_i)) = f_2(K_i) = K_{i+1}$

Unfortunately, I can’t find any protocols that both have properties 2 and 5.⁷ If you know one, please contact me! However, if we accept that third parties won’t be able to derive our public keys, we can steal a protocol used by Bitcoin. ⁸

That protocol is BIP32, and it tells us exactly how to do this. The specific protocol we are going to be ripping off is “hardened child key derivation”. Since I am not at all competent or licensed in this, I am just going to use it without attempting to improve or optimize it in any way.

With this knowledge in hand, we can use a private key to generate a new private key. After a certain interval, we will delete the old one. This enables us to do automatic key rotation/ratcheting, without having to keep anything synchronized with anyone.

Could this be integrated into PGP?

Theoretically, yes. You’d just do “normal” key rotation and upload the chain of signatures to a PGP server.

Would this be a panacea?

No, OTR is still better. If an old private key of ours is leaked today, that enabled an adversary to decrypt all conversations after that point. But in OTR, even if you have their key, you still have to carry out the actual MITM attack. To see why this is superior, study the following timeline:

1. 2020-01-01: Key is generated.
2. 2020-06-01: Private key is stored in some backup, somewhere.
3. 2021-06-01: Backup service hacked, private key revealed.

Under OTR, an active adversary can decrypt all communications after June 1, 2021 - the moment they got the key. Under “slightly less shitty PGP”, a passive adversary can decrypt all communications after June 1, 2020 - the age of the key that was leaked.

I am not sure what this property is called, but it seems pretty important! If you know, please leave a comment or send me an e-mail!

Since this protocol is still bad, nobody is going to make it. Mainly because it would be aesthetically unpleasing and nobody wants to work with aesthetically unpleasing software, but also because modern software can’t ship with such security flaws. Old software, like PGP, is grandfathered in, to the chagrin of expert cryptographers around the world. But only something with the rough security level, such that it is, of PGP, is simple enough to actually work for e-mail encryption.

We are thus stuck with a terrible piece of software that nobody actually likes, because it is ugly, but that nobody wants to replace, because the replacement would also be ugly.

Addendum

As a proof of concept, I wrote a Python script to actually do this key ratcheting. While it’s a mostly faithful implementation of BIP32, it has a home-rolled replacement for the chain code functionality, because implementing that properly would require a new storage format.

If that were implemented, you should be able to leak old signing keys with impunity, because there is additional material being used in the deriveation. At some point, I imagine time-lock encryption will actually become viable. With that, you would be able to rig it up to automatically leak old signing keys.

This is released into the public domain, with even less warranty than the usual “NO WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE”. Seriously, you really should not use this for anything.

Usage:

$ openssl ecparam -name secp256k1 -genkey -out sk.pem
$ ./ratchet_secp256k1.py sk.pem <itercount>
-----BEGIN EC PRIVATE KEY-----
***
-----END EC PRIVATE KEY-----