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.


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

  • $\begingroup$ Thanks! I actually came up with this idea myself earlier on. I believe that some variation of the new Freenet UDP protocol uses this approach. However, while a sliding window of 64 packets (for example in IPSEC for replay protection) is enough for packet reordering, this is only because newer packets can always move the "sequence number" forward. If one needs to tolerate packet dropping, a window of 64 packets means that a maximum of 64 packets can be sent without an ack from the remote end while still being able to hit the hash table. So, assuming packet drops, this approach is difficult. $\endgroup$
    – Nakedible
    Dec 18, 2010 at 12:02
  • $\begingroup$ I'll mark this answer accepted after a few days anyway, if nobody comes up with anything else - however, it's not a solution I can use (and I should've remembered to mention that approach in my original question). $\endgroup$
    – Nakedible
    Dec 19, 2010 at 20:50
  • $\begingroup$ @Nakedible: Sorry I couldn't be of more help. Your (very interesting) question might be better suited for another venue; it's really more a systems than a theory problem. $\endgroup$ Dec 21, 2010 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.