How does one design a traffic analysis resistant protocol? I'm curios about protocols which leak considerable personal information, like instant messaging exposing the contacts relation.  How does one make an instant messaging protocol which is resistant to traffic analysis?

I'm interested most specifically in server side attacks on users' contacts/friends lists.  In particular, the messaging system's servers are considered compromised, or even outright hostile.  I'm curious about the server aspect because Tor and I2P offer traffic analysis protection at the network level.

I could imagine an anonymous open mailbox like protocol.  A public key's hash identifies a public mailbox that's used for hello messages.  A hello message contains a seed for selecting a series of subsequent mailboxes that actually get used for communications.

You probably don't want attackers identifying the public mailboxes used for hello messages though.  You could perhaps scale the mailbox range with the user base to ensure that all mailboxes saw non-zero traffic while avoiding asking every participant to attempt to decrypt all messages as public key hello message.  Or maybe implement "please reuse" queue for mailboxes.

Is there any standard crypto literature on designing traffic analysis resistant protocols?
The obvious way to thwart traffic analysis is to send fixed-size messages at a fixed rate, whether there's any actual information to transmit or not.

I've heard it claimed that such protocols have been used in the past for diplomatic communications: a fixed-length packet of encrypted data would be sent say, once a day to an embassy in a foreign country, and the embassy would reply with another fixed-length encrypted packet.

Of course, such protocols are on one hand wasteful of bandwidth, and on the other constrain the peak bandwidth of the encrypted channel, which is why they're not more often deployed in practice.



To apply this principle to an instant messaging protocol, let's assume that we have a trusted central server acting as a message relay.  Each user of the messaging service establishes a separate encrypted connection to the server.  (We can use existing off-the-shelf protocols like SSL/TLS for that.)  Over these encrypted connections, the clients send messages to the server, which relays them to other clients.  (Again, we can use a standard instant messaging protocol like IRC or XMPP for the client&ndash;server interaction.)

The only unusual thing we'll do is throttle the communications between the clients and the server so that each client sends the server a single block of $n_c$ bytes at time intervals of $t_c$, and the server sends a block of $n_s$ bytes to each client at time intervals of $t_s$.  These blocks might combine multiple messages, and a single message might be split over multiple blocks; also, if there isn't enough data to fill a block, it's padded with dummy data which is ignored by the receiver.

(Note that the blocks need not map to single packets in the underlying transport protocol; it's enough that each block is fully assembled before it's passed to the transport layer, so that one cannot tell how many messages a block might contain by timing the transmission layer.  In many cases, this could be easily achieved by inserting an extra "chunking" layer between the messaging protocol and the encryption layer, without either having to be aware of the chunking.)

The parameters $n_c$, $n_s$, $t_c$ and $t_s$ should be chosen to match the needs of the messaging protocol.  For simple text-based instant messaging, $t_c$ and $t_s$ might be from 0.1 to 0.5 seconds, and $n_c$ and $n_s$ might range from, say, 64 to 256 bytes.  (Even lower bandwidth might be usable if the messaging protocol was optimized for it.)  Voice messaging is likely to need somewhat more bandwidth, depending on the audio quality desired.

The reason for using a central server is that, in a typical conversation, only one participant (or at most a few) is likely to be talking at any given time; thus, the peak bandwidth requirements for the clients will probably be more or less independent of the number of participants, whereas in a naive distributed protocol they'd scale linearly with it.  (This could be avoided by using more advanced messaging protocols, but that would complicate the example.)  Of course, the server would still require bandwidth proportional to the number of clients, but that's generally the case with centralized instant messaging protocols anyway, and it could be mitigated by connecting multiple servers in a network (with fixed-bandwidth links, of course!).