3
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ 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. 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. $\endgroup$
    – Maarten Bodewes
    Aug 30 '21 at 7:53
  • 1
    $\begingroup$ Full dupe here but posted on Information Security before this site existed. $\endgroup$
    – Maarten Bodewes
    Aug 30 '21 at 8:26
  • $\begingroup$ You might be interested in this $\endgroup$ Aug 30 '21 at 9:28
  • $\begingroup$ 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? $\endgroup$
    – Meir Maor
    Aug 30 '21 at 10:48
  • $\begingroup$ 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 Cryptography Meta. $\endgroup$
    – Maarten Bodewes
    Aug 30 '21 at 11:52
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I don't see in the question anything that makes a multi-target attack impossible. Thus I can't agree. See my answer. $\endgroup$
    – fgrieu
    Aug 30 '21 at 16:10
1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ If there were only a million possible keys, you're pretty much broken already... $\endgroup$
    – poncho
    Aug 30 '21 at 16:16
  • $\begingroup$ @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. $\endgroup$
    – fgrieu
    Aug 30 '21 at 16:20
  • $\begingroup$ I find it lovely that I upvoted two good answers one answering yes and one answering no. $\endgroup$
    – Meir Maor
    Aug 30 '21 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.