Plausible deniability and forward security (why not to use PGP)

[hickford]

Mailpile plans to secure communications with PGP:

PGP encryption and verification of emails and recipients

But PGP's security is at odds with the kind of security appropriate for casual conversation. This is discussed eloquently in the Cypherpunk's paper Why not to use PGP. (They go on to introduce a new cryptosystem with more desirable properties).

The specific problems with PGP: Suppose your key or your correspondent's key is compromised, say by carelessness, hacking, or court order. Then all your past messages can be decrypted (as well as future ones), and your signatures be verified by a third party (say a court of law).

Again, in the words of Moxie Marlinspike

And the problem is that if at any point in the future, Bob’s public key is compromised, all previous traffic is compromised as well; that someone could easily just record all the traffic, and that’s totally not unrealistic today, and then at any point try and compromise Bob’s public key and go back and decrypt all of the previous traffic. So the first thing they notice is that one key compromise affects all previous correspondence. The second thing that seems weird is that the secrecy of what I write is a function of your security practices. I mean, I feel like I’m somewhat paranoid and I have reasonable security practices, but I don’t know about the people that I am communicating with. I would like for what I write to somehow be a function of my security practices. And the third thing that they note is that the PGP model gives you authenticity, but not deniability. If I sign my email “Hey Bob, today I was thinking that Eve is a real jerk” and at some point this email is compromised and discovered, there’s no way for me to deny that I wrote this. So the nice thing is that Bob knows that I wrote it, but there’s no way for me to deny to everyone else that I wrote it – you have this ‘undeniable’ problem.

To name these problems, PGP doesn't have forward secrecy, and it doesn't have plausible deniability. To be clear, this isn't a break of PGP—it never claimed to have these properties.

It's not immediately obvious that these properties are even possible. Nevertheless, in 2004, the Cypherpunks exhibited a cryptosystem (off-the-record, or OTR) that fails gracefully:

You could say that Bob losing control of his private key was the problem. But with today’s easily-compromised personal computers, this is an all-too-likely occurence. We would really prefer to be able to handle such failures gracefully, and not simply give away the farm.

There were two main problems:

• The compromise of Bob’s secrets allowed Eve to read not only future messages protected with that key, but past messages as well.
• When Alice wanted to prove to Bob that she was the author of the message, she used a digital signature, which also proves it to Eve, and any other third party.

When we think about private messages in the context of social conversation, we really want a system with different properties: we want only Bob to be able to read the message, and Bob should be assured that Alice was the author; however, no one else should be able to do either. Further, after Alice and Bob have exchanged their message, it should be impossible for anyone (including Alice and Bob themselves) to subsequently read or verify the authenticity of the encrypted message, even if they kept a copy of it. It is clear that PGP does not provide these desirable properties.

This paper introduces a protocol for private social communication which we call “off-the-record messaging”. The notion of an off-the-record conversation well-captures the semantics one intuitively wants from private communication: only the two parties involved are privy to the contents of the conversation; after the conversation is over, no one (not even the parties involved) can produce a [cryptographically verifiable] transcript; and although the participants are assured of each other’s identities, neither they nor anyone else can prove this information to a third party. Using this protocol, Alice and Bob can enjoy the same privacy in their online conversations that they do when they speak in person.

Ok, so that explains what forward secrecy and deniability are, and why they are desirable. But are they—as I claim—necessary? And if so, why doesn't PGP have them?

To answer the second question, PGP was written a world ago. Not so much was known then! In 1991 strong cryptography was illegal in the US. The government instead pushed 'key escrow'—encryption to which would always have a backdoor. Phil Zimmerman's stated aims for PGP were to liberate cryptography and to protect the privacy of ordinary conversation from surveillance. As is apparent, the legal battle was won (for the history of how, including why the PGP source code was printed in a paper book, listen to Moxie's talk). Today, crypto underpins the online shopping history. Alas, the second aim hasn't been achieved. Almost all digital communication (text messages, emails, phone calls) remains unencrypted. Security agencies engage in total mass surveillance.

