7 ms·

Riffle: an efficient communication system with strong anonymity

187 points by clarkmoody 10y ago

grondilu 10y ago
> Anonymous communication is an important part of democratic societies and freedom of speech. Is it?
- vertis 10y ago
  It's easy to take for granted in an advanced democratic state, because freedom of speech is protected in one way or another. For a certain subset of societies that suppress information and views, anonymous communication becomes more important. Enabling more voices is in essence making the society more democratic (or leading towards). In addition, if you look at what's going on in Poland[1] at the moment, then you could very well argue that a popular service that can't be censored would help present a more balanced view of what is going on. From that perspective it becomes a safeguard to prevent slipping, even if things are sailing along fine at the moment. [1]: http://www.independent.co.uk/news/world/americas/barack-obama-attacks-polish-democracy-in-a-speech-polish-tv-changes-speech-a7129136.html http://www.independent.co.uk/news/world/americas/barack-obam...
  - bpchaps 10y ago
    Absolutely. Back when I first started doing FOIA requests, everything was anonymous. Not necessarily because of paranoia, but because it gave me a calm peace of mind after submitting requests. After some bogus FOIA redactions and misinterpretations, I submitted a Request for Review (RFR) to the Illinois attorney general's office who refused to continue without a signature with a valid first and last name to associate the RFR to the original FOIA request.... even though my first and last name weren't actually on any previous requests (their argument made no sense, especially with ESIGN in mind). My lawyer even told me that it would be a waste of time to fight it and to just accept it - since a lawsuit would very likely require my name anyway. Or alternatively give up on the request. Since my writing style stand out like a sore thumb, staying "anonymous" seemed pretty silly going forward, so I stopped. These days, I feel naked when submitting a request and in a lot of ways, it definitely feels like it does limit certain types of requests. If anything, my requests are a little bit more agitated - I definitely no longer have the same peace of mind as before.
  - mkesper 10y ago
    Anonymous communication might help desinformation/propaganda trolls too, though.
- jakub_h 10y ago
  Isn't it? You don't have secret ballot in your country's elections?
  - vegabook 10y ago
    that's not freedom of speech. Secret ballots are probably indispensible for democracy, but it is debatable (note I said "debatable") whether anonymity is necessary for freedom of speech and democracy. After all we've had many revolutions and regime changes in societies past where there was no anonymity of communication. Now arguably you could say that said regime changes might have occurred with less blood had anonymity been available, but then it is also arguable whether anonymous communication is anything like as forceful and persuasive as someone prepared to risk themselves by taking a public stance. IE we could argue that anonymous stances would not have created the regime change in the first place. A whole bunch of avatars screaming a slogan is not persuasive.
    - cortesoft 10y ago
      I think when people talk about the importance of anonymity in communication, they aren't talking about the people talking to each other not knowing who the person they are talking to is. What they are talking about is the ability to talk to other people without a third-party (namely the government) knowing who you are talking to. Pre-internet, this was accomplished in many ways. Secret meeting groups, anonymous newsletters, etc. With modern communication and data collection, it is much easier than ever before to know who is talking to who. If a government always knows who is talking to who, it becomes much easier to suppress detractors.
    - twr 10y ago
      John Adams' Thoughts on Government (published in 1776) seems appropriate here as an example of anonymous communication, one that helped formulate the very notion of US democracy. It was written during a revolution, too.
    - jakub_h 10y ago
      > that's not freedom of speech. I didn't say that, I was talking about the value of anonymous communication in a democracy. Surely voting is a form of communication.
- logfromblammo 10y ago
  Yes, it is. If it is possible to experience out-of-band retribution for unpopular speech traced to an identifiable individual, some minority opinions fall silent. In the US, police accountability activists may find additional civil offense summonses on the windshields of their cars--even when parked in their own driveways. That is childish and petty harassment, and the forms of retribution can be much worse. Various regulatory agencies have been used to attack political opponents, such as IRS audit rates showing a marked difference between supporters and non-supporters. EPA may demand more land use restrictions on owners with less political strength. It is very important to be able to tell other people about your grievances without fear of someone saying, "Oh yeah? If you thought that was bad, just wait 'til you see what you get for blabbing about it!"
