Thoughts on “Oft Target” (HotPETs 17)

I just watched the, as ever provocative, presentation of Paul Syverson at HotPETs 2017, on targeting adversaries against Tor. I will just put down here some thoughts on onion routing, threat models, and security engineering loosely related to the talk.

Onion routing, as a concept, has committed an original sin, that has since its inception been haunting it: it dismisses the Global Passive Adversary as “unrealistic”, and attempts to provide anonymity properties against most limited “realistic” adversaries. This was necessary to achieve the performance and low cost required for anonymizing streams; it also seems logical enough to only protect against the actual adversaries that can be instantiated. Yet, with hint sight, it opens the door to all sorts of practical attacks, and also (importantly) theoretical confusion.

The Global Passive Adversary (GPA) is an abstraction, not a real thing. In security engineering, saying that the GPA is the adversary of a scheme means that the designers ensure that the schemes security properties hold even though all network communications are visible to the adversary. However, this is not the important practical implication. When a scheme is secure against the GPA it is also secure against any subset of network traffic, or any aspects of the network traffic — content or meta-data — being available to the adversary.

So while the GPA cannot exist, adversaries that have subsets of the GPA capability of course exist and are ubiquitous. Trivially, your ISP, your employer, an internet exchange, or the NSA, all can capture some traffic. The GPA model ensures a scheme is secure against them all. So while the GPA in its full capacity is not realistic, any subset of the GPA becomes realistic. The key question is: which subset is relevant? Different users would be concerned with different subsets; which exact subset the adversary has, is usually a well guarded secret; and assumptions about cost etc, are fragile.

A subtle implication of a scheme being secure against a GPA is that any aspect of the traffic can be seen by the adversary without compromising the anonymity system. That is not limited to actually capturing the traffic on the list, but also all partial function or views of the traffic. Paul presents a very interesting example of IRC traffic: even observing one user’s IRC traffic to a hidden IRC server, gives a very good idea of what the traffic will look like in all other links carrying the same IRC channel. In this case the adversary leverages knowledge of the structure of the IRC protocol (namely it relays chat traffic and mirrors it to all users in a channel), to build models of the network traffic that can be used to detect the channel.

This capability is taken into account when a system protects against the GPA. However, when a system like onion routing, only protects against “partial” or “local” adversaries, it is unclear what this implies about an adversary’s prior knowledge about the protocol, and indirect observations of load on far links. Such indirect observations were used in our early 2005 traffic analysis of tor paper. Fingerprinting websites is also another setting in which an an adversary does not have to “see” one side of an onion routing connection, and may simply model it and match the model using machine learning techniques.

So to conclude: the GPA does not exist, it is a super set of all adversaries users may care. But because we cannot know which is real, we chose to protect against the GPA. Furthermore, not only we do not what links or messages real adversaries can access, but we are also unsure about what other types of information they may extract from links that are not fully observed — through indirect observation, knowledge of the protocols, or modelling. Thus it is very likely that we will continue to see the slow trickle of attacks against onion routing systems as researchers discover more about capabilities or real adversaries, better side-channels to observe relevant information from far links, or better models for web or IRC traffic that require no or few observations.

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.