4 ms·

AFAIK the signal protocol makes no guarantees about metadata. Signal the service makes claims about what they store (I.e., very little) but no properties of the

AFAIK the signal protocol makes no guarantees about metadata. Signal the service makes claims about what they store (I.e., very little) but no properties of the protocol guarantee metadata anonymity (user X communicated with user Y). At the very least I believe signal metadata is vulnerable to traffic analysis which is in scope for the threat model for some alternate systems. Vuvuzela would be something closer to providing metadata guarantees (observer cannot determine who I communicate with). Tor has some similarities. A quick Google for “metadata anonymous chat” brings up these papers, which can point you in a good direction: Small survey (vuvuzela, pung, tor) and discussion of performance/privacy trade off. https://www.mit.edu/~yossigi/metadata.pdf https://www.mit.edu/~yossigi/metadata.pdf Stadium (similar to vuvuzela, tries to optimize required cover noise): https://people.csail.mit.edu/nickolai/papers/tyagi-stadium-eprint.pdf https://people.csail.mit.edu/nickolai/papers/tyagi-stadium-e... Dissent/Riffle are also in this vein, although I haven’t seen much work on those in a few years. https://dedis.cs.yale.edu/dissent/ https://dedis.cs.yale.edu/dissent/ Rollercoaster seems to operate in this space, where computational overheard required by DC/mixnet solutions grows very large with large number of users. The novel contribution appears to be reducing that overhead without reducing guarantees provided by comparable systems.

_lambdalambda 5y ago
Hi paper author here :) thanks for the great comment. I'll add some thoughts for other potential future readers: Generally, almost every protocol that does not do some form of traffic shaping is vulnerable to traffic analysis. If an adversary just wants to confirm their suspicion that A talks to B, they can correlate the outgoing traffic patterns of A with the incoming traffic patterns of B. Doing this over a multiple rounds they can increase their confidence. This is something they can do on Signal or even between two Tor participants. Note that starting with such a suspicion is easier than finding out _who_ A is talking to. In that case they'd need to either (a) follow network messages through the network or (b) collect traffic patterns from all potential communication partners. That's why Tor is nevertheless effective in hiding which websites you visit. Thanks also for listening other anonymous network designs! There are many really interesting ones. And for some (e.g. DC nets) you can get broadcast that is only depending on the total network size and not the group size. We chose Loopix because we were looking into mobile devices. Here, Loopix has the interesting concept of provider nodes which (i) can store messages if clients are offline and (ii) regulate access to the network e.g. against a fee to make it commercially viable. Also, Mix networks are very easy to scale up by simply adding more nodes. When we tried to put decentralised collaboration (e.g. CRDTs) on top of Loopix we hit the problem that distributing the edit updates was rather inefficient. That's basically the problem from which the Rollercoaster idea developed.
- alexeldeib 5y ago
  Appreciate the reply! Definitely not my area of expertise, private communication is just something I do enjoy nerding out on :) Curious, re: traffic analysis. Were you highlighting the fact that systems which don’t deliberately try to prevent traffic analysis are generally vulnerable, or calling out a weakness in some of these systems themselves? E.g. I believe tor is susceptible to traffic analysis like you mentioned, but my understanding of some of the other solutions is that they were designed to be resilient to this in various ways, but most of those approaches involve e.g. always sending same size payloads at similar frequencies, even when there is no real payload to transmit (cover noise), and that gets expensive quickly? Or introduces high latency to maintain comparable anonymity guarantees?
  - _lambdalambda 5y ago
    It's a great topic :) and with so many interesting ideas and constructions. In my comment I was trying to make the more general statement that is (likely) impossible to achieve strong metadata privacy (or unobservable communication) without cover traffic. However, metadata privacy is a bit of a spectrum (see my other comment above). Adding latency at the relays/mixes already helps to make it harder for an adversary to correlate the traffic as their measurements get more noisy. This then very quickly gets to a level where we have "practically unobservable communication" as the signal to noise ratio is very low. By increasing/decreasing the latency of the intermediate hops one can directly control the trade-off between latency and anonymity. Check-out e.g. Figure 6 in the Loopix paper (https://www.usenix.org/system/files/conference/usenixsecurity17/sec17-piotrowska.pdf https://www.usenix.org/system/files/conference/usenixsecurit...). Similarly, this holds for cover traffic. In an ideal scenario the rate of the outgoing traffic is fully independent of whether one communicates or not. In a less ideal scenario we just add some other requests on top (e.g. a random browser bot on Tor) to create noise. In some cases this might be good enough. However, it won't satisfy any theoretical definition of unobservable communication which indicates that an observer can mitigate the noise by extending their observation over a long-long time.

