Simpler secure group messaging? (PETS17)

I am at the Privacy Enhancing Technologies Symposium in Minnesota. As it is customary the conversations with other privacy researchers and developers are extremely engaging. One topic I discussed over beer with Mike Perry and Natalie Eskinazi is whether secure group messaging protocols could be simplified by relaxing some of their security and systems assumptions.

In the past I questioned whether group key agreements need to be contributory of symmetric. In this post I argue that plausible deniability properties can be relaxed, leaderlessness assumptions may be too strong, full asynchrony unnecessary, and high-scalability unlikely to make a difference. In brief, protocol designers should stop looking for the perfect protocol, with all features, and instead design a protocol that is good enough. This is controversial, so I will discuss those one by one.

Plausible deniability within a group?

Off-the-record messaging protocols, from OTR to the protocols underlying signal / whatsapp, provide cryptographic plausible deniability. In a nutshell, this means that when Alice talks to Bob, after a certain point in time Bob will not be able to prove cryptographically to any other party that Alice sent a particular message. This is technically achieved by either publishing the signature keys used after a while, or using symmetric message authentication codes to ensure Bob could have forged any authenticatior.

Before moving to the group setting it is worth thinking what plausible deniability buys you in the 2-party case: It protects Alice from an adversary, that needs cryptographic proof that she said a particular thing to Bob. However, the adversary — at the time of the conversation cannot be Bob. Bob is convinced that it is Alice that sent a message — and thus there is no need for other evidence. Similarly, if Bob is fully trusted by the adversary — for example to keep a tamper proof log of all messages sent and received and all secrets — then the defense is ineffective.

Plausible deniability protects Alice in a very narrow setting: When Alice sent a message to Bob, who at the time was honestly following the protocol, and that in the future decides to work with an adversary (that does not fully trust Bob) to convince the adversary that Alice said something. Even in the 2-party case, this is quite eclectic.

However, this property becomes even more elusive in the multi-party case. Imagine that Alice sends a message to a group of 7 participants, though a channel providing plausible deniability. At the time the message is received by 6 parties, that are all convinced that it came from Alice. For plausible deniability to be meaningful, all those parties at that time should not be adversaries. Then, down the line one or more (incl. Alice) transcripts are leaked, and the those transcripts do not contain any cryptographic authenticators for Alice.

However, for adversaries not performing legal attacks (when a court needs to be convinced of a fact) the lack of authenticators has never been a barrier to believe in a transcript of a conversation. Similarly, courts in the UK, do not rely on cryptographic authenticators to ensure authenticity: a record of a conversation, backed by an expert witness that states that it is unlikely to have been modified (through forensics) is sufficient. Furthermore, in the context of a group chat there will be multiple transcripts, all matching — unless users engaged in a very wide conspiracy to make the discussion look like something else. No software facilitates this, and without this facility, plausible deniability would provide a meaningless protection.

So my conclusion is as follow: a weak form of plausible deniability may be provided by ensuring honest parties delete authenticators (incl. signatures) once they have been checked. This ensures that honest captured devices do not contain cryptographic evidence. However, as we discussed above, dishonest parties can anyway bypass plausible deniability — and thus providing it through crypto tricks increases complexity without providing much protection.

So I advocate for the simple options of using signatures and deleting them upon reception. If your chat partners are bad, and do not delete it at this point, you are in trouble anyway.

Groups will always be small.

People want to have private conversations within groups. However, how large can these groups be until at least one of the participants or their device is compromized? The size of the group is often used in secure group chat protocols as a parameters N, and the cost of the  protocol in terms of number of messages or their size can be O(N) or O(1) or O(logN). However, this is meaningless since N will never become too big — for systems or operational security reasons.

Thus secure group chat protocols that work well for small number of users are likely to be good enough — no need to optimize in terms of N. Optimizations that reduce the constant factors are likely to be as important.

Submitting to a leader & asynchrony

Significant complexities arise in secure group chat protocols from the implicit assumption that all members of the group are equal, they talk through point-to-point messages, and that no infrastructure exists that can be trusted to anything relating to the chat. However, this is not how popular chat programs work: irc, xmpp, signal, whatsapp all rely on servers to mediate communications, and provide some services!

The most important service that can be provided by a central party is ordering: a server or a special participant can assume a “leader” role to order messages, in a total order that others will accept. They may be prevented from doing this arbitrarily: clients can include enough information to ensure that the total order imposed is compatible with causal ordering of messages (as Ximin Luo points out). However, since there is no canonical total ordering, why not rely on the ordering imposed by one of the members of the group (the leader) or a services mediating the communications.

Of course, a key challenge when relying on a leader is what happens when the leader dies or goes off line. When there is a graceful exit the leader can handover to the next leader. When there is a crash-failure things become more complex: group member need to detect the failure and replace the leader. This is complex in systems assuming high degrees of asynchrony, where there is no cut-off time out after which one can be sure another node it dead. In that case paxos or pBFT protocols need to be used to do leader election and consensus. However, if one ditches this assumption, and instead assumes that there exists a perfect failure detector — then nodes can detect failures and replace the leader.

Now, in practice users do not expect a chat session to survive the demise of the service they use (be it skype, whatsapp, or facebook). So it seems that providing such a property for secure group chat is unnecessarily complex.

Conclusion.

I would now advocate group secure messaging systems on the following lines:

• Ditch full plausible deniability; use signatures, and rely on honest parties to delete them upon checking.
• Design systems for optimal operation with group sizes of 3-50. There is no point in having much larger groups, or killing designs on the basis they do not perform when N goes to infinity.
• Rely on an infrastructure server or a leader within the group to offer consistent total ordering to all. Assume that others can detect its liveness through a timeout (synchronous), and either elect or rotate another one in. Or simply, stop the chat session once they become unavailable.

Advertisement