Encrypting or obfuscating transport stream identifiers in SSL-like connections

Question

First, a longish prologue.

Assume typical SSL/IKE/SSH-like connections where a Diffie-Hellman exchange is done first to establish session encryption and decryption keys, where those keys are subsequently used for all transmission in the connection, with a symmetric encryption algorithm, such as AES. Also assume that a single peer has many separate connections, with separate symmetric keys.

If the connections are not separated by other external means (such as TCP connections), a peer receiving a packet needs some way to distinguish which connection a packet belongs to, to know which symmetric keys to use for decrypting it.

This is obviously trivially handled by prefixing each message by a connection id (that is not cryptographically significant). This is the approach taken by IPSEC, for example (security association id, 32-bit integer).

And, here comes the question:

• What would be a method to encrypt the connection id in such a way, that nobody else but the recipient can tell which packets belong to which connection?

The simple solution would be to encrypt the connection id with an asymmetric encryption method for the recipient's public key, and prefix this block to each message. However, this solution is computationally too expensive to be done per packet, atleast with the traditional methods of asymmetric encryption (RSA, ElGamal, Elliptic Curves, etc.).

An incomplete solution would be that the recipient server has one shared connection id encryption key, which is revealed to each communicating party inside the Diffie-Hellman handshake. This way, no passive attacker can know which packet belongs to which connection - but every party in active communication with the recipient has the same shared symmetric encryption key, and can tell all the connections apart.

Yet another solution would be for the recipient just to trial decrypt each packet with every symmetric key it has, and see which decryption produces a valid authenticator for the packet. But this becomes computationally too expensive, if the recipient has more than a few connections.

So, my question is really - are there any other methods I haven't thought of that could be used for the purpose? There are all sorts of funky encryption methods one could use, such as homomorphic encryption, but I haven't really come up with anything solid. Or is this problem a straight case of asymmetric encryption (or trapdoor function), for which there are no sufficiently fast solutions?

Or, if such a method can not be found, then I would like to find a simple obfuscation method, that wouldn't really give any guarantees, but which would make it hard for an attacker to determine the connection identities from just a few packets.

Answer 1

Use a variation on your shared secret-key encryption proposal: Every packet has an encrypted header for which the plaintext is the connection ID concatenated with the packet sequence number. After successfully receiving a (connection, n) packet, the next packet received on that connection will be (connection, n+1). Store the encryption of (connection, n+1) in a hash table and remove the expired entry for (connection, n). When receiving a packet, do a hash table lookup using the packet's encrypted header word to find out its associated connection. Obviously for this to work, sender and receiver must use synchronized ciphers (e.g. a stream cipher initialized with a negotiated IV and the shared secret key).

You can easily extend this algorithm to deal with longer sliding windows by adding hash table entries for sequence numbers n through n+k. The space cost is O(mk) where m is the number of open connections and k is the length of the sliding window.