- __jal 10y ago
  Yes[1]. If you're still not convinced, ask Publius[2]. [1] https://www.indexoncensorship.org/2014/01/five-activists-punished-governments-speaking/ https://www.indexoncensorship.org/2014/01/five-activists-pun... [2] https://en.wikipedia.org/wiki/The_Federalist_Papers https://en.wikipedia.org/wiki/The_Federalist_Papers
- DINKDINK 10y ago
  Let's assume that someone had the capability to read your thoughts without your consent. An oppressive regime would thrive with this technology: Scan everyone's brain to detect undesirables to the state. Communications between members of a group are the organizations thoughts that they have not made public yet. Should a political regime have the ability to mind read that group? If no, you should support private communication. Anonymous communications are the same thing. Pretty much all civil rights are born out of law breaking: A black and white person marrying, someone drinking beer (prohibition), people having homosexual sex. If all statements required an identity attached to them, no one would be able to anonymously campaign the merits of their ethical lawbreaking to advance social mores.
  - alphapapa 10y ago
    It's a little bit sad to me that, when we think of civil rights nowadays, the first examples that come to our minds are drinking beer and having sex. Thankfully, those that came before us had other priorities, ones which allowed us to get to the point where we can have these discussions today.
- 0xdeadbeefbabe 10y ago
  "It could be used to destroy a democracy too" -anon Edit: I'm too afraid of the downvotes to take responsibility for my speech.
swordswinger12 10y ago
If you're interested in the basic tools used in this system, this is another paper that uses some similar ones: http://arxiv.org/abs/1503.06115 http://arxiv.org/abs/1503.06115 Phil Rogaway called it 'elegant', fwiw.
robotmlg 10y ago
The name reminds me of the Solitaire cipher from Neal Stephenson's Cryptonomicon, which is calculated using a deck of playing cards: https://en.wikipedia.org/wiki/Solitaire_(cipher) https://en.wikipedia.org/wiki/Solitaire_(cipher)
- puddintane 10y ago
  Interestingly enough that is being discussed on the front page of HN right now! That is if you have not already seen this. [1] https://news.ycombinator.com/item?id=12076568 https://news.ycombinator.com/item?id=12076568
  - robotmlg 10y ago
    Yeah, I saw that and wondered if my comment was the inspiration for that post :-)
luan42 10y ago
With no real reaction after the NSA leaks and with people in various governments trying somehow to criminalize encryption and anonymity, this is exactly what we need. We don't need another centralized Google/Facebook/etc. powered application.
- Panino 10y ago
  > With no real reaction after the NSA leaks I know where you're coming from but I don't think this is the case. There are too many examples to give but here are some nice ones: In 2013, there were only a small number of E2E encrypted messenger users. Now there are over a billion Signal Protocol users alone, not even including other systems. This isn't getting deployed because it's easier to develop, support, or use than plaintext. In 2013, RC4 was widely used in TLS and random number generation (on BSD systems). It has been kicked out and now ChaCha is seeing wide deployment in the same places (although FreeBSD is lagging behind). Let's Encrypt has substantially increased TLS availability and usage. In 2013, the default crypto in OpenSSH was (IIRC) P-256 and AES-CTR, with ECDSA host keys. It's now X25519 and ChaCha20-Poly1305 with EdDSA host keys. In 2013, TLS was mostly RC4 and CBC. Now (on my servers) it's mostly GCM and ChaCha. Even the IETF has said to stop using RC4. The NaCl family, including in particular Libsodium, has a TON of users. Besides supporting only strong crypto, the high-level API has made it almost impossible to publish a successful new crypto library today that's in the style of OpenSSL where the only answer to "how to I accomplish X?" is "go fuck yourself." Good riddance to Russian roulette crypto libraries. We're even seeing movement in pqcrypto. So while some people are being reactive and switching out bad crypto for good (as in above examples), some are being proactive. Google is experimenting with pq-safe key agreement, as just one example. Tor is working on it as well. So not only has there been a positive reaction since 2013, but people are beginning to be more proactive as well, trying to stay ahead of the curve. The number of users of strong crypto has increased by several billion since 2013.
  - pdimitar 10y ago
    Paranoid response alert: This doesn't mean much, in my opinion. It might stop several thousand teams of garage hacker heroes but it's hard to argue it would stop NSA / GCHQ / anybody else on their level. With all of the leaks (good chunk of them are just theories, admittedly) that claim that agencies can utilize hardware backdoors remotely, it's hard for me to imagine I am safe from snooping, ever. What good would a stronger SSL/TLS key do if the agencies can directly connect to my CPU? What good would a strong VPN and a network like Tor do if my NIC reports my traffic via a backdoor in its driver without a chance of me ever noticing? I definitely agree some progress has been made. No two opinions about it. I do question if these countermeasures achieve anything at all against the biggest and most formidable snoopers however. I feel like they are letting us argue over things they've cracked long ago and are letting us think we're safe. Usually when public statements are made by them which try to smear/outlaw a technology, it's then I'd think the agencies are having a hard time. If they don't say anything, I'm presuming they got things well under control and where they want them to be. Not the ideal theory but all of this reply was just my thoughts anyway. If I had any facts whatsoever, I'd most likely be in a prison, so there's that. We can mostly only theorize here.
