Combating traffic analysis over request-response protocols 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:


Contribute a message to the chat, where the server responds verifying that the message was sent.
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:


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.
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".
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.