Now, why is forward security vital? Because key compromises happen. Eventual key compromise should be expected. And it might happen sooner than expected, or without you knowing.

Legal pressure

In my country, the UK, it's a criminal offence (RIPA) to refuse to surrender keys to the police. My dad and I used to send PGP encrypted messages to each other—about nothing more than family stuff. Yet at any time in the future, the police may demand my keys. If I yield, they can decrypt all the messages I ever sent. If I refuse, I can be gaoled. Had I used a forward secure protocol, I could safely reveal my private key to the police without compromising past messages (the ephemeral keys would be long lost). On my walk home, I simply announce to my friends to stop using the compromised key.

Contrary to the PGP FAQ, people in other jurisdictions are not safe. Your government may introduce a similar law in future, and use it to decrypt old messages. Your government may already introduced a similar law in secret.

Even without draconian laws, intelligence agencies are covertly pressuring providers for keys. Lavabit cracked, but responsibly informed the public and shut down.

Hacking

This is speculation (until the next Snowden reveal), but we should assume intelligence agencies are also trying to acquire secret keys by hacking. This is worse than legal pressure, because you might not detect compromise. Forward security doesn't solve the problem, but it is some protection—messages sent before the compromise remain safe.

Summary

To protect against today's threats, any cryptosystem worth its salt should be forward secure. Security agencies are recording communications en mass (eg. Prism, Tempura). Key compromises happen regularly.

There is communication software today (OTR for instant messaging http://www.cypherpunks.ca/otr/ and RedPhone for voice calls https://whispersystems.org/) that does forward secure encryption, authentication, and plausible deniability. That's the standard we want for secure communication. If it's possible for email, we should do it.

If it's not possible for email, maybe we should ditch email. The network effect makes any change hard, but it's same cost to convince your friends "let's all install pidgin-otr" as "let's all install PGP". The former is a better investment. Encrypting all your messages (and signing them) for five years with the same key—as with PGP—is shooting yourself in the foot.

---

It's worth noting Google turned on forward security for their HTTPS servers http://googleonlinesecurity.blogspot.co.uk/2011/11/protecting-data-for-long-term-with.html . I doubt this protects against the NSA--they will have specific backdoors into Google. But it remains an instructional manual for other service providers--use forward secure crypto, make the NSA go out of their way to attack you.

[tomleo]

If I understand PGP correctly then it is still an improvement over unencrypted communication. What confuses me about OTR is "after the conversation is over, no one (not even the parties involved) can produce a transcript" so does that mean I would be unable to search my email archives?

If a government wished to read my emails I belive there would be little to stop them. However if all my emails were encrypted, then even if a government had my emails, the government would still require a court order to read them (because they would need my key).

[public]

@tomleo It's an improvement in that random people who gain access to your inbox probably wont be able to read the content of your email sure. That's a pretty common threat but it doesn't do much against an attacker who's trying to gather every little bit of data they can about you for profiling purposes.

Currently there aren't any stored messaging protocols with PFS afaik. There's been some research but nothing particularly solid so far.

GPG also doesn't encrypt your mail headers so it is no defence against network and metadata analysis. This is a more solvable problem.

[hickford]

after the conversation is over, no one (not even the parties involved) can produce a transcript" so does that mean I would be unable to search my email archives

@tomleo sorry that is unclear. It doesn't mean that. You can (and typically would) save copies of messages you receive. The novel feature is the cryptographic signatures (that during the conversation convinced the parties of each other's identies and protected against man-in-the-middle attack) are worthless as they appear in the transcript. This is in contrast to PGP, where signatures remain good for years (until key compromise) and are world-verifiable (a PGP-signed message would be undeniable in a court).

How does OTR achieve deniability? In each message, it deliberately leaks the information used to sign the previous message (slight simplification). This makes it easy to fiddle transcripts. Thus, if two parties take their transcripts to court and they differ, it will be 'his-word-against-her-word'. As normal when testimonies differ, the court will decide based on circumstance and reputation. The cryptography plays no part, it has been rinsed out.

