Unique GCM/CCM initial counters without recipient side message counters

Question

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 ciphertext 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 values become?

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?

Answer 1

Perhaps a workaround for this would be to instead use deterministic nonce generation with AES-GCM-SIV, which has been formally proposed in a paper by Shay Gueron and Yehuda Lindell. The core idea is to use the MAC over the plaintext as part of the initial counter for encryption and reuse that as a tag on decryption.

This can be bolted onto any AES and GCM implementation if you have the ability to call GHASH standalone.

This has several advantages:

• The counter only needs to be kept for re-keying, but no longer needs to be sent over the network in any way.
• You gain IV/nonce reuse resistance (though it still leaks whether two messages were identical), possibly allowing randomized nonces safely.
• You're back on the “beaten path” so that you're back in an area where cryptanalysis exists, rather than homegrown cryptography.

But also disadvantages:

• You need an initial extra AES call to derive the internal keys when initially setting up keys, plus an extra call with a separate context for every authentication tag.
• The scheme is inherently dual-pass, once to derive the authentication tag and once for the encryption/decryption, so it may be unacceptably slow for your use case.

---

Technically, this meets your criteria:

1. Implicit packet counters can't be used to ensure that the initial counters are unique,

Non-uniqueness no does not lead to a loss of confidentiality with AES-GCM-SIV. You can avoid using a counter and instead use a randomized nonce (or a fixed nonce if you know all messages will be unique, e.g. by making the counter part of the message body instead).

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

The packet counter does not have to be sent in any way with AES-GCM-SIV.

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.

AES-GCM-SIV unfortunately requires a second AES context to encrypt the GHASH output with, but this requirement is only a “should”.

• The size of the packets should be kept as small as possible. The overhead of the ciphertext 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.

Depending on how exactly you implement this, the size of the packets will actually go down if you use a fixed nonce and unique message bodies.

• 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).

There won't be any packet counter values to try because it's completely out of the attacker's hands.