Achieving PFS with public key cryptography

Question

I'm seeking to understand how Perfect Forward Secrecy (PFS) works for non SSL applications.

More specifically, I'm interested in how Moxie Marlinspike accomplishes this in TextSecure and other applications. I've heard that they use a "racheting" protocol which gives each session its own specific key which prevents a compromise of the private key of one of the users.

(e.g. A user encrypts a message to bob using bob's public key. How do I add PFS into the equation?)

How is this implemented? How would I create an application (let's say a chat application) and keep each message (or conversation) forward secret?

Answer 1

I'm seeking to understand how Perfect Forward Secrecy (PFS) works for non SSL applications.

Well, let's reiterate shortly what PFS is about: You want to prevent anyone getting your master key to be able to decrypt messages he has captured beforehand.

For example, let's assume the case of SSL/TLS where the private key of the server certificate gets compromised. Without PFS it would be then possible for an attacker to decrypt all messages that were encrypted with this key. More specifically the private key is usually used to encrypt session keys, which in return are used for the encryption of the actual data. The problem remains the same, it only adds a layer of abstraction.

How is this implemented? How would I create an application (let's say a chat application) and keep each message (or conversation) forward secret?

So, what you want is to achieve is to exchange keys in a way that the compromise of a single message doesn't break your whole system. Instead of using a static key, i.e. your private key for the key exchange of session keys, you need to come up with a scheme that is built around ephemeral keys. This is exactly what the Diffie-Hellman key exchange (DHKE) is about. The problem with classical DHKE is that the communication partners are not authenticated, so Man-in-the-middle attacks become possible.

Therefore you need to combine these two schemes: Use RSA for authentication, and use DHKE to come up with a ephemeral session keys. In such a setup neither the compromise of a single session key nor the compromise of the master key itself would allow an attacker to decrypt messages from other sessions happening before.

This works great and is basically the way how PFS is achieved in SSL/TLS. Another quite popular example for such a scheme is Off-the-Record Messaging (OTR), although key(s) have to be verified manually, rather than through a Public-key infrastructure based upon RSA.

More specifically, I'm interested in how Moxie Marlinspike accomplishes this in TextSecure and other applications.

TextSecure is essentially based on OTR. However, they improved OTR in a way to make it suitable for mobile applications. The biggest problem in a mobile environment is, that you can't expect both parties to be online at the same time. Mobile connections get interrupted all of the time, so classical DHKE would become a problem, because it could take a lot of time until both parties have agreed on a session key, which ideally would be used only for a single message. Essentially what you want is for the key exchange to be happening asynchronously. It get's a little bit more complicated than that, because TextSecure also solves a couple of other issues, like out-of-order decryption and preventing metadata to be leaked through cleartexts.

I've heard that they use a "racheting" protocol which gives each session its own specific key which prevents a compromise of the private key of one of the users.

What you are referring to is Axolotl Ratchet and you'll find a detailed description of it goals and inner workings here.

(e.g. A user encrypts a message to bob using bob's public key. How do I add PFS into the equation?)

In short: Don't use bob's public key to encrypt the message. Use his public key for authentication, come up with ephemeral keys for encryption, e.g. by using DHKE.

Answer 2

PFS usually involves ephemeral keys, i.e. keys that exist for the duration of the conversation but are thrown away later.

One way to do this is to create an ephemeral RSA keypair for the duration of the conversation:

• Alice and Bob both have long-term RSA keys, and both know each others' public keys.
• Alice generates a 768-bit RSA keypair. This is her ephemeral key. She signs the ephemeral public key with her long-term private key, and sends the information to Bob.
• Bob receives the packet, verifies its authenticity with Alice's long-term public key, then keeps a copy of Alice's ephemeral public key.
• Bob picks a random 128-bit symmetric key, encrypts it with Alice's public ephemeral key, signs it with his long-term private key, and sends it to Alice.
• Alice verifies the authenticity of the packet using Bob's public key, decrypts it with her ephemeral private key.
• Both parties now know a 128-bit key which can be used for encrypting their communications with a symmetric cipher, e.g. AES.
• At the end of the conversation, Alice discards her ephemeral private key.

Since Alice's private key is destroyed at the end of the conversation, there's no way to discover what the symmetric key was after the fact, even if either of their long-term keys are compromised.

This can also be achieved with the Diffie-Hellman key exchange algorithm in a similar way - this is where you see DHE / ECDHE in cipher suites.