Is off-the-record style encryption possible with email?

Question

The instant messaging world has off-the-record encryption - which means you get authentication, encryption, and forward deniability. Key material is published after a session ends such that an eavesdropper could forge messages, allowing deniability, even if private keys are lost.

For email, however, all we have is GPG/PGP, which offers authentication and encryption, but no forward deniability. If a private key is compromised, an adversary can prove that messages were yours. Furthermore, compromising the one private key compromises all messages sent with that key, unlike PFS implementations with HTTPS which use session keys.

Is it possible for off-the-record style encryption to function in the asynchronous multi-server environment of SMTP? Does such a protocol exist?

If not, how would a next-generation alternative to SMTP have to differ if it were to support current approaches to forward deniability and forward secrecy?

Answer 1

Simple forward deniability is easy to achieve with PGP: simply don't sign the email you send ! Anybody can send emails with arbitrary contents and alleged sender; signatures are meant specifically to cancel forward deniability.

However, if you do not sign you also lose integrity. What you would like is to be able to send an email such that:

• the recipient can be reasonably sure that the email is from who he believes the sender to be, and has not been altered in transit;
• but neither external attackers or the recipient themselves gain any proof that could be shown to third parties that the alleged sender really sent the email.

Connected protocols like instant messaging can achieve these properties by using a shared secret established with a protocol like Diffie-Hellman. When Alice and Bob share the secret K (and used authentication to establish that shared knowledge), and Bob receives a message with a correct MAC value which uses K, then Bob knows that the message comes from Alice, because only Alice and himself know K, and Bob did not send it himself. However, Bob has nothing "convincing" to show, because since he knows K, he could have forged all the messages.

With emails, there is no connection, so no semi-transient shared secret: a secret value that sender and recipient share, never stored in a file but still retained for several successive messages. However, there is a kind of "encryption-with-MAC" format in OpenPGP, section 5.13. The format is also very flexible, so one could build an OpenPGP message containing:

• a public-key encrypted session key packet which contains a random K encrypted with the recipient's public key;
• a signature packet which includes a signature computed over the previous packet (and only over that packet, not the plaintext data);
• the plaintext data, as an "encryption-with-MAC" packet.

Such an email would incarnate forward deniability with integrity: from the outside, it can be proven that the alleged sender sent at least one message, one day, to the recipient; and the recipient can show K and the proof tells that K was known to the sender too. However, nobody can demonstrate that any specific message contents were encrypted with K.

Unfortunately, though the OpenPGP format can support a lot of combinations, this is not necessarily the case of existing implementations (like GnuPG). Moreover, the "encryption-with-MAC" packet uses a cheap homemade MAC (it simply appends the SHA-1 hash of the data, and encrypts the whole lot) which does not look very secure to me. I am not aware of extensive studies of that sort-of-MAC construction, but I would not bet my last shirt on its robustness.

So you can potentially have forward deniability with authentication and integrity in PGP but only as long as the relevant software support this specific combination, which, as far as I know, they do not. Yet.

---

In cryptographic research, there is also another type of algorithm called ring signatures would could be applied to the subject: with ring signatures, the sender (Alice) computes a special type of signature involving her private key and the public key of the recipient (Bob), such that it can be proven, from the outside, that either Alice or Bob computed the signature, but which one actually did it is unknown.

There is no currently defined support for ring signatures in OpenPGP.

Answer 2

As you specifically asked for an "alternative to SMTP", you could also tackle this problem from the completely other direction.

As @Thomas Pornin so eloquently described, OTR for mails doesn't work because mail is an asynchronous form of communication while the Diffie-Hellman protocol needs both parties directly talking to each other before any encryption can be made.

If you don't want to change the way the encryption works, then you have to change the way mail works. There are two options:

1. Use a normal asynchronous email for every communication packet that needs to be send. As @Ross Dargan has said, OTR is pretty 'chatty' so several messages need to be exchanged before the real data can be send. This may take some time according to when the sender/receiver is online.
2. Only send kind of an invitation by mail, then connect directly to the receiver and continue along the normal OTR-for-IM protocol.

Both cases could be well hidden by the email client for your convenience. (Gmail already mixes chats and mails in its inbox (but without encryption).)

Both defy the original purpose of email as asynchronous communication between terminals that only are active or connected to a network for unknown and short amounts of time. But if you look at today's infrastructure, this hardly fits anymore anyway. Usually, both sender and receiver (or at least their client machines) are active and online 24/7. Even if not, the additional waiting time is only a minor cause of inconvenience.

The good news? Both versions don't rely on a changed protocol on neither SMTP nor OTR. You can easily implement all necessary changes in the clients. Happy coding!

Answer 3

It has been already mentioned but the authors of OTR provide really nice explanation in their paper:

However, there is a solution Alice can use in this case, called ring signatures. A digital signature can prove that Alice sent a message. A ring signature extends this concept and can be used to prove that, given a set of people, some member of the set sent the message, but it is impossible to determine which one. So Alice can send her message signed with a ring signature for the set {Alice,Bob} (and encrypted to Bob.) In this case, Bob will be able to verify that it indeed came from Alice (since he knows he did not send it himself), but will not be able to prove this to anyone else, since he can just as easily generate the ring signature himself. Ring signatures have been implemented as an extension to PGP.