# Which block cipher modes of operation allow a predictable IV?

Recently I found out that in the modes CBC and PCBC the IV may be passed in cleartext but never must be predictable. However for this part of my app I rather have the IV be predictable and unique (i.e. generated from other data known to the "receiver" and also the adversary, and not stored/transmitted with the ciphertext) rather than random.

What options do I have as a cipher mode? How do I choose between them? Which is the main difference between OFB and CFB?

-
I added some information from the comments (as I understood them), and reworded your title. Feel free to edit again. –  Paŭlo Ebermann Aug 11 '12 at 10:43

The short answer for the mode: use EAX.

There are several reasons why EAX is Good, but, in particular:

• It includes integrity check, which is a must have (yes, really; defense against active attackers is often overlooked, and this is equally often deadly).
• It needs a unique IV (a nonce) but tolerates predictable nonces.

As for OFB and CFB, see the Wikipedia page which has nice schematics. However, since neither does any kind of integrity checks, you would have to add some kind of HMAC, so choosing a nice integrated mode like EAX is simpler (and simplicity is good for security).

If for some reason you really cannot use EAX (or another similar mode), you can survive CBC by generating unpredictable IV the following way: use your source of "unique, predictable IV" to generate block-sized values, and encrypt each value with the block cipher, using a distinct secret key (which you do not have to share with anybody else). This is like using the block cipher as a PRNG. You still need a bit of randomness at some point (when you generate that extra key) but not as much as previously.

-
I'll just note two reasons why your answer is good but not helpful to me. EAX is not available in .NET (at least to my knowledge. CBC,ECB,OFB,CFB,CTS all appear to be). In my situation I dont want to store the random IV anywhere which is why i am asking for ciphers which allow me to use predictable IVs. -edit- i am encrypting certain columns on a per row bases. –  acidzombie24 Aug 10 '12 at 20:15
IVs only ever need to be "stored" insofar as ciphertexts also need to be stored. $\:$ Furthermore, I don't see what that has to do with predictability of IVs. $\;\;$ –  Ricky Demer Aug 10 '12 at 21:55
Also you may want to check out my comment to this answer about salting an IV. I think i'm going with CFB since OFB gave me a runtime error about being an invalid mode for .NET RijndaelManaged class –  acidzombie24 Aug 10 '12 at 23:33
@acidzombie24, Bouncy Castle supports EAX mode and is available for .NET. See EAXBlockCipher. –  D.W. Aug 12 '12 at 5:20

Counter mode allows predictable IVs.

You generally partition the counter in to two pieces. One portion guarantees the counter is unique, the other piece is what you increment.

So when using a 128-bit block cipher you might partition it so that 64-bits are your uniqueness portion and the remaining 64-bits of the counter.

The uniqueness piece can be done by any scheme you like. If you're storing the data in a database, you might be able to use the row counter for this piece. If not, one suggestion is that you could set this to the MAC address of the encrypting host, followed by the number of milliseconds since 1970 with the remaining bits chosen at random.

The remaining 64-bits count up from zero on each clock of the underlying block cipher.

If you want an encrypt/authenticate mode that allows predictable IVs, try GCM.

-

Instead of a standard block cipher, you can use a tweakable block cipher. These can be constructed with low overhead from regular block ciphers. Then you can chain them together with a suitable mode to increase the effective block size. Alternatively, you can use a mode like CMC which directly constructs a tweakable cipher with wide block.

In a tweakable cipher, any two different tweaks (even adversarially chosen) induce independent ciphers. In particular, tweaks need not be secret or random or unpredictable, just distinct.

-

NIST Special Publication 800-38A, Recommendation for Block Cipher Modes of Operation, states in Appendix C that (emphasis mine):

"For the CBC and CFB modes, the IVs must be unpredictable. In particular, for any given plaintext, it must not be possible to predict the IV that will be associated to the plaintext in advance of the generation of the IV. [...]

For the OFB mode, the IV need not be unpredictable, but it must be a nonce 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."

Appendix B also allows (and describes appropriate methods for) the use of deterministic initial counter blocks (they avoid the use of the term "IV") for the CTR mode.

SP 800-38A does, however, allow the generation of IVs for the CBC and CFB modes by encrypting a unique deterministic value:

"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."

Ps. I'm a bit puzzled myself about NIST's advice against using predictable IVs with CFB mode, so I decided to ask a separate question about it.

Pps. In a paper published in 2008, "New proofs for old modes", Mark Wooding proves:

"that full-width CFB is secure if the IV is any ‘generalized counter’, and that both full-width and truncated $t$-bit CFB are secure if the IV is an encrypted counter."

Thus, CFB mode with full-block feedback is secure as long as the IVs are unique, while for CFB mode implemented with partial-block feedback using a shift register, the encrypted counter method recommended by NIST (which guarantees both uniqueness and unpredictability) should be used.

One reason for the difference is that CFB mode with low feedback lengths has some weak ("sliding") IVs, notably including the all-zero IV, that should be avoided. These weak IVs are rare, however, so a randomly chosen IV is extremely unlikely to hit them.

-