21
$\begingroup$

What if, instead of using CBC mode in the normal way with a random IV, I used this approach:

  1. Use a fixed IV (like a block of 0's).
  2. Before encrypting, generate a random block and prepend it to the plaintext.
  3. After decrypting, ignore the first block.

Is this exactly the same in terms of security as using a random IV?

Also, would it make any difference if I used something like a message counter instead of a random block in step 2?

$\endgroup$
17
$\begingroup$

The security of that approach is equivalent to that of normal CBC.

Your scheme with first plaintext block $IV^\prime$ is clearly identical to normal CBC with $IV=AES(IV^\prime)$. Since a block cipher is a permutation over a block, a uniformly random first plaintext block will lead to a uniformly random IV for normal CBC.

A ciphertext produced with your scheme is of the same nature as with plain CBC. i.e. you can decrypt a normal CBC ciphertext with your algo, and you can decrypt a ciphertext produced by your algo with normal CBC.

The only downside of your scheme is that it costs one additional AES invocation per message. No difference in ciphertext size, and no CPU cost beyond that single call.

One interesting question is what happens with IVs that are unique, but not unpredictable. I suspect your scheme is secure in such a situation, unlike normal CBC. But I don't have a proof for that.

$\endgroup$
  • 1
    $\begingroup$ I'd postulate that the scheme is secure with predictable IVs such as counters as long as the number of encrypted blocks is below the birthday bound. The idea is that the AES primitive will never encrypt the same block twice. The failure when a collision happens might be more severe though. $\endgroup$ – CodesInChaos Nov 19 '12 at 11:53
  • $\begingroup$ @CodesInChaos CBC encryption already fails upon reaching the birthday bound, so one should rekey well before then. $\endgroup$ – Demi Jan 14 at 5:59
  • $\begingroup$ Proof of a related security theorem, where the IV is a counter: crypto.stackexchange.com/a/67296 Adapting this to consider the possibility of IV collision if the IV is chosen randomly left as an exercise for the reader. $\endgroup$ – Squeamish Ossifrage Mar 12 at 18:13
11
$\begingroup$

If you look at the CBC diagram, you'll see that having a fixed IV is equivalent to having the first ciphertext block become the IV. If your cipher is a good pseudorandom permutation, then what you are doing does work, if and only if all timestamps are unique such that the "new IV" is unique and unpredictable.

Blockquote

And in fact, if you do not use the decrypted value of the first block (the "IV") this is provably just as secure as normal CBC in the ideal cipher model, as the IV requirements of CBC (uniqueness and unpredictability) happen to coincide with what a pseudorandom permutation does.

If you do use that value, I am not sure. I believe it is still secure but cannot think of a convincing argument of why it is (or is not) right now, perhaps someone can complete this.

You may also set the "fixed IV" to zero for convenience - its value is irrelevant.


That said, it is probably best to fix your IV transmission, just to do things cleanly and not have to explain your weird IV trick. After all, if you can transmit the ciphertext, why can't the IV make it?

$\endgroup$
  • $\begingroup$ +1 to fixing IV transmission. If you can transmit the ciphertext, you can transmit the IV. Just append the IV to the ciphertext, and unpack it on the other end. $\endgroup$ – Stephen Touset Jan 20 '13 at 1:12
  • 1
    $\begingroup$ Also, be very sure your timestamps are unique. If they're only accurate to a second, you're probably going to be generating messages with identical timestamps, which could be very bad. You can also insert a random, unused nonce into each message, but then you might as well just use a dynamic IV. $\endgroup$ – Stephen Touset Jan 20 '13 at 1:15
  • $\begingroup$ The ciphertext is transmited in a data structure using a Web Service. So adding an IV force me to change the Web Service... and I am not the only one using this Web Service. $\endgroup$ – user687254 Jan 20 '13 at 18:48
  • 1
    $\begingroup$ So append the IV to the beginning of the ciphertext entry. It will be a fixed length, so can later be stripped off the front unambiguously. $\endgroup$ – Stephen Touset Jan 21 '13 at 20:05
6
$\begingroup$

Sure, that's fine, but you're really just using the first block of ciphertext as the IV.

If you choose the first plaintext block to be a running message counter (which you might as well do; it's easier than generating a random block) and your "discarded IV" to be all zeros (or vice versa) then your method is equivalent to standard CBC mode combined with the "encrypted counter" method of IV generation as described in Appendix C of NIST SP 800-38A:

"There are two recommended methods for generating unpredictable IVs. The first method is to apply the forward cipher function, under the same key that is used for the encryption of the plaintext, to a nonce. The nonce must be a data block that is unique to each execution of the encryption operation. For example, the nonce may be a counter, as described in Appendix B, or a message number. The second method is to generate a random data block using a FIPS-approved random number generator."

However, note that this scheme is only secure if the nonce in the first plaintext block is outside the control of the attacker. If the attacker can choose the nonce, they can trivially break this scheme, as described e.g. by Rogaway in section 4 of this paper.

As long as the uniqueness of the nonces can be guaranteed, such attacks can be thwarted by using a separate, independent encryption key to turn the nonce into the IV. However, if there's a risk of the attacker having any control over the nonce at all, uniqueness typically becomes hard to guarantee. In that case, the only solution (besides eliminating the possibility of an attacker influencing the nonce generation in the first place) is to switch to a nonce misuse resistant encryption mode such as SIV.

$\endgroup$
  • $\begingroup$ How is the IV unpredictable if I'm combining all zeros with a message counter? $\endgroup$ – Joshua Jan 9 '13 at 16:34
  • $\begingroup$ @Joshua: It becomes unpredictable (to an adversary who does not know the key) when it passes through the block cipher. $\endgroup$ – Ilmari Karonen Jan 9 '13 at 16:43
  • $\begingroup$ Note that that's assuming that the adversary does not have oracle access to the block cipher. Even if the adversary does have such access to the high-level CBC mode encryption function (i.e. they can request the encryption of chosen plaintexts), CBC mode prevents them from directly feeding chosen inputs to the block cipher as long as they cannot predict the IV. Thus, the ability to predict the IV and oracle access to the block cipher are essentially equivalent for an IND-CPA adversary attacking CBC mode using this IV generation method -- either one implies the other. $\endgroup$ – Ilmari Karonen Jan 9 '13 at 16:51
  • $\begingroup$ So then I am to understand that when you refer to being unable to predict the IV, that you mean that the first ciphertext block, whose plaintext is xor'd with the incrementing IV (or whatever), is sufficiently unpredictable between encryption runs, not that the IV used is sufficiently unpredictable? As it stands, if I were to pass the (incrementing) IV used in clear text along with the ciphertext, an eve would be able to see that the IV is clearly predictable, but the resulting first block still is not. $\endgroup$ – Joshua Jan 9 '13 at 21:51
  • $\begingroup$ @Joshua: In the scheme you've described in your question, the first ciphertext block is, in effect, the IV for the rest of the message. (That's how CBC works: every block of ciphertext is, in effect, used as the IV for the next block.) It's not predictable, even if the first plaintext block (or the "real" IV that's XORed with it) is, because it's obtained by encrypting the plaintext with an unknown (to the attacker) key. $\endgroup$ – Ilmari Karonen Jan 9 '13 at 22:44
