On Thu, Jun 19, 2014 at 2:15 PM, Brian Warner <[email protected]> wrote: > > I think you need one of (SURBs, Hidden Services, a realtime reverse > channel) to hide a recipient's identity
I'd include broadcast (e.g. alt.anonymous.messages) and PIR (e.g. Pynchon Gate). [Trevor]: >> It's interesting you're not proposing a "nymserver" here [...] >> I assume that's because you want to limit nym -> Alice traffic for >> security reasons, so it's safer to dole out SURBs in small quantities >> to correspondents? > > Yeah, small quantities limits the "burst of traffic" attacks that could > be mounted to try and discover the location of the recipient > (network-enforced rate-limiting). If I understand the arguments at [1], eliminating nymservers also helps against long-term "intersection" aka "statistical disclosure" attacks. [Trevor, wrt tackling forward mixing independent from reverse / replies / SURBs] >> Or at least, it's nice to solve easier problems on the way to harder >> ones. > > Yeah. I guess we should address the "two people who know each other get > to communicate securely" case before trying to tackle the case where one > of them doesn't know the other. While I agree, we should consider the counter-argument from Mixminion [2] and Sphinx [3] that indistinguishable forward and reverse messages give more security, so should be co-designed. From Mixminion: """ Since replies may be rare relative to forward messages, and thus much easier to trace, the Mixminion protocol makes reply messages indistinguishable from forward messages even for mix nodes. Thus forward and reply messages can share the same anonymity set. """ I see the benefit, but I'm not sure it's worth the cost. In particular, reading [2] and [3] makes me think: (a) "tagging attacks" are better handled with separate forward and reverse formats (b) the benefits of indistinguishable forward/reverse traffic are not huge I argue (a) and (b) below (this is long and and boring, sorry...) Tagging vs. separate formats --- Consider a tagging attack against forward messages: The entry mix can flip a bit in the message body that is sent to the next mix. This bit will stay flipped as subsequent mixes onion-decrypt the body with a stream cipher, so the recipient can see that the plaintext has a certain bit flipped and collude with the entry mix to determine the sender. This is fixed by putting integrity checks in the onion-encrypted headers, so mixes can discard tampered messages. For reverse messages, the sender uses a SURB provided by the recipient for the headers, so it's impossible for the headers to contain body integrity checks. But tagging the message body isn't an attack against reverse messages, since it doesn't affect recipient anonymity. So problem solved. (You might ask: what about messages between senders and recipients who both want identity-hiding. In that case, you could send a forward message to some middle-person containing a reverse message. The middle-person decrypts the reverse mesage and sends it (Mixminion supports this, combining it with the "crossover" notion - see below). The above measures against tagging still work). Tagging vs. a combined format --- Now consider a combined format. Forward messages have to be indistinguishable from reverse messages, so can't use integrity checks. That means tagged messages *will* flow through the mix net in the forward direction. To prevent this leaking information, MixMaster and Sphinx add some other mechanisms: * The body is processed with a large-block cipher, so that tagging the input to a mix results in a randomized output. * At a designated "crossover" mix in Mixminion (the exit mix in Sphinx), the input message body is used to decrypt the next destination. I think the security argument is: * The large-block cipher prevents the crossover mix from detecting that a message was tagged with a specific value, and undoing the tag so the message can be processed. * If a message is tagged, when it reaches the crossover mix the next destination is undecryptable. Thus no later mixes or the recipient get any information about the tagging. * The crossover mix does learn that a tagging - or some sort of tampering - occurred. But since the crossover can't link the message with a recipient, it doesn't matter if the tagging allows the message to be linked to a sender (and the large-block cipher makes linking to a specific sender hard, since different taggings can't be recognized). The last bullet is subtle. As Mixminion points out, "the choice of crossover point can still reveal information about the intended recipient". If the crossover mix was chosen because it has a relationship with some recipients but not others, then when it detects the tagging, it can associate the tagged message with these recipients. To prevent this, Mixminion recommends that the crossover mix should be be placed in the path after sufficient mixing has already happened to protect the sender's identity, but with some additional mixes following (Sphinx doesn't support this - the exit mix is used as a crossover). Mixminion also discusses the possibility of "multiple-message" tagging, where the crossover is able to infer that several messages passing through it might be related (e.g. they arrive at similar times). If some of these message are tagged and some are not, the crossover could learn the destination from the untagged ones. To prevent this, Mixminion suggests that senders should choose different crossover points. Stepping back, the issue seems to be that crossover mixes are in a position to learn *something* from the tagged message, so we need to make complex arguments, and be careful choosing them, to prevent this being a problem. Security without a combined format --- So the mechanisms and security situation wrt tagging are complicated in the case of a combined format. Are the benefits of indistinguishable forward and reverse traffic worth it? Mixminion argues that it's helpful to combine forward and reverse traffic since "replies may be rare relative to forward messages, and thus much easier to trace". To argue the other way: * Due to link encryption, forward and reverse traffic will always be indistinguishable to outsiders (i.e. anyone but the mixes themselves). * A viable mix net might get a lot of security from dummy traffic. In that case, the dummy traffic could contain both forward and reverse messages, so a severe imbalance could be avoided. * If reverse messages are rarer (perhaps because more users care about relationship-hiding than identity-hiding), then it might be acceptable for reverse messages to spend more time in the mix net to get the same degree of security. Anyways, I admit this is a hard question, but I think there's decent arguments for anyone to work on a simple format for forward mixes that resists tagging attacks (e.g. something like [4]). Trevor [1] http://archives.seul.org/mixminion/dev/Oct-2007/msg00010.html [2] http://mixminion.net/ [3] http://www.cypherpunks.ca/~iang/pubs/Sphinx_Oakland09.pdf [4] https://eprint.iacr.org/2002/119.pdf _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
