Anonymizing a group chat

Question

I wonder if it's possible to have a peer-to-peer group chat protocol, where anybody is free to join the chat and broadcast with a chosen username to all others who have joined it, but with a strong anonymization property. The property desired is that it is impossible, or at least difficult, for a man-in-the-middle to determine which IP address is associated with each username in the chat. To be clear the man-in-the-middle is able (like anyone else) to join the chat and observe everything being said, and he can also be assumed able to monitor all transmissions of at least some members of the chat.

Naturally, the timing of packets could give away who is who, so it would be necessary for all users to be sending packets at regular intervals to hide which users are actually speaking.

If the chat system uses a server, the man-in-the-middle can be assumed to have access to the server. So it's no good to simply encrypt all messages between each user and the server.

I'm thinking about a scheme where users are constantly passing "pieces" of messages between each other, and trying to assemble pieces into completed messages by XORing recent pieces, in a way that it's not clear who first sent all the pieces required for a message. Each peer to peer link could be encrypted with the recipient's public key.

However, the man-in-the-middle may be free to create as many users as he wishes, which might defeat this scheme. If man-in-the-middle users greatly outnumber other users, then the man-in-the-middle can trace most of what's going on.

Is it possible?

Answer 1

You are essentially describing instant messaging via onion routing or garlic routing. Tox is an example of such a protocol. Tor Chat is another.

In an onion network, messages are encapsulated in layers of encryption, analogous to layers of an onion. The encrypted data is transmitted through a series of network nodes called onion routers, each of which "peels" away a single layer, uncovering the data's next destination. When the final layer is decrypted, the message arrives at its destination.

Below is a simple illustrated description of onion routing (taken from Wiki).

In this example onion, the source of the data sends the onion to Router A, which removes a layer of encryption to learn only where to send it next and where it came from (though it does not know if the sender is the origin or just another node). Router A sends it to Router B, which decrypts another layer to learn its next destination. Router B sends it to Router C, which removes the final layer of encryption and transmits the original message to its destination.

This does not completely defeat attacks, but if implemented correctly it should be difficult to de-anonymize users and interpret traffic. The arrest of silk road creator Ross Ulbricht suggests that with enough desire, time, and luck the FBI could catch you. But even then, you'd probably need to make some mistakes along the way. And obviously the FBI are not your average man in the middle.

Answer 2

Anonymous messaging systems do exist. Examples include Karaoke, Stadium, and Vuvuzela. In these systems, anonymity is defined using the notion of differential privacy. Systems with stronger notion of privacy/anonymity also exist. For examples and references, see section 2.1 in the Karaoke paper: https://www.usenix.org/system/files/osdi18-lazar.pdf

Note that onion routing like Tor network does not protect against traffic analysis.