4 ms·

Rollercoaster: Communicating Efficiently and Anonymously in Large Groups

48 points by yarapavan 5y ago

wolverine876 5y ago
Interesting goals ... > apps such as WhatsApp and Signal and billions of people around the world have the contents of their message protected against strong adversaries. However, while the message contents are encrypted, their metadata still leaks sensitive information AFAIK Signal already protects metadata and does group chats. What does Rollercoaster add? (I don't want to turn this into another thread about Signal. I'd hope we can focus on what Rollercoaster does.)
- woah 5y ago
  How can Signal protect metadata? If the CIA hacks Signal's servers and sees a large encrypted payload coming in from me and going out to you, they know i texted you an image even if they can't see what it is.
  - wolverine876 5y ago
    As I said, I don't want to discuss Signal. Their website explains a lot of their protocols, but they do protect metadata. I think at least one of your assumptions is wrong.
    - Ar-Curunir 5y ago
      Signal does not protect metadata cryptographically; it protects it via benevolence of the Signal server operators. Things could change any minute. Rollercoaster protects metadata cryptographically by optimizing an existing cryptographic technique called mixnets for the group setting.
    - 0des 5y ago
      Discussing Signal is somewhat unavoidable in this context though.
      - consumer451 5y ago
        > Discussing Signal is somewhat unavoidable in this context though. In which case I feel the need to share this very interesting talk from Moxie about the negatives of decentralization from the POV of product. I have no education or horse in this race, but I found this talk very interesting and dare I say brave. https://www.youtube.com/watch?v=Nj3YFprqAr8 https://www.youtube.com/watch?v=Nj3YFprqAr8 Would love to be pointed to the best counterarguments, but again the focus on product was the interesting take for me.
        MattJ100 5y ago
        > Would love to be pointed to the best counterarguments, but again the focus on product was the interesting take for me. I attempted to summarize the trade-offs in this post: https://snikket.org/blog/products-vs-protocols/ https://snikket.org/blog/products-vs-protocols/ There are also a number of responses written by others, such as: - An Objection to "The Ecosystem is Moving": https://gultsch.de/objection.html https://gultsch.de/objection.html - "Re. The Ecosystem is Moving": https://blog.jabberhead.tk/2019/12/29/re-the-ecosystem-is-moving/ https://blog.jabberhead.tk/2019/12/29/re-the-ecosystem-is-mo... - "Have you considered the alternative?" https://homebrewserver.club/have-you-considered-the-alternative.html https://homebrewserver.club/have-you-considered-the-alternat...
        wolverine876 5y ago
        > I attempted to summarize the trade-offs in this post: https://snikket.org/blog/products-vs-protocols/ https://snikket.org/blog/products-vs-protocols/ What an intelligent, honest, balanced analysis, thank you. It's hard to believe I read that on the Internet!
- alexeldeib 5y ago
  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.
- dhx 5y ago
  Rollercoaster has a decentralised traffic-analysis resistant architecture whereas Signal is centralised. With a centralised architecture such as Signal, Eve could monitor when Alice sends a message and correlate it over time to which endpoints receive a message soon thereafter. If Bob and Carol are in a group chat with Alice and they receive messages soon after Alice sends messages, Eve can assume over time that they're communicating with each other in a group chat. Due to the lack of cover traffic with Signal, the time of day, frequency and size of messages can be used to infer what they're doing or discussing. For Signal on mobile devices, the geolocation of the mobile device known from a cell tower network would also provide additional information about what Alice, Bob and Carol could be discussing. With Rollercoaster, the idea is that Eve cannot discern between different messages flowing through the network as there is no identifying data (including the size of messages which are all constant). Eve is also hampered from conducting passive timing analysis of submission and receipt of messages (even in group chats) because every node on the network is sending messages at the same rate all year round and also buffering messages and releasing them in a randomised order (not FIFO). To Eve, a message being sent by Alice could be a real message, a cover message, a real message being relayed 1min after receipt from another node or a cover message being relayed 1min after receipt from another node. With protection against Eve performing passive attacks in place, the focus moves to protecting against Eve performing active attacks including Sybil attacks (owning a considerable number of nodes in the network to try and control the entire mix net between Alice, Bob and Carol). Rollercoaster is based on Loopix[1] which includes "loop cover traffic" to detect Eve performing some forms of active attacks. The paper for an alternative mix net communication network Miranda[2] has more detail on how such mix networks can be defended against active attackers, and the numerous limitations that remain. [1] https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/piotrowska https://www.usenix.org/conference/usenixsecurity17/technical... [2] https://eprint.iacr.org/2017/1000.pdf https://eprint.iacr.org/2017/1000.pdf
  - _lambdalambda 5y ago
    Hi, paper author here :) thanks for providing a great answer to that question. I missed that the post/paper made its way to HN. One thing I'd add for the benefit of the discussion is that the term "metadata privacy" is rather fuzzy and different people mean different things with it. That's where some confusion can come from. I like to use "unobservable communication" to refer to absolute metadata privacy where no single bit of information is leaked - i.e. an adversary cannot even tell if any communication is happening at all at any point in time. For most real-world use-cases and threat models, this absolute privacy goal is often a bit unpractical because it comes with high latency or bandwidth needs. For instance, Tor is popular and practical because they prioritise latency and throughput with a careful threat model that excludes a global network adversary. However, the right threat model really depends on the individual use-case and circumstances. I think that Loopix (as linked above and what we use in our paper) does a great job in quantifying the achieved anonymity. See also https://bib.mixnetworks.org/pdf/serjantov2002towards.pdf https://bib.mixnetworks.org/pdf/serjantov2002towards.pdf for some more Information Theory in the context of Mix networks.

