Absolute forward secrecy

Case scenario: Alice and Bob are emailing messages back and forth between them. They know their email is not secure, so they use encryption to preserve their privacy. Suddenly, SWAT teams break simultaneously into Alice’s and Bob’s apartments. Their respective computers are seized and they are asked at gunpoint for their encryption keys. Can their prior conversation, which has been duly recorded before the break-in, remain private?

Answer: it can, but it requires a very stringent form of secrecy, which I will call Absolute Forward Secrecy (AFS). This is one step beyond Perfect Forward Secrecy (PFS), which is touted a lot these days. In this article, I discuss the different kinds of forward secrecy, and how to obtain the absolute kind with a minimum of hassle.

Does the above scenario sound far-fetched? If it does, congratulations, you live a simple life, and good luck keeping an important matter private. If it doesn’t, this article may be for you.

Regular encryption, such as using a symmetric key, or even Pretty Good Privacy (PGP), won’t do. The moment you give your key to those gentlemen (or ladies, why not?) who kindly asked for it, they will be able to decrypt all your prior messages. Alice and Bob should have been using a package having the property of Forward Secrecy, which neither symmetric encryption algorithms nor PGP possess. Different definitions of this property are given at different places. This is the one currently on Wikipedia:

“In cryptography, forward secrecy (FS; also known as perfect forward secrecy, or PFS) is a property of key-agreement protocols ensuring that a session key derived from a set of long-term keys cannot be compromised if one of the long-term keys is compromised in the future.”

Now, simple FS and perfect PFS are not exactly the same. Here’s the difference according to forwardsecrecy.com:

“Forward Secrecy has been used as a synonym for Perfect Forward Secrecy but there is a subtle difference between the two. Perfect Forward Secrecy has the additional property that an agreed key will not be compromised even if agreed keys derived from the same long-term keying material in a subsequent run are compromised.”

For the case scenario above, there is no difference because we will assume that all the other keys that might be involved in the exchanges between Alice and Bob are random, not derived from their permanent keys. With this in mind, these are the kinds of (perfect) forward secrecy they are going to achieve:

1. No forward secrecy.
2. Delayed forward secrecy (DFS). This means that each message is not forward secret right away, but becomes so after more messages follow.
3. Instant forward secrecy (IFS). The property is acquired right away. This means that messages can be decrypted only once, even by someone who has the permanent keys and all the exchanged material.
4. Absolute forward secrecy (AFS). This is when the last message decrypted cannot be decrypted again, even if the internal state of the machines involved is known (the machines might store some secret information, which is deleted eventually, but the seizure prevented that). Observe that regular FS does not imply that the enemy has access to the machines, which may remain secure, while AFS does. For all practical purposes, an AFS message self-destructs as soon as it is read.

Now, AFS is extremely hard to achieve, especially if a server is involved. In this case, seizing the server reveals any data that might have been stored there. It doesn’t matter that it may be encrypted. Once the enemy gets Alice’s and Bob’s keys (and presumably, the server administrator’s keys as well), they can decrypt anything that has not been deleted, and likely they have not given them any time to do this.

In another article, I posit that servers are evil because they can do things that the users will never be aware of. Here we see that, even if the server remains saintly, they cannot protect the privacy of its users in the event of a forceful attack as described above.

But there is a chance if servers are not involved. This is precisely the way PassLok does it with its Read-once mode, and SeeOnce all the time. A PassLok Read-once message is encrypted with theDiffie-Hellman combination of an ephemeral private key, which is stored (encrypted) in the sender’s machine until the next message is encrypted on his side, and an ephemeral public key coming from the other side, which had been received (also encrypted) on the previous message. If strict alternation of messages is violated, messages after the first use the most recent ephemeral private key rather than the previous one.

