AES, Cipher Block Chaining Mode, Static Initialization Vector, and Changing Data

Question

When using AES (or probably most any cipher), it is bad practice to reuse an initialization vector (IV) for a given key. For example, suppose I encrypt a chunk of data with a given IV using cipher block chaining (CBC) mode. For the next chunk of data, the IV should be changed (e.g., the nonce might be incremented or something). I'm wondering, though, (and mostly out of curiosity) how much of a security risk it is if the same IV is used if it can be guaranteed that the first four bytes of the chunks are incrementing. In other words, suppose two chunks of data to be encrypted are:

0x00000000someotherdatafollowsforsomenumberofblocks
0x00000001someotherdatathatmaydifferormaynotfollows

If the same IV is used for both chunks of data, how much information would be leaked?

Answer 1

Well, that depends on the block size of the encryption algorithm. For the usual block size of 64 bytes i dont think that would make any difference. The first bits would be the same for many blocks, before entering the block cipher, but the result would not have any recognisable pattern. For block sizes < 4 bytes (i dont think that happens) it would make a difference, because the first block(s) would always be the same, leaking information about patterns. Just my opinion.

edit:

Found this

"For CBC and CFB, reusing an IV leaks some information about the first block of plaintext, and about any common prefix shared by the two messages"

Source: lectures of my university :)

Answer 2

In this particular case, it's fine. The "effective IV" is your first encrypted block, which is guaranteed to be different for each message (as long as the nonce truly never repeats under the same key), because the block cipher operation is a bijection.

It is, however, very fragile. Someone who is maintaining this protocol long after you've moved on to greener pastures might well not understand that the security depends heavily on that non-repeating nonce, and could "optimise" it out. Is sending that single extra block each message for a real IV really an overhead you can't afford?

Answer 3

Mark, what you describe is pretty much what is proposed in Appendix C of NIST SP800-38a. In particular, there are two ways to generate an IV:

1. Generate a new IV randomly for each message.
2. For each message use a new unique nonce (this may be a counter), encrypt the nonce, and use the result as IV.

The second option looks very similar to what you are proposing.