jcfrei 10y ago
link to a prototype implementation by the author: https://github.com/kwonalbert/riffle https://github.com/kwonalbert/riffle
- mirimir 10y ago
  > NOTE: This prototype implements most of what's described in the paper, but does NOT make any guarantees about security. This prototype is almost certainly full of security bugs. Please do not adapt this code to use for real anonymous communication. So I wonder if this will be updated.
mirimir 10y ago
Kwon thesis: https://dspace.mit.edu/bitstream/handle/1721.1/99859/927718269-MIT.pdf https://dspace.mit.edu/bitstream/handle/1721.1/99859/9277182... Paper: https://people.csail.mit.edu/devadas/pubs/riffle.pdf https://people.csail.mit.edu/devadas/pubs/riffle.pdf
magicfractal 10y ago
It would be nice to understand on a high level how it compares with other systems for the non-experts.
wtbob 10y ago
It's interesting, for certain, but still requires all clients to dedicate an identical amount of bandwidth (n.b.: this is very probably required for traffic-analysis-resistant anonymity): 'Moreover, each message needs to be padded to a fixed length to prevent privacy leakage through the size of the message,' (pg.23) and 'To be fully traffic analysis resistant, all users are required to upload a message, even if they do not wish to communicate that round' (pg. 25). Granted, the second sentence leaves open the possibility that perhaps all users aren't required to upload a message, at the cost of increased susceptibility to analysis, but I don't think that's really intended: worst-case, there's one client message per round, which provides no real anonymity against the client's primary server. I'm not putting it down, really: Riffle is a remarkable achievement. Sadly, it appears that anonymity is really, really hard to do truly efficiently.
- wtbob 10y ago
  Also, if I'm reading it correctly then each plaintext message from a particular client ends up at the same location within an epoch, due to the one-time shuffle at the beginning of each epoch. That might be able to reveal information about a client's activity within the epoch. I also wonder if the presence of distinguishably-mandatory plaintext messages could be used within an epoch, particularly with respect to the previous point. E.g. maybe knowing the the same client was active in rounds 1 & 2, the inactive in round 3, then active in round 4, then inactive in rounds 5 & 6, then active in rounds 7 & 8 could be used to identify the client (imagine a low-latency system, and keystroke timings or voice packet lengths).
daxorid 10y ago
Somewhat reminiscent of agl's awesome-but-defunct pond, with turn-based rather than randomized sends.
- mirimir 10y ago
  Anyone know why it's defunct, if it's so awesome?
  - sporkenfang 10y ago
    The author graduated and nobody stepped up to maintain the work. Happens to 99% of graduate student projects. The sad truth here is a lot of well maintained open source work is funded by companies who pay individuals to work and/or maintain the projects. Lots of cool ideas have no such luck.
    - mirimir 10y ago
      OK, I get it. I didn't know that he did Pond as a grad student.
indolering 10y ago
> For latency sensitive microblogging, we can support up to 10,000 users with less than one second latency with 160 byte messages. This is not a general-purpose mix network.

