Using a Non-Random IV with modes other than CBC

Question

The weakness CWE-329 is an interesting problem with CBC mode. However, does this same weakness affect the other modes of operation that rely upon an IV such as: PCBC, CFB and OFB? My gut feeling is, YES. I am wondering if there a consensus on this topic? Or is there a possible explanation of why its not a weakness.

Answer 1

Each mode of operation has its own IV requirements. Some need uniform, unpredictable randomness. Other are equally happy with just uniqueness.

CBC is well-known for its need of an IV chosen randomly and uniformly among the possible IV values, and such that an attacker who can choose the text to encrypt may not predict the IV value before submitting the said text.

PCBC is similar to CBC in that respect. When encrypting, PCBC is equivalent to applying a linear transformation on the input data, followed by CBC encryption. So PCBC also needs a uniform unpredictable IV.

CFB and OFB require only uniqueness: for a given key, each IV value shall be used at most once. The is no need for unpredictability or uniformness because the IV is first encrypted "as is" (before any operation with the plaintext) and encryption of a sequence of values with a good block cipher, using a key that the attacker does not know, is a good PRNG. This means that CFB and OFB somehow include what it takes to elevate a unique IV to appropriate uniform randomness.

CTR is somewhat similar to OFB. CTR encrypts the successive values of a counter, and the IV is the initial value for the counter. Security is achieved as long as no counter value is ever used twice with the same key. Hence, using CTR "burns" a range of consecutive values, beginning with the IV; none of these values shall be used afterwards as IV.

Note that OFB also generates a pseudo-random stream, and using as IV one of the block cipher outputs in a previously generated stream means that you regenerate the same stream from that point. So OFB also "burns" a bunch of values. However, these values are uniformly distributed in the set of block values, and not numerically consecutive as with CTR. The consequence is that a +1 policy on IV management (you emit several messages, each encrypted separately but with the same key, and simply increment an internal counter to get the next IV) is acceptable for OFB mode -- but not acceptable at all with CTR.

Remember the bit about CFB and OFB including their own PRNG ? The idea has been reused. Many modern block cipher modes, especially those which include checked integrity such as EAX or GCM, do the same kind of trick, and only require uniqueness.

---

Uniqueness and randomness are two distinct properties. Randomness is hard to get in some context; most desktop machines and servers manage to maintain an acceptable source of randomness (/dev/urandom, CryptGenRandom()... the name depends on the OS), but many embedded systems cannot. On the other hand, uniqueness is not totally free either: it needs some kind of memory, which resists across reboots. Using the current time as IV is tempting but delicate, unless you can guarantee a monotonous clock (otherwise, an attacker could reset the clock to trigger IV reuse).

However, appropriate cryptographically strong randomness yields uniqueness "for free" with overwhelming probability (if the block size is large enough, but you want to use 128-bit blocks for other reasons anyway). Therefore, if you have a strong PRNG on hand, you can use it to produce your IV for all modes.

Answer 2

As Ilmari says, modes of operation that convert a block cipher to a stream cipher are not susceptible to incremented IVs as a vulnerability. In this case, you're encrypting nonce values (IVs) through a block cipher to produce the key stream which you then use as a key stream, some form of operation (XOR) with the plaintext.

One CBC issue arises from the fact that $\oplus$ is commutative and associative and that for any $a$, $a \oplus a = 0$ and $a \oplus 0 = a$ hold. In terms of your SO answer I'll use slightly different notation - for IVs I'll use $I_p$ for the previous IV and $I_c$ for the chosen IV; $G$ represents my guess. Then I can compute $E(I_c \oplus (I_c \oplus I_p \oplus G)) = E(I_p \oplus G)$ and compare this to the actual encrypted block; in doing so I can validate or invalidate my guess. It works because of the elimination of $I_c$.

Although you could use this on a block basis, the issue comes with predictable IVs under the same key - then you have your exploit since you can predict the $I_c$ correctly and guess a $G$ and compare this to the created ciphertext for that instance.

Passing the IV through the block cipher, this does not occur since most block cipher designs are not malleable, as xor is; however, as with any stream cipher you are then working on the requirement that the key stream be indistinguishable from purely random information. If you repeat the same input to the block cipher, you repeat the same output and therefore generate two input bits that can be xor'd together to deduce two plaintexts xor'd together. From there, you can work to reproduce the key and plaintext parts.

Answer 3

I'm pretty sure at least the CTR and OFB modes are not affected: they simply use the block cipher as a keystream generator for a synchronous stream cipher, and, importantly, the generated keystream is not affected by the plaintext in any way.

The only (absolutely vital!) requirement for these modes is that the IVs (and for CTR mode, all other counter values used during the encryption process) must be unique. As far as I know, it's perfectly safe to maintain a single running counter for CTR encryption over multiple message, or to feed the last block of an OFB keystream once more through the cipher to generate the IV for the next message.

I don't believe CFB mode is affected, either, since the IV is passed through the block cipher before being combined with the plaintext. Indeed, for the first block of the message, CFB, OFB and CTR modes are all identical: they all compute the first block as ciphertext = plaintext ⊕ Enc(IV).

The PCBC mode is affected, however, since it is identical to CBC mode for the first block of the message. So is any other mode which encrypts the first block as ciphertext = Enc(plaintext ⊕ IV).