What are the constraints for an IV using AES in CBC mode?

Question

I'm designing a protocol for use into a VPN software.

The VPN frames are encapsulated into AES-256 CBC encrypted frames. I understand that IVs must be uniquely used for each message encrypted with the same key. I believe that usually protocols generate those randomly and transmit them (in cleartext, since those are no supposed to be secret) with the ciphertext.

In my case, I wanted to avoid that because transmitting 16 bytes of IV for each VPN frame has a huge cost in bandwidth (in some cases, the size of the headers would exceed the size of the encapsulated frames) so I decided to compute those IV instead, using the following mechanism:

4.4.1. DATA messages initialization vectors

   Each DATA message relies on the session keys and on an initialization
   vector. This initialization vector MUST be unpredictable.

   That is, it is computed for each DATA message using a concatenation
   of the current session and sequence numbers. The concatenation MUST
   have the following layout (numbers are in network byte order):

                  0      7 8     15 16    23 24    31
                 +-----------------------------------+
                 |          session_number           |
                 +-----------------------------------+
                 |          sequence_number          |
                 +-----------------------------------+
                 |           must_be_zero            |
                 +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+

   The must_be_zero field is a sequence of 0x00 bytes so that the whole
   frame is the size of a block for the selected cipher algorithm.

   The concatenation buffer, which is globally unique, is then ciphered
   using the target host encryption key (KE) without padding and using a
   null initialization vector.

   The resulting buffer is the initialization vector to use to (de)cipher
   the DATA message.

The complete protocol specification is available here if anyone wants to read it.

The session_number is constant for a given session (it has the same lifetime than the AES keys of the session) and the sequence number is a zero-initialized counter incremented on each send.

Doing so, I believe I have an unpredictable IV (because the attacker would have to know KE to predict the IV) and that this IV is unique (because it depends on the sequence_number which changes for each message).

I realized lately that this method was expensive in CPU time and was the cause of performance issues (because of the hash computation that seems to be the bottleneck).

So I do have two questions here:

• Is my method correct (read "secure") ?
• How could I do differently to avoid computing a hash for each IV while keeping unpredictability and uniqueness ?

Answer 1

The IV for a block cipher in CBC mode must not only be "uniquely used for each message encrypted with the same key". It is usually assumed to be indistinguishable from random by an adversary.

If the IV is predictable, some attacks apply. For example, if an attacker is able to choose plaintext messages with prior knowledge of what the IV will be for this chosen plaintext, she can determine if a plaintext block in a previous message matches a guess; that's simply by submitting a message which first plaintext block is the exclusive-OR of that guess, the IV that will be used, and the ciphertext block preceding the block guessed (or the corresponding IV if the guessed block is the first block); then checking if the first ciphertext block for the chosen plaintext matches the ciphertext block for the guessed plaintext (there is a match if and only if the guess is right).

If I understand it correctly, the scheme proposed avoids transmission of the IV, replacing that IV with a (never transmitted) value obtained by enciphering a unique but predictable value, with AES and the same key as used as in the rest of the message.

This is not quite as good as a random IV. For example, an adversary temporarily gaining the capability to encipher blocks of her choice with the key (or equivalently, temporarily gaining the capability to dynamically choose plaintext blocks as a function of the previous ciphertext block within the same enciphered message) can use that capability to compute IVs that will be used in the future, in turn making it possible to verify guesses on messages encrypted after she had been denied that arbitrary block encipher capability, if she still has the capability to encipher chosen messages (having in-advance knowledge of the IVs, she proceeds just as outlined above in the regular CBC case). By contrast, with a truly random IV, the temporary possibility to encipher arbitrary blocks does not compromise the security of later messages.

Admittedly, the threat model I have been considering is quite hairy, and does not match the one usually assumed in the standard proof that CBC is IND-CPA (where the adversary has the capability to encipher arbitrary messages, but never to encipher arbitrary blocks). I fail to tell if the proposed scheme is IND-CPA, or not (that's an interesting question; an interesting variant would use decryption, rather than encryption, to prepare the IV).

Note 1: It is easy to make an implementation goof when trying to avoid reuse of a predictable value, especially if the key survives power loss.

Note 2: The scheme as described in the question does not insure integrity. That's a major practical issue.

Note 3: I fail to understand how the proposed scheme can be considered inefficient, and how "hash" crept into that consideration.