Advantages/disadvantages of different message numbering schemes

Question

For a stream of packets, where each packet is individually encrypted with a block cipher, it's desirable to have each encrypted packet only valid for that position in the stream.

A message number would work, but there are many different ways of implementing it.

Given a construct using HMAC for integrity check (i.e. we send (HMAC || cipher-text) or (HMAC || IV || cipher-text), where HMAC is over cipher-text or (IV || cipher-text) respectively).

I can think of the following:

1. Encrypt (message || message-number), after decrypt check the message number.
2. HMAC instead (encrypted-message || IV || message-number), message number check is built into the HMAC.
3. Don't reseed the IV, so assuming CBC the IV of the current packet is the cipher-text of the last block of the previous packet.
4. Use a random initial IV, then for each packet, the actual IV used is HASH(IV || message number)
5. Use a random initial IV, then for each packet, the actual IV used is ENCRYPT(IV + message number)

What's the standard way of adding a message number, and are there any known security risks with the other methods I mention above?

Answer 1

If the receiver can wait for all the packets before decrypting:

This case is simple, since your final goal is to ensure that the plaintext you decrypt was the exact same plaintext you encrypted. (Trivially, this includes rejecting re-ordered plaintext.) Use an Authenticated Encryption (AE) scheme (eg, CCM, GCM, etc) across all the packets, treating the packet contents as concatenated parts of the same message. The receiver waits for all packets to arrive then authenticates and decrypts them. If the authentication fails, the message is different in some way, possibly because the contents are re-ordered, possibly something else.

If the receiver must decrypt packets as they arrive:

Encrypt each packet individually. Use an AE scheme that supports additional authenticated data, such as CCM or GCM. Such schemes are designed to encrypt a secret payload and authenticate the same secret payload alongside plaintext data, which is often times metadata relevant to the ciphertext. If the authentication passes, the receiver can be sure that the secret payload corresponds with the plaintext metadata and that both are unaltered.

This allows you to encrypt your plaintext $M$ as $C=E(M)$, authenticate the ciphertext $C$ along with a plaintext packet number/counter $ctr$, then send $(C,ctr)$ to the receiver. The receiver verifies that $(C,ctr)$ properly authenticates, meaning that $ctr$ belongs to that package.

Presumably the packet number isn't a secret since an attacker can probably watch the wire and count packets anyway. Nonetheless, the packet number $ctr$ can be omitted from the data the sender transmits and the receiver can just substitute the $ctr$ value that they are expecting when they receive the packet and perform the authenticate.

The Proposed Schemes

This assumes you're using CBC for encryption and HMAC for authentication.

1. This is a good option. In concept, you've created a very simple self-contained protocol for your data that encapsulates ordering of the packets. Then the packets are simply encrypted and authenticated. It's the simplest scheme, and the least likely to be screwed up.

2. This is essentially building an AE scheme for ciphertext and additional associated data (message-number is the associated data). Likely encrypted-message is variable length, but message-number is presumably fixed length. If it is fixed length this should work, if it's variable length this would require modification.

3. This is potentially risky. The IV for a CBC-encrypted message should be unpredictable and you're working in discrete packets. If the attacker can control what data is in a packet and has seen the previous packet, they will know the IV for the packet they are about to generate and can use that to launch attacks. There was a popular TLS/SSL attack that exploited this type of CBC IV chaining.

4. This option is actually kind of pointless. It requires that the original random IV be sent along with the derived (aka, "actual") IV, both MAC'd alongside the ciphertext. Verifying message-number would consist of re-deriving the real IV using the random IV and the expected message-number. It's essentially option (2): they both have an IV, message-number-based value, and the ciphertext.

   (To see why both IVs must be sent: If just the original random IV is sent, we can't validate that the derived IV is correct. The HMAC covers only the ciphertext and random IV, so after that the HMAC does the check the packet receiver will derive the real IV and have nothing to check it against. If message-number is wrong then the derived IV is wrong, and the first block of plaintext is trashed, but a trashed first block of plaintext is not always detectable.

   If just the derived IV is sent, the recipient can't validate what message-number the derived IV is for. The HMAC will validate the derived IV and the ciphertext, but the receiver will just decrypt using the IV, knowing nothing about what message-number should have been used to generate it.)

5. This would work, but it is pretty much the same as option (1) if you send the "actual" IV, since the receiver needs to check the message-number by decrypting the IV (option (1) would require decrypting the plaintext).

Of those listed, option (1) is probably the best. It isn't the cryptography itself enforcing the message ordering, rather the "protocol" encapsulated within the packets. Option (2) seems perfectly reasonable as well.