Combating traffic analysis over request-response protocols

Question

Suppose I am to design a request-response protocol (similar HTTP). For the sake of simplicity let us assume that this is a "chat" protocol where the client can only perform two actions:

1. Contribute a message to the chat, where the server responds verifying that the message was sent.
2. Request the chat contents, where the server responds with the chat contents.

All requests and responses have confidentiality, authenticity and integrity assurances. Requests and responses are of variable size.

In this protocol, a passive attacker can apply traffic analysis to estimate the size of a message sent, estimate the size of the conversation contents and distinguish between the two types of requests and responses.

The most obvious way to combat this type of traffic-analysis is to send and receive messages of fixed length at fixed intervals, however, due to the nature of the protocol, this is not possible.

How does one combat traffic analysis in such protocols without changing the nature of the protocol or wasting (a lot) bandwidth?

Update: Some of the information derived from traffic analysis of the protocol is of negligible importance for civilian purposes. I am mainly attempting to reduce the amount of information gained from the length of a request or response.

Suppose that the server supports multiple "chatrooms".

Here are two examples of how an attacker could utilize the length of server responses:

1. Given that different "chatrooms" do not have contents of equal size, the length of a server response to a "chat contents" request will differ for every "chatroom". This allows a passive attacker to distinguish between "chatrooms" that the user might be accessing.
2. In the same way as above, a passive attacker that can monitor the traffic of two users can detect if they participate in the same "chatroom".

Answer 1

The obvious way to combat frequency analysis is to completely mask every kind of frequency. For a chat server with a moderate number of clients this could be achieved e.g. by imposing the restriction that each client might have at most N chats open at any time and send at most M characters per L seconds in each chat. Then have each client poll the server each L seconds and have the server return a response of size N*M + header size each time.

Update Given the requirements in your updated answer, it seems to me you just have to implement a function server side that calculates the maximum length of the response the client might get regardless of which chat rooms he or she is currently attending.

For instance, suppose the protocol is such that each message in each chat room is given an auto incremented serial number, and each request is on the form "send all message in chat room RID since message MID". The obvious solution would be for the server to store the messages in a table with the fields RID,MID,time stamp,data, on each request get the time stamp of RID,MID, calculate the total length of all messages stored after that time stamp, and respond with a block padded to that length.

If each client might attend only a single chat room at a time, the length of the response might be reduced to the amount of data of the most frequented chat room during the requested time period.

Answer 2

I would try to exploit the fact that client and server use a unique session, that communications are strictly serialized, and that messages are neither lost nor duplicated (if any such assumption does not hold, I guess it is simple to add a protocol for that). I would also consider the "chat contents" sent back by the server as one the messages (just very big).

To say, let's assume that - as first operation during the handshake- the client and the server agree on a certain randomized dictionary, where each message symbol (letter, group of letters, words, etc) is represented via a communication symbol.

Messages are then communicated only via the new encoding. Moreover, each symbol being produced and received influences the dictionary shared by each end. As result the dictionaries will change constantly, but will remain in sync. Think of an unoptimized adaptive Huffman encoding (if it were really optimized you would give away symbol frequency).

If sessions are long lived, building of the initial dictionary would take negligible bandwidth. I cannot really say what the real bandwidth overhead will be, but if the update mechanism for the dictionary is reasonable, it may be quite low.

Answer 3

While maintaining a constant rate of data transfer is one way to thwart traffic analysis, I think there are other ways, too. Maybe this is only a half-baked idea, but wouldn't it be sufficient to maintain any fixed distribution of data transfer?

E.g., use a fixed packet size, and send packets at times that are indistinguishable from a Poisson distribution. (A Poisson distribution describes the output of a Geiger counter, or, closer to home, of popcorn pops. Each tiny interval of time has the same small probability of producing an event, namely some constant rho times the length of the interval.) When the user needs no data transferred, send dummy packets that could have been sent by a Poisson process for some value of rho. When the user needs more data transferred, send more packets but not so many that an observer could statistically determine that rho had increased.

Of course, the packet size could also be varied, keeping the same criterion that a burst of data is not statistically so anomalous as to allow an observer to distinguish it from a random fluctuation.