3
$\begingroup$

The proper precautions, this is an acceptable way to implement CBC (and yes, it interoperates with the more traditional implementation of CBC, at least, implementations of CBC that put the IV immediately in front of the ciphertext).

The proper precaution is to make sure, in the encrypt direction, that the value of the iv exclusive-or'ed with the block of garbage isn't the value you used with for a previous block (or, at least, it's sufficiently improbable). If you use the same IV all the time, then you can make the garbage block an incrementing counter; if you use the last ciphertext block as the IV, well, just about any garbage block that isn't correlated to the previous encryption will work.

Now, why would you implement CBC this way? Well, I've personally run into two distinct scenarios where this trick helps:

  • You're using encryption hardware that always insists on using the last ciphertext block from the previous message. Now, we know that using predictable IVs can be insecure; this trick allows us to use such hardware without inheriting the potential security problems.

  • You're using hardware that can vectorize CBC mode (and so encrypting a message of 101 blocks is not much more expensive than encrypting a message of 100 blocks). With standard CBC mode, we need to generate an unpredictable IV; cryptographically secure RNGs can be expensive, at least, more expensive than writing a nonce into the garbage block, and asking hardware to encrypt one more block.

$\endgroup$
2
$\begingroup$

Sure you can do that and it would work just fine, but why would you do it?

It doesn't save any on the communications side of the house as you still have to communicate the garbage ciphertext block. On the computation side of things, if you decrypt that garbage block and throw it away, you have made one additional call to the block cipher operation that you don't really need to make.

In today's fast computers, that isn't much of an issue, but if you are on a low computation power device, making an extra call to the block cipher will add some unnecessary delay.

$\endgroup$
  • $\begingroup$ I guess its supposed to save on sending the IV out the door, but that the unnecessary calls to the encryption/decryption routines may be unacceptably wasteful $\endgroup$ – Joshua Jan 8 '13 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.