187 points by clarkmoody 10y ago

grondilu 10y ago

> Anonymous communication is an important part of democratic societies and freedom of speech. Is it?

vertis 10y ago
It's easy to take for granted in an advanced democratic state, because freedom of speech is protected in one way or another. For a certain subset of societies that suppress information and views, anonymous communication becomes more important. Enabling more voices is in essence making the society more democratic (or leading towards). In addition, if you look at what's going on in Poland[1] at the moment, then you could very well argue that a popular service that can't be censored would help present a more balanced view of what is going on. From that perspective it becomes a safeguard to prevent slipping, even if things are sailing along fine at the moment. [1]: http://www.independent.co.uk/news/world/americas/barack-obama-attacks-polish-democracy-in-a-speech-polish-tv-changes-speech-a7129136.html http://www.independent.co.uk/news/world/americas/barack-obam...
- bpchaps 10y ago
  Absolutely. Back when I first started doing FOIA requests, everything was anonymous. Not necessarily because of paranoia, but because it gave me a calm peace of mind after submitting requests. After some bogus FOIA redactions and misinterpretations, I submitted a Request for Review (RFR) to the Illinois attorney general's office who refused to continue without a signature with a valid first and last name to associate the RFR to the original FOIA request.... even though my first and last name weren't actually on any previous requests (their argument made no sense, especially with ESIGN in mind). My lawyer even told me that it would be a waste of time to fight it and to just accept it - since a lawsuit would very likely require my name anyway. Or alternatively give up on the request. Since my writing style stand out like a sore thumb, staying "anonymous" seemed pretty silly going forward, so I stopped. These days, I feel naked when submitting a request and in a lot of ways, it definitely feels like it does limit certain types of requests. If anything, my requests are a little bit more agitated - I definitely no longer have the same peace of mind as before.
- mkesper 10y ago
  Anonymous communication might help desinformation/propaganda trolls too, though.
jakub_h 10y ago
Isn't it? You don't have secret ballot in your country's elections?
- vegabook 10y ago
  that's not freedom of speech. Secret ballots are probably indispensible for democracy, but it is debatable (note I said "debatable") whether anonymity is necessary for freedom of speech and democracy. After all we've had many revolutions and regime changes in societies past where there was no anonymity of communication. Now arguably you could say that said regime changes might have occurred with less blood had anonymity been available, but then it is also arguable whether anonymous communication is anything like as forceful and persuasive as someone prepared to risk themselves by taking a public stance. IE we could argue that anonymous stances would not have created the regime change in the first place. A whole bunch of avatars screaming a slogan is not persuasive.
  - cortesoft 10y ago
    I think when people talk about the importance of anonymity in communication, they aren't talking about the people talking to each other not knowing who the person they are talking to is. What they are talking about is the ability to talk to other people without a third-party (namely the government) knowing who you are talking to. Pre-internet, this was accomplished in many ways. Secret meeting groups, anonymous newsletters, etc. With modern communication and data collection, it is much easier than ever before to know who is talking to who. If a government always knows who is talking to who, it becomes much easier to suppress detractors.
  - twr 10y ago
    John Adams' Thoughts on Government (published in 1776) seems appropriate here as an example of anonymous communication, one that helped formulate the very notion of US democracy. It was written during a revolution, too.
  - jakub_h 10y ago
    > that's not freedom of speech. I didn't say that, I was talking about the value of anonymous communication in a democracy. Surely voting is a form of communication.