48 points by yarapavan 5y ago

Interesting goals ... > apps such as WhatsApp and Signal and billions of people around the world have the contents of their message protected against strong adversaries. However, while the message contents are encrypted, their metadata still leaks sensitive information AFAIK Signal already protects metadata and does group chats. What does Rollercoaster add? (I don't want to turn this into another thread about Signal. I'd hope we can focus on what Rollercoaster does.)

woah 5y ago
How can Signal protect metadata? If the CIA hacks Signal's servers and sees a large encrypted payload coming in from me and going out to you, they know i texted you an image even if they can't see what it is.
- wolverine876 5y ago
  As I said, I don't want to discuss Signal. Their website explains a lot of their protocols, but they do protect metadata. I think at least one of your assumptions is wrong.
  - Ar-Curunir 5y ago
    Signal does not protect metadata cryptographically; it protects it via benevolence of the Signal server operators. Things could change any minute. Rollercoaster protects metadata cryptographically by optimizing an existing cryptographic technique called mixnets for the group setting.
  - 0des 5y ago
    Discussing Signal is somewhat unavoidable in this context though.
    - consumer451 5y ago
      > Discussing Signal is somewhat unavoidable in this context though. In which case I feel the need to share this very interesting talk from Moxie about the negatives of decentralization from the POV of product. I have no education or horse in this race, but I found this talk very interesting and dare I say brave. https://www.youtube.com/watch?v=Nj3YFprqAr8 https://www.youtube.com/watch?v=Nj3YFprqAr8 Would love to be pointed to the best counterarguments, but again the focus on product was the interesting take for me.
      - MattJ100 5y ago
        > Would love to be pointed to the best counterarguments, but again the focus on product was the interesting take for me. I attempted to summarize the trade-offs in this post: https://snikket.org/blog/products-vs-protocols/ https://snikket.org/blog/products-vs-protocols/ There are also a number of responses written by others, such as: - An Objection to "The Ecosystem is Moving": https://gultsch.de/objection.html https://gultsch.de/objection.html - "Re. The Ecosystem is Moving": https://blog.jabberhead.tk/2019/12/29/re-the-ecosystem-is-moving/ https://blog.jabberhead.tk/2019/12/29/re-the-ecosystem-is-mo... - "Have you considered the alternative?" https://homebrewserver.club/have-you-considered-the-alternative.html https://homebrewserver.club/have-you-considered-the-alternat...
        wolverine876 5y ago
        > I attempted to summarize the trade-offs in this post: https://snikket.org/blog/products-vs-protocols/ https://snikket.org/blog/products-vs-protocols/ What an intelligent, honest, balanced analysis, thank you. It's hard to believe I read that on the Internet!
alexeldeib 5y ago
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.
dhx 5y ago
Rollercoaster has a decentralised traffic-analysis resistant architecture whereas Signal is centralised. With a centralised architecture such as Signal, Eve could monitor when Alice sends a message and correlate it over time to which endpoints receive a message soon thereafter. If Bob and Carol are in a group chat with Alice and they receive messages soon after Alice sends messages, Eve can assume over time that they're communicating with each other in a group chat. Due to the lack of cover traffic with Signal, the time of day, frequency and size of messages can be used to infer what they're doing or discussing. For Signal on mobile devices, the geolocation of the mobile device known from a cell tower network would also provide additional information about what Alice, Bob and Carol could be discussing. With Rollercoaster, the idea is that Eve cannot discern between different messages flowing through the network as there is no identifying data (including the size of messages which are all constant). Eve is also hampered from conducting passive timing analysis of submission and receipt of messages (even in group chats) because every node on the network is sending messages at the same rate all year round and also buffering messages and releasing them in a randomised order (not FIFO). To Eve, a message being sent by Alice could be a real message, a cover message, a real message being relayed 1min after receipt from another node or a cover message being relayed 1min after receipt from another node. With protection against Eve performing passive attacks in place, the focus moves to protecting against Eve performing active attacks including Sybil attacks (owning a considerable number of nodes in the network to try and control the entire mix net between Alice, Bob and Carol). Rollercoaster is based on Loopix[1] which includes "loop cover traffic" to detect Eve performing some forms of active attacks. The paper for an alternative mix net communication network Miranda[2] has more detail on how such mix networks can be defended against active attackers, and the numerous limitations that remain. [1] https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/piotrowska https://www.usenix.org/conference/usenixsecurity17/technical... [2] https://eprint.iacr.org/2017/1000.pdf https://eprint.iacr.org/2017/1000.pdf
- _lambdalambda 5y ago
  Hi, paper author here :) thanks for providing a great answer to that question. I missed that the post/paper made its way to HN. One thing I'd add for the benefit of the discussion is that the term "metadata privacy" is rather fuzzy and different people mean different things with it. That's where some confusion can come from. I like to use "unobservable communication" to refer to absolute metadata privacy where no single bit of information is leaked - i.e. an adversary cannot even tell if any communication is happening at all at any point in time. For most real-world use-cases and threat models, this absolute privacy goal is often a bit unpractical because it comes with high latency or bandwidth needs. For instance, Tor is popular and practical because they prioritise latency and throughput with a careful threat model that excludes a global network adversary. However, the right threat model really depends on the individual use-case and circumstances. I think that Loopix (as linked above and what we use in our paper) does a great job in quantifying the achieved anonymity. See also https://bib.mixnetworks.org/pdf/serjantov2002towards.pdf https://bib.mixnetworks.org/pdf/serjantov2002towards.pdf for some more Information Theory in the context of Mix networks.