Using CBC with a fixed IV and a random first plaintext block What if, instead of using CBC mode in the normal way with a random IV, I used this approach:


Use a fixed IV (like a block of 0's).
Before encrypting, generate a random block and prepend it to the plaintext.
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?
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.