---

How to save transcripts securely on your computer or a home server is a separate (and simpler) problem. It needn't be the same crypto.

[malexmave]

@matt-hickford The big plus for PGP / GPG is that it is actually moderately in use today, compared to OTR for eMails, which would be a whole new technology.

Aside from that, there is the technical problem of OTR being (to my knowledge, correct me if I'm wrong) impossible to do asynchronously (because it is using Diffie-Hellman, which requires the parties to negotiate a key on the fly). That is fine for OTR Chat but not for eMail. And generating a key once when both parties are online and then keep using it kind of defeats the purpose of OTR.

Then there is the issue @public has already touched on: Storing the conversations. You want to be able to read your mails from a week ago, and storing them after the conversation ends implies other crypto, which again is not forward secret anymore.

Bottom line: OTR is, to my knowledge, not a good choice for eMails, and even if it were, it would only be possible to use it between mailpile users, as no one else has implemented anything in that regard yet.

But: If there should ever be a XMPP-Integration into Mailpile, as they have announced there might be, that should obviously have OTR. But that's another Issue.

[zesstra]

I guess, Mailpile could - after receiving the mail and after first decryption for the user - strip the signature, set a flag that it was originally signed by the sender, and encrypt it again without signature. Then at least it can't later be proven to third parties that the mail came from a specific sender or had this specific content.

[malexmave]

@zesstra As long as it does not happen automatically all the time without me enabling a setting for it... I like having those sigs around, and once you strip them, there is no way to know if the message is still unchanged from its original form (which is the point of deniability, but not helpful if you are not interested in deniability, but accountability, for example).

But, in general, I think that's a good idea to have as an option (gods, Mailpile is going to have so many options, we need a really good UI for that as well).

[public]

@zesstra that works against an attacker that only has access to your inbox. One that can monitor the network or can gain access to the senders mailbox can still find the signature.

IANAL but I'm not sure missing signatures would make any difference at all in most courts either.

[zesstra]

Well, yes. There is no defence against a attacker storing the communication combined with a (later) compromise of the private key. My suggestion was merely to mitigate some effects of compromised computers in the future.

Since any unsigned mail in your mailbox could easily be faked/modified by you, no court should accept the content of your inbox/mail archive as a proof that I wrote something... If they do, even OTR would of course not help at all.

[nikmit]

Very nice thread and valid points worth much consideration. There are two opposing requirements here and I don't see a way for both to be satisfied. You can either guarantee plausible deniability or be able to use emails as documents. Is it possible to have two different types of mail service? One treated as a modern day fax machine, intended for documents and accountability and a second one which is more of a asynchronous informal chat. The key here would be that these two services are clearly defined and there is no option for informal chat to be used as documents and vice versa.

[zesstra]

I just noticed this suggestion: http://www.whispersystems.org/blog/asynchronous-security "Forward Secrecy for Asynchronous Messages" Did not read it completely so far, though...

[malexmave]

The suggestion would require changes to the server architecture of the eMail Providers (having support for storing pre-generated key exchange halves), so I am quite sure that this is not going to happen with the major players.

On the other hand, if someone was to write a patch for some popular open source eMail Server, perhaps it would at least be possible for small groups of people sharing a server (or a network of compatible servers) to do this exchange.

The process on sending a message would go something like this then:

1. User A wants to send a Mail to User B
2. User A queries User B's mail Server for one stored key exchange
3. User A completes the key exchange
4. User A encrypts his message with the generated shared secret, packages up his part of the key exchange (perhaps in an eMail header?), sends it to his own Server.
5. User A's Server sends the encrypted message to User B's Server
6. User B polls the Server for new messages, receives the encrypted messasge, checks which stored key exchange was used, completes his part of the key exchange using the information from the eMail header, decrypts the message.

This may allow asynchronous forward secrecy, but still does not quite solve the problems of storing the eMails. You can...

1. Not store them (which is probably not what you want)
2. Store them unencrypted (which is probably bad)
3. Store them encrypted with your public key (which defeats the purpose of PFS using Diffie-Hellmann)

Also, this still does not solve the Problem of eMails not being Off the Record. They still are not off the record using this technique, as I understand it (correct me if I'm wrong with this).

So, the proposal would increase security, but only works with a very limited subset of eMail Servers at best.

[BjarniRunar]

Trying to make a single tool solve all problems is not going to end well.

If you want to be "off the record" and have plausible deniability and perfect forward secrecy, you use chat and OTR. If you want to be "on the record with privacy", you use OpenPGP, signed and encrypted.

This may however be the first good reason I have seen (aside from market expectations) to actually build chat into Mailpile as well as a 1st level feature. Then there can be an "on/off the record" button which transparently switches from e-mail to chat, or back again. Assuming everyone is online and there is a communication channel available, that is.

[scholarly]

In every case where you want OTR, you have to trust that the person you are talking to is not going to testify against you in court. The technology is only a part of the system: A PGP signature from your key does not in itself prove that you signed the document, nor does the lack of a signature prove that you didn't write it. And just because OTR reveals the MAC key after it's used doesn't mean that an unauthenticated transcript won't convince a jury. (Make sure your attorney understands OTR and can explain it to the jury.) This is why we have things like courts and juries and people discussing the specifics of the case to determine whether Bob or Alice is more likely to lie about the content of their messages.

[scholarly]

perhaps it would at least be possible for small groups of people sharing a server (or a network of compatible servers) to do this exchange

This is what we need. The current infrastructure was designed 30+ years ago. It does not meet today's needs. period.

We need new protocols, and we need to introduce them in a way that is semi-painless so we don't repeat the deployment problems of IPv6. If mailpile can get a big enough userbase, we can use that to drive adoption. But it will NOT be easy or quick. Gmail has a very good UI, and it will take a very big tangible benefit to get most people to switch. ("Security" doesn't sell very well among non-geeks.)

[fpietrosanti]

OpenPGP can provide forward secrecy, given proper implement and use of sub-keys: http://tools.ietf.org/html/draft-brown-pgp-pfs-03

[smari]

a) PFS (Perfect Forward Secrecy) and E-mail are inherently incompatible. The ability to read e-mails back in time and the ability to not ever have a third party be able to view your e-mail do not line up. Even with smart subkey use and such, you're going to be sacrificing one feature or the other. For the vast majority of users, history is more valuable than repudiability.