_lambdalambda 5y ago

Hi paper author here :) thanks for the great comment. I'll add some thoughts for other potential future readers: Generally, almost every protocol that does not do some form of traffic shaping is vulnerable to traffic analysis. If an adversary just wants to confirm their suspicion that A talks to B, they can correlate the outgoing traffic patterns of A with the incoming traffic patterns of B. Doing this over a multiple rounds they can increase their confidence. This is something they can do on Signal or even between two Tor participants. Note that starting with such a suspicion is easier than finding out _who_ A is talking to. In that case they'd need to either (a) follow network messages through the network or (b) collect traffic patterns from all potential communication partners. That's why Tor is nevertheless effective in hiding which websites you visit. Thanks also for listening other anonymous network designs! There are many really interesting ones. And for some (e.g. DC nets) you can get broadcast that is only depending on the total network size and not the group size. We chose Loopix because we were looking into mobile devices. Here, Loopix has the interesting concept of provider nodes which (i) can store messages if clients are offline and (ii) regulate access to the network e.g. against a fee to make it commercially viable. Also, Mix networks are very easy to scale up by simply adding more nodes. When we tried to put decentralised collaboration (e.g. CRDTs) on top of Loopix we hit the problem that distributing the edit updates was rather inefficient. That's basically the problem from which the Rollercoaster idea developed.

alexeldeib 5y ago
Appreciate the reply! Definitely not my area of expertise, private communication is just something I do enjoy nerding out on :) Curious, re: traffic analysis. Were you highlighting the fact that systems which don’t deliberately try to prevent traffic analysis are generally vulnerable, or calling out a weakness in some of these systems themselves? E.g. I believe tor is susceptible to traffic analysis like you mentioned, but my understanding of some of the other solutions is that they were designed to be resilient to this in various ways, but most of those approaches involve e.g. always sending same size payloads at similar frequencies, even when there is no real payload to transmit (cover noise), and that gets expensive quickly? Or introduces high latency to maintain comparable anonymity guarantees?
- _lambdalambda 5y ago
  It's a great topic :) and with so many interesting ideas and constructions. In my comment I was trying to make the more general statement that is (likely) impossible to achieve strong metadata privacy (or unobservable communication) without cover traffic. However, metadata privacy is a bit of a spectrum (see my other comment above). Adding latency at the relays/mixes already helps to make it harder for an adversary to correlate the traffic as their measurements get more noisy. This then very quickly gets to a level where we have "practically unobservable communication" as the signal to noise ratio is very low. By increasing/decreasing the latency of the intermediate hops one can directly control the trade-off between latency and anonymity. Check-out e.g. Figure 6 in the Loopix paper (https://www.usenix.org/system/files/conference/usenixsecurity17/sec17-piotrowska.pdf https://www.usenix.org/system/files/conference/usenixsecurit...). Similarly, this holds for cover traffic. In an ideal scenario the rate of the outgoing traffic is fully independent of whether one communicates or not. In a less ideal scenario we just add some other requests on top (e.g. a random browser bot on Tor) to create noise. In some cases this might be good enough. However, it won't satisfy any theoretical definition of unobservable communication which indicates that an observer can mitigate the noise by extending their observation over a long-long time.