Is using a predictable IV with CFB mode safe or not?

Question

While writing this answer, I noted that NIST SP 800-38A says 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 CBC mode, using a predictable IV allows a well known chosen plaintext attack exploiting the way in which the IV is combined with the first block. However, I don't see how a similar attack could apply to CFB mode; indeed, as I observed in an earlier answer, the CFB, OFB and CTR modes are equivalent for the first block.

Indeed, in this answer, Thomas Pornin writes that (emphasis again mine):

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

So, is Thomas wrong, or is NIST mistaken or merely excessively cautious? And if there is an attack enabled by using predictable IVs with CFB mode, how does it work?

Answer 1

Thomas is correct; there's no attack on CFB mode if you can predict the IV; NIST is just being cautious.

With CBC, the value of the first encrypted block $C_0 = E_k( IV \oplus P_0)$, where $IV$ is the IV used for that packet, $P_0$ is the value of the first plaintext block, and $E_k$ is the evaluation of the block cipher.

If an attacker can predict the value of the $IV$ in advance, and can influence the value $P_0$, then he can get the value $E_k(Q)$, for any value $Q$. Here is how; he learns the value of $IV$, and then injects a message whose first plaintext value $P_0 = IV \oplus Q$. The encryptor will generate an encrypted message whose first block is $C_o = E_k( IV \oplus P_0 ) = E_k( Q )$.

Using this encryption oracle, the attacker can verify guesses on the possible decryption of previous messages.

In contrast, with CFB mode, the first encrypted block is $C_0 = E_k(IV) \oplus P_0$. While this looks similar, there is no similar opportunity to an attacker to select the block that is presented to the block cipher. If the attacker knows the IV in advance, all he knows the value of the first block that will be presented to the block cipher; he cannot influence it by selecting any specific value for the first plaintext block. Now, if the attacker can control the value of the IV, then yes, he can use that directly to create an encryption oracle; he generally don't allow the attacker to do that.

In addition, if we use the same IV repeatedly, then there is also a weakness (beyond the rather obvious leaking of the first block); the second ciphertext block is $C_1 = E_k( E_k(IV) \oplus P_0 ) \oplus P_1$; if $IV$ is constant, so is $E_k(IV)$, and so the attacker can select messages with $P_0 = E_k(IV) \oplus Q$, also creating an encryption oracle.

The bottom line: predictable IVs are safe in CFB mode, as long as they don't repeat, and you don't allow the attacker to pick them.

Answer 2

I found a little more info on Google, so let me provide a partial answer to my own question. In particular, I found a post by David Wagner to sci.crypt in 2004, titled "IND-CPA for CFB mode", which in turn led me to a paper titled "Practical symmetric on-line encryption", published in FSE 2003 by Fouque, Martinet and Poupard.

In this paper, the authors prove that CFB mode (using full-block feedback) is IND-CPA secure as long as no input block to the cipher is reused (and as long as the underlying block cipher is secure), and that this holds with high probability as long as the IVs are chosen at random, and as long as the total number of $n$-bit blocks encrypted with a given key is much less than $2^{n/2}$. (In fact, with these assumptions, they prove indistinguishability under a stronger attack model which they call concurrent blockwise adaptive chosen plaintext attack.)

However, while Fouque et al. indeed assume random IVs, it does seem to me that their proof works just fine even with deterministic IVs, provided that the adversary does not get to choose the IVs and that the method of choosing the IVs does not specifically encourage collisions. (For example, using a counter as the IV should be fine, whereas choosing the next IV by encrypting the previous IV — with the same key as used for message encryption — and optionally XORing it with a predictable constant would definitely be bad.)

However, a bigger issue with the security proof by Fouque et al. is that it only provides a meaningful security margin for CFB mode with full-block feedback (and a sufficiently large cipher block size). Naïvely extending their proof to CFB-$k$ mode (i.e. the variant of CFB mode using $k$-bit truncated output with a shift register) only shows this mode to be secure when the number of blocks encrypted with the same key is much less than $2^{k/2}$. (A more careful analysis could perhaps improve this bound, but that looks like a non-trivial task.) Obviously, for e.g. $k = 1$ or even $k = 8$, this proves absolutely nothing at all!

Indeed, as David Wagner notes in his post, there are weak IVs for CFB-$k$ with small $k$, consisting of bit patterns that repeat with period $k$ or small multiples thereof. (In particular, if the IV and the plaintext consists of all zero bits, the ciphertext will also be all zeros with probability $1/2^k$.) While these weak IVs are rare, and thus unlikely to be chosen by random, some of them — including, in particular, the all-zero IV — may be likely to occur more often than by chance in a naïve counter sequence.

I'm not aware of any practical security proofs for CFB-$k$ mode for small $k$, and David Wagner also writes so in his post. However, it seems clear that, if such encryption modes are secure at all, they can only be so if the IVs are chosen at random — possibly using the NIST-recommended method of encrypting a counter — or at least in some other manner that, with high probability, avoids the weak IVs described by Wagner.

However, for CFB-$k$ mode with large $k$ (say, $k \ge 64$), the Fouque et al. proof does demonstrate security comparable to other classical block cipher modes, provided that the IVs are chosen in a manner that does not allow an attacker to easily generate collisions. Random IVs will certainly work for that, but, as far as I can tell, so should e.g. using a counter as the IV. If in doubt, though, follow the NIST recommendation and encrypt the counter just to be sure.

---

Addendum: I found a paper by Mark Wooding, "New proofs for old modes", IACR Cryptology ePrint Archive (2008), which gives improves security proofs for a number of classical block cipher operating modes. In particular, he writes:

"We show 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. We also show that, unlike CBC mode, it is safe to ‘carry over’ the final shift-register value from the previous message as the IV for the next message."

(By "generalized counter", if I read the paper correctly, Wooding simply means any fixed enumeration of the IV space, possibly known to the attacker.)

Answer 3

A predictable nonce that cannot be controlled by the adversary is safe as a CFB IV (with some assumptions), as shown in the other answers. However, a nonce that can be chosen by an adversary is not safe against chosen plaintext attacks, as shown in Evaluation of Some Blockcipher Modes of Operation (page 36):

Assume s = n. The adversary asks its oracle to encrypt $(N^1, P^1)$ where $N^1 = 0^n$ and $P^1 = 0^{2n}$, getting back the two-block ciphertext $C^1 = C^1_1C^1_2$. Next the adversary asks its oracle to encrypt $(N^2, P^2)$ where $N^2 = C^1_1$ and $P^2 = 0^n$. It gets the one-block response $C^2$. The adversary outputs one (it thinks it has a genuine encryption oracle) if $C^2 = C^1_2$. Otherwise it outputs zero.

So an attacker controlled nonce is not indistinguishable under chosen plaintext attacks. This can be extended to a guessing attack against a block of previously seen ciphertext, by choosing the previous block of ciphertext as the nonce to an encryption oracle.

This is of course a very weak form of attack that will not apply to most predictable IVs, like counters.