b) We're not trying to solve every problem in the world. We're just trying to make things vastly better. If somebody can come up with a guaranteed anti-rubberhosing mechanism that we can build into Mailpile that does not come at the cost of making e-mail unusable for 99% of users, then we'll consider it. Until then, let's focus on the things we can fix.

c) Don't mix metaphors. Chat is different from mail. Chat is expected to be repudiable and ephemeral. E-mail is not.

[fpietrosanti]

@smari i think that email is just an asyncronous messaging system that contain text and possible file transfer. Instant Messaging (chat) is just a syncronous messaging system that contain text and possible file transfer. In that context i really see no differences between the two, a part from the amount of time you are willing to keep an history of messages (and related files, if present).

[scholarly]

I can think of some extreme but important cases where repudiability (not PFS) could be important but chat is not a desirable option (think whistle-blower). However, I agree with @smari that Mailpile should not try to solve that problem. Very few people are willing to go to the extremes necessary to remain completely anonymous, and Mailpile will release version 1.0 in 2046 if we try to make it work for those extremes. ;-)

[mjowe]

I don't see this as a real problem. The encrypted messages are usually send over TLS-secured connections. So only you (plus your mail provider) and the recipient (plus his mail provider) have access to the encrypted messages and could later decrypt them if the key is compromised. If both host there own servers and agree to delete the messages you essentially have perfect forward secrecy.

