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?
The short answer for the mode: use EAX.
There are several reasons why EAX is Good, but, in particular:
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.
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.