logfromblammo 10y ago
Yes, it is. If it is possible to experience out-of-band retribution for unpopular speech traced to an identifiable individual, some minority opinions fall silent. In the US, police accountability activists may find additional civil offense summonses on the windshields of their cars--even when parked in their own driveways. That is childish and petty harassment, and the forms of retribution can be much worse. Various regulatory agencies have been used to attack political opponents, such as IRS audit rates showing a marked difference between supporters and non-supporters. EPA may demand more land use restrictions on owners with less political strength. It is very important to be able to tell other people about your grievances without fear of someone saying, "Oh yeah? If you thought that was bad, just wait 'til you see what you get for blabbing about it!"
__jal 10y ago
Yes[1]. If you're still not convinced, ask Publius[2]. [1] https://www.indexoncensorship.org/2014/01/five-activists-punished-governments-speaking/ https://www.indexoncensorship.org/2014/01/five-activists-pun... [2] https://en.wikipedia.org/wiki/The_Federalist_Papers https://en.wikipedia.org/wiki/The_Federalist_Papers
DINKDINK 10y ago
Let's assume that someone had the capability to read your thoughts without your consent. An oppressive regime would thrive with this technology: Scan everyone's brain to detect undesirables to the state. Communications between members of a group are the organizations thoughts that they have not made public yet. Should a political regime have the ability to mind read that group? If no, you should support private communication. Anonymous communications are the same thing. Pretty much all civil rights are born out of law breaking: A black and white person marrying, someone drinking beer (prohibition), people having homosexual sex. If all statements required an identity attached to them, no one would be able to anonymously campaign the merits of their ethical lawbreaking to advance social mores.
- alphapapa 10y ago
  It's a little bit sad to me that, when we think of civil rights nowadays, the first examples that come to our minds are drinking beer and having sex. Thankfully, those that came before us had other priorities, ones which allowed us to get to the point where we can have these discussions today.
0xdeadbeefbabe 10y ago
"It could be used to destroy a democracy too" -anon Edit: I'm too afraid of the downvotes to take responsibility for my speech.

swordswinger12 10y ago

If you're interested in the basic tools used in this system, this is another paper that uses some similar ones: http://arxiv.org/abs/1503.06115 http://arxiv.org/abs/1503.06115 Phil Rogaway called it 'elegant', fwiw.

robotmlg 10y ago

The name reminds me of the Solitaire cipher from Neal Stephenson's Cryptonomicon, which is calculated using a deck of playing cards: https://en.wikipedia.org/wiki/Solitaire_(cipher) https://en.wikipedia.org/wiki/Solitaire_(cipher)

puddintane 10y ago
Interestingly enough that is being discussed on the front page of HN right now! That is if you have not already seen this. [1] https://news.ycombinator.com/item?id=12076568 https://news.ycombinator.com/item?id=12076568
- robotmlg 10y ago
  Yeah, I saw that and wondered if my comment was the inspiration for that post :-)

luan42 10y ago

With no real reaction after the NSA leaks and with people in various governments trying somehow to criminalize encryption and anonymity, this is exactly what we need. We don't need another centralized Google/Facebook/etc. powered application.

Panino 10y ago
> With no real reaction after the NSA leaks I know where you're coming from but I don't think this is the case. There are too many examples to give but here are some nice ones: In 2013, there were only a small number of E2E encrypted messenger users. Now there are over a billion Signal Protocol users alone, not even including other systems. This isn't getting deployed because it's easier to develop, support, or use than plaintext. In 2013, RC4 was widely used in TLS and random number generation (on BSD systems). It has been kicked out and now ChaCha is seeing wide deployment in the same places (although FreeBSD is lagging behind). Let's Encrypt has substantially increased TLS availability and usage. In 2013, the default crypto in OpenSSH was (IIRC) P-256 and AES-CTR, with ECDSA host keys. It's now X25519 and ChaCha20-Poly1305 with EdDSA host keys. In 2013, TLS was mostly RC4 and CBC. Now (on my servers) it's mostly GCM and ChaCha. Even the IETF has said to stop using RC4. The NaCl family, including in particular Libsodium, has a TON of users. Besides supporting only strong crypto, the high-level API has made it almost impossible to publish a successful new crypto library today that's in the style of OpenSSL where the only answer to "how to I accomplish X?" is "go fuck yourself." Good riddance to Russian roulette crypto libraries. We're even seeing movement in pqcrypto. So while some people are being reactive and switching out bad crypto for good (as in above examples), some are being proactive. Google is experimenting with pq-safe key agreement, as just one example. Tor is working on it as well. So not only has there been a positive reaction since 2013, but people are beginning to be more proactive as well, trying to stay ahead of the curve. The number of users of strong crypto has increased by several billion since 2013.
- pdimitar 10y ago
  Paranoid response alert: This doesn't mean much, in my opinion. It might stop several thousand teams of garage hacker heroes but it's hard to argue it would stop NSA / GCHQ / anybody else on their level. With all of the leaks (good chunk of them are just theories, admittedly) that claim that agencies can utilize hardware backdoors remotely, it's hard for me to imagine I am safe from snooping, ever. What good would a stronger SSL/TLS key do if the agencies can directly connect to my CPU? What good would a strong VPN and a network like Tor do if my NIC reports my traffic via a backdoor in its driver without a chance of me ever noticing? I definitely agree some progress has been made. No two opinions about it. I do question if these countermeasures achieve anything at all against the biggest and most formidable snoopers however. I feel like they are letting us argue over things they've cracked long ago and are letting us think we're safe. Usually when public statements are made by them which try to smear/outlaw a technology, it's then I'd think the agencies are having a hard time. If they don't say anything, I'm presuming they got things well under control and where they want them to be. Not the ideal theory but all of this reply was just my thoughts anyway. If I had any facts whatsoever, I'd most likely be in a prison, so there's that. We can mostly only theorize here.