Below is a table illustrating a conversation between Alice and Bob, using PassLok in Read-once mode. We use small case for private keys, capitals for public keys, which derive irreversibly from the matching private keys. Parentheses denote symmetric encryption using the Diffie-Hellman combination of private and public keys inside the parentheses. Numbered keys are ephemeral, unnumbered are permanent. Alice’s and Bob’s permanent public keys, A and B respectively, are public and known at the start, but no ephemeral keys have been generated yet. The users’ permanent private keys, a and b, are shown as stored to facilitate comprehension, although in fact they are never stored but entered anew by each user when they are needed. The states below are recorded after the recipient decrypts the message. “Null” means no data for a particular item.

Color code: orange=no FS, lime=delayed FS, green=instant FS, blue=absolute FS

The colors help to understand the different levels of forward secrecy. This way:

• Alice’s first message (1) has no forward secrecy because it is encrypted with the combination (a1,B) = (b,A1)—remember that the fundamental property of the Diffie-Hellman exchange is that (x,Y) = (y,X)—and b is compromised while A1 can be decrypted from the message itself as soon as either a or b are compromised.
• Bob’s first message (2) has forward secrecy because it is encrypted exclusively by ephemeral material. Even though (b1,A1) = (a1,B1), once both ephemeral private keys a1 and b1 are overwritten, there is no way to decrypt the message because none of the Diffie-Hellman combinations can be made. This does not happen right away, however. The public key B1 is encrypted with the (b,A1) = (a1,B) combination so, since a1 is not overwritten upon decrypting the message, B1 can be retrieved again, and so can the main transmitted message.
• Message number 3, which is the second one from Alice, however, becomes trivially un-decryptable as soon as it is read. It is encrypted by the result of the combination (a1,B1), which is the same used in the previous message from Bob. The difference is that Bob deletes the ephemeral key A1 and replaces it with A2 as soon as the message is successfully decrypted. Lacking A1, the software cannot reconstruct the decrypting key again. It is, however, not absolutely un-decryptable, since A1 can be obtained from message 1.
• A similar situation is found with message 4, which is the second from Bob. It needs the result of (b1,A2) = (a2,B1). Alice does no longer have B1 after reading this message once, and so there is instant forward secrecy, but an enemy with access to all the exchanges plus the date stored in both machines can still get B1 from message 2, where it is encrypted by (b,A1), and then A1 can be decrypted from message 1.
• When we get to message 5, however, the situation changes, not only is it impossible to decrypt on Bob’s end after A3 replaces A2, but we also find that reconstructing (a2,B2) = (b2,A2) has become impossible because both a2 and A2 have been overwritten on both ends. The only other place where A2 can be obtained from is message 3, but there it is encrypted by (a1,B1) = (b1,A1), and now both ephemeral private keys, a1 and b1, which were never found outside of machine storage, have ceased to exist. All messages after this one have the same Absolute Forward Secrecy.

One may ask, however, if AFS is fragile so that variations in the protocol would destroy it. Clearly a full reset, where all ephemeral keys are deleted, would send the exchange back to the state in message 1 above, so it would take 5 messages for AFS to be re-established, but how about a simple re-send? In PassLok and SeeOnce, encrypting a new message before a reply to the previous one has been decrypted puts the app in a special mode where all subsequent messages encrypted before a reply use the new ephemeral public key rather than the previous one. What happens in this case?

In the table below, Alice sends a second message 5’ right after 5. This second message is encrypted using the new key instead of the previous, as in message 2 above. Both are received and decrypted on Bob’s end, and then he replies normally in message 6.

We see that, although message 5’ only enjoys delayed FS, its reply goes back to full AFS, as well as all subsequent messages. This is because (b2,A3) = (a3,B2), and both b2 and B2 have been overwritten.B2 can be obtained from message 4, but there it is encrypted by (b1,A2) = (a2,B1), and now both a1 and b1 have been overwritten.

Alice and Bob can rest assured if they are PassLok or SeeOnce users, because not even a SWAT intervention will be able to reveal their conversation after the very first message. Perhaps there will soon be other apps out there that achieve a similar feat, but probably none that do it so simply and quickly.