# Unique GCM/CCM initial counters without recipient side message counters

I am implementing the encryption layer for a communication protocol. The bulk encryption method used is either AES-CCM or AES-GCM. Due to implementation details, encryption of packets is usually, but not necessarily, performed by the sender in the same order the packets are sent over the network. This means two things:

1. Implicit packet counters can't be used to ensure that the initial counters are unique,
2. Explicit packet counters shouldn't be sent as plain text, due to implementation specific side channel attacks. (When packets are sent out of order, it is due to things happening sender side the attacker shouldn't be unnecessarily made aware of, and that would be significantly harder to spot using frequency analysis only.)

Packet counters are however sent encrypted and verified by the recipient using a sliding window technique.

Additionally, the following requirements should be met if possible:

• No additional AES context should have to be maintained for each connection. i.e. if AES encryption is used in any way, it has to be done using the same key as for bulk encryption.
• The size of the packets should be kept as small as possible. The overhead of the cipher text should be equal to the 96-bit nonce, 128 bit MAC, plus optional padding that might be used to mask the length of the plain text.
• I don't want to consider all possible security implications of letting the recipient simply try all possible implicit packet counter values in order (DOS-attacks, timing attacks, etc).

Thus, I am thinking a simple two-round unbalanced Luby-Rackoff cipher could be used for generating the nonces sender side, e.g.:

1. Let $T$ be the 32 bit encoding of the packet counter value.
2. Generate a 64 bit random bit string $S$.
3. Let $U = MSB_{32}(AES_k(0^{32}||S||0^{32})) \oplus T$
4. Let $V = MSB_{64}(AES_k(0^{32}||U||1^{64})) \oplus S$
5. If $MSB_{32}(V) = 0^{32}$ goto 2.
6. Let $Nonce = V||U$.

Since the transform is bijective, these nonces will be unique. Furthermore, the padding ensures that the plain text blocks passed to $AES_k$ do not collide with any counter values. Also, $AES_k$ is rekeyed at least once every $2^{32}$ packets, plus that the nonces aren't decrypted by the recipient since the packet counter value is also sent encrypted as part of the "regular" plain text.

The question is what the security level of the confidentiality of the packet counter counter values becomes?

Obviously, by the birthday paradox, there is a 0.5 probability that the same $S$ value will be generated at least twice before the cipher is rekeyed, and since the packets are sent in order most of the time, it should at least be easy to spot when such $S$ collisions do not happen, but is it possible to distinguish such occurrences caused by chance from those caused by $S$ collisions with non-negligible probability? Should a third round be added?

-