jcfrei 10y ago

link to a prototype implementation by the author: https://github.com/kwonalbert/riffle https://github.com/kwonalbert/riffle

mirimir 10y ago
> NOTE: This prototype implements most of what's described in the paper, but does NOT make any guarantees about security. This prototype is almost certainly full of security bugs. Please do not adapt this code to use for real anonymous communication. So I wonder if this will be updated.

mirimir 10y ago

Kwon thesis: https://dspace.mit.edu/bitstream/handle/1721.1/99859/927718269-MIT.pdf https://dspace.mit.edu/bitstream/handle/1721.1/99859/9277182... Paper: https://people.csail.mit.edu/devadas/pubs/riffle.pdf https://people.csail.mit.edu/devadas/pubs/riffle.pdf

magicfractal 10y ago

It would be nice to understand on a high level how it compares with other systems for the non-experts.

wtbob 10y ago

It's interesting, for certain, but still requires all clients to dedicate an identical amount of bandwidth (n.b.: this is very probably required for traffic-analysis-resistant anonymity): 'Moreover, each message needs to be padded to a fixed length to prevent privacy leakage through the size of the message,' (pg.23) and 'To be fully traffic analysis resistant, all users are required to upload a message, even if they do not wish to communicate that round' (pg. 25). Granted, the second sentence leaves open the possibility that perhaps all users aren't required to upload a message, at the cost of increased susceptibility to analysis, but I don't think that's really intended: worst-case, there's one client message per round, which provides no real anonymity against the client's primary server. I'm not putting it down, really: Riffle is a remarkable achievement. Sadly, it appears that anonymity is really, really hard to do truly efficiently.

wtbob 10y ago
Also, if I'm reading it correctly then each plaintext message from a particular client ends up at the same location within an epoch, due to the one-time shuffle at the beginning of each epoch. That might be able to reveal information about a client's activity within the epoch. I also wonder if the presence of distinguishably-mandatory plaintext messages could be used within an epoch, particularly with respect to the previous point. E.g. maybe knowing the the same client was active in rounds 1 & 2, the inactive in round 3, then active in round 4, then inactive in rounds 5 & 6, then active in rounds 7 & 8 could be used to identify the client (imagine a low-latency system, and keystroke timings or voice packet lengths).

daxorid 10y ago

Somewhat reminiscent of agl's awesome-but-defunct pond, with turn-based rather than randomized sends.

mirimir 10y ago
Anyone know why it's defunct, if it's so awesome?
- sporkenfang 10y ago
  The author graduated and nobody stepped up to maintain the work. Happens to 99% of graduate student projects. The sad truth here is a lot of well maintained open source work is funded by companies who pay individuals to work and/or maintain the projects. Lots of cool ideas have no such luck.
  - mirimir 10y ago
    OK, I get it. I didn't know that he did Pond as a grad student.

indolering 10y ago

> For latency sensitive microblogging, we can support up to 10,000 users with less than one second latency with 160 byte messages. This is not a general-purpose mix network.