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

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 ?
-
If you're designing this protocol, you really should consider using authenticated encryption (CBC with an HMAC is fine, assuming you get the details correct, but something like GCM mode is better) if at all possible. –  Stephen Touset Mar 15 '13 at 16:33
For memory, the IV in CBC mode should not only be unique, but also cryptographically secure (as opposed to a mode like CTR, where the IV only needs to be unique). Would you consider the IV in this protocol to be CS? @StephenTouset 's suggestion to use GCM is good advice. –  hunter Mar 15 '13 at 16:41
@StephenTouset: I never heard of that before. I will surely take a look. Thanks for the advice. –  ereOn Mar 15 '13 at 17:51
"cryptographically secure" is ambiguous, as it might mean "indistinguishable from random. $\hspace{.7 in}$ CBC's actual requirement for IVs is that they be unpredictable. $\:$ –  Ricky Demer Mar 15 '13 at 19:51
Yes. GCM mode is essentially a mode that natively combines CTR mode and an authenticator. You get secrecy and authentication. –  Stephen Touset Mar 17 '13 at 1:14

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.

A simple way to make the security as good as that of CBC with random IV would be to encipher the unique-but-predictable value with a key independent of the one used in the rest of the message.

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.

-
Thanks for this. I think I'm gonna implement the whole thing with AES in GCM mode. By any chance, would you know if the IV for this mode have the same constraints of unicity and unpredictability ? –  ereOn Mar 17 '13 at 9:58
The "IV" for GCM is actually called a nonce, and as the name suggests, it does not have to be indistinguishable from random. On the other hand, if the nonce is not unique then the consequences will be that all confidentiality of the plain text is lost. You may read the NIST requirements for the nonce in the CTR mode specifications. –  owlstead Mar 17 '13 at 15:39
More precisely, the IV for GCM shall be such that it (and its increments that will be used) is different from any other IV or increment thereof previously used with the same key. See appendix A in SP-800-38D. session_number|session_sequence|zeroes is usable as IV if the number of zeroes is more than the base-2 log of the number of blocks per messages. –  fgrieu Mar 18 '13 at 11:39