[uktu]

Just to straighten out some of the crypto ideas that have been thrown about above: @ everyone see http://www.phrack.org/issues.html?issue=68&id=14 plausible deniability is a myth @mjowe see https://github.com/pagekite/Mailpile/issues/186#issuecomment-26209216 what TLS? @malexmave see https://whispersystems.org/blog/asynchronous-security/ for a similar protocol

[uktu]

I agree with @smari that for now, the focus is just to make things vastly better. However, @BjarniRunar made an excellent suggestion above in https://github.com/pagekite/Mailpile/issues/79#issuecomment-23158506 that could be a longer-term goal - maybe after initial release. His suggestion could transform social practices associated with data retention. By allowing transparent switching between PGP email and OTR chat, it could help make clear their differing assumptions to average users, and encourage minimal retention practices. @smari , what do you think of the proposal to eventually add transparent switching between PGP email and OTR chat?

[tildelowengrimm]

@brennannovak If this is closed, does that mean that deniability and PFS are off the table?

[smari]

@flamsmark, PFS over the wire should be handled by TLS, but this is outside the scope of Mailpile - although we could do some kind of checking for PFS on the TLS and warn users if it's missing, it seems like that'd be more confusing than helpful in real world situations. PFS for data at rest is not a goal of Mailpile, as PFS for data at rest is equivalent to not storing data, and people tend to want to be able to read their older e-mails. That is to say, Mailpile is not going to try to be Snapchat.

[BjarniRunar]

To further clarify, the chat idea is not off the table - but it is a secondary "nice to have" stretch goal. Our primary goal is to provide a secure-as-possible e-mail client for the way the majority of people actually use e-mail. In that context, PFS is indeed off the table.

[tildelowengrimm]

@smari I think your comment is talking about a different thing from the thing I think this thread is about.

When we're talking about PFS in this scenario, I think we mean

“An adversary who obtains access to an encrypted message in transit, and then later obtains access to the recipient's long-term key should not be able decrypt that message.”

If that's true, we have PFS, if not, we don't.

I don't think that this is about TLS to the MTA. Of course we should have a good, forward-secret TLS connection to the MTA. That's defense-in-depth. The PFS property I'm talking about should be true whether or not we have TLS to the MTA.

I don't think that this is about data at rest once it's in the recipient's mail store either. I understand that this is a little double-think-y, since many users' MTA is a cloud provider who they may not trust. I'd like to consider a message to be “in transit” only when it's moving from the sender's MTA to the recipient's MTA. That avoids the recipient-MTA-trust tangle.

“Messages” could be IM or email messages, but since Mailpile is a mail client first, I only want to talk about email for now.

GPG doesn't have this PFS property. Using GPG for email encryption is a totally reasonable strategy, and probably the right first one for Mailpile. That won't provide PFS for messages.

However, there are other transport encryption systems which Mailpile could opportunistically use. Open Whisper Systems' Textsecure implements a pretty compelling example of this sort of FS message-based cryptosystem. There's no reason why an FS message-based cryptosystem couldn't use GPG as an identity-certification system.

Again: I don't think that there's any reason to design or implement one of these any time soon. I think that using GPG encryption for mail is absolutely the right thing to do right now. However, I think that in the long term, moving to an FS cryptosystem would be awesome.

I think it would be great to leave an open issue for this, perhaps filed under a far-future/wishlist milestone.

[malexmave]

Related: #452

[ArneBab]

@flamsmark the openpgp pfs suggestion talks about creating a short-term encryption key (public key) and attaching that to a message. That way the receiver can reply with perfect forward secrecy (and also attach a short-term encryption key to complete the secure environment). The first message will not have perfect forward secrecy, but all subsequent messages will provide it - if both sides support PFS. If not, this will just be a default GPG exchange with an added attachment (which gets ignored by the side without PFS).

Since the messages should be signed, the sender can trust the attached short-term key. And all this can be done without any additional support by GnuPG.