Score:3

CBC mode with predictable IV ok if key is only used once?

mc flag

Someone told me recently that using CBC mode with a predictable (e.g. all 0) IV is reasonably secure if a key is only used for encryption one time. I've gone through a couple of examples of chosen plaintext attacks against CBC mode with a predictable IV and it does seem that they assume that the key that is used for the attacker's encrypted text is the same as the key used for the attackee's encrypted text. Also, in this instance, an attacker could not control the entirety of the plain text that is encrypted, just a small portion of it.

So, is this person correct, does using the key for encryption only once make using a predictable IV safe or is there an issue I'm not seeing?

Maarten Bodewes avatar
in flag
Interesting - I could not find a dupe on this site, while I'm sure that this has been at least part of other answers. The closest I could find is [this answer](https://crypto.stackexchange.com/a/5099/1172). Obviously, identical data at the start of multiple messages and of at least one block would lead to identical ciphertext blocks, so reuse of a key / IV combination is never IND-CPA secure without making specific claims on the input messages, *regardless* if the attacker controls the messages - no active attack / Oracle required.
Maarten Bodewes avatar
in flag
Full dupe [here](https://security.stackexchange.com/q/10081/2651) but posted on [security.se] before this site existed.
automatictester avatar
ht flag
You might be interested in [this](https://security.stackexchange.com/questions/17044/when-using-aes-and-cbc-is-it-necessary-to-keep-the-iv-secret)
Meir Maor avatar
in flag
We should have an answer to this here on crypto, legitemate question the answer linked above seems like a complete answer, shall we copy it verbatim and link to original? (possibly as community answer). Write something original which says essentially the same, possibly adding something not super important just to feel that we did something new?
Maarten Bodewes avatar
in flag
Hmm, maybe I should have posted my answer to the link that automatictester included here and then linked to it from the Security site. I am not certain about it, maybe something for [meta].
Score:3
my flag

So, is this person correct, does using the key for encryption only once make using a predictable IV safe?

Yes, he is correct.

This attack works by the attacker obtaining a CBC-mode ciphertext, and wants to verify the plaintext contents of a specific plaintext block. To do that, he computes that the input to the block cipher would be if that guess was correct (and the corresponding output), and based on that, create a plaintext message that, with the predictable IV, send that input to the block cipher. He then asks for that plaintext message to be encrypted with the same key. If the corresponding ciphertext message has the expected output block, he then knows that his guess was correct.

If we encrypt only a single message, then he cannot perform this attack - he can learn the original ciphertext, but then he cannot ask for a second message to be encrypted with the same key.

Now, this holds if the encryptor takes the entire plaintext, and encrypts it in its entirety, and that full ciphertext is sent to the receiver (and the adversary). If you run CBC mode incrementally, for example, you take the first part of the plaintext, encrypt it, send it out, and then take the second part plaintext, and then encrypt that, then that's not safe - if the attacker can listen to the first part of the ciphertext, and then (based on that) modify what the second part of the plaintext, he can implement the 'predictable IV' attack - even though it may not look like you're sending a second IV, because of how CBC mode works, you effectively are.

Also, in this instance, an attacker could not control the entirety of the plain text that is encrypted, just a small portion of it.

Doesn't matter - it's still safe even if the attacker has arbitrary control. For example, if the adversary can specify the entire message except for one bit, he still can't learn what that one bit is.

fgrieu avatar
ng flag
I don't see in the question anything that makes a multi-target attack impossible. Thus I can't agree. See [my answer](https://crypto.stackexchange.com/a/93801/555).
Score:1
ng flag

So, is this person correct, does using the key for encryption only once make using a predictable IV safe?

No, he is incorrect at least academically. And in some cases practically.

That's because of so-called multi-target attacks. Assuming $b$-bit keys, and $k$ random keys are used (and thus $k$ ciphertexts) for known common (or chosen) first block $P_0$ of plaintext (e.g. same start of the payload), there is a so-called multi-target attack with expected cost $2^{b-1}/k$ encryptions recovering one full plaintext, that is $k$ times faster than with random IV. That attack simply enumerate keys, enciphers the known fixed $\text{IV}\oplus P_0$, and searches the outcome in a table of all first ciphertext blocks (which can be optimized to cost just over a single memory access).

Even when the "known common (or chosen) first block of plaintext" condition is met, this attack is seldom a disaster in practice for random 128-bit or larger keys, even for very large $k$ (which would be many millions in some realistic scenarios, e.g. session keys). That's because storing and accessing the necessary table actually has a non-negligible cost (investment and power). It's hard to imagine we loose more than 20 bits of security against an attacker using ASICs, which is the most reasonable way to carry such attack against a 128-bit key by brute force. But the problem could be devastating if the key was deterministically derived from a password, and there's even a thousand passwords used.

poncho avatar
my flag
If there were only a million possible keys, you're pretty much broken already...
fgrieu avatar
ng flag
@poncho: I clarified what I mean. My million (now thousands) is not the number of _possible_ keys for the block cipher, but the numbers of actually used passwords, thus _actually used target_ keys for the block cipher, derived by a password-based key derivation function, e.g. Argon2 Scrypt or PBKDF2 assumed to lack random salt.
Meir Maor avatar
in flag
I find it lovely that I upvoted two good answers one answering yes and one answering no.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.