# Encrypted counter as IV in CBC mode encryption using same key

I'm currently working with a secure transport protocol that defines the IV to be a counter (incremental nonce) to be encrypted with the same key. This is a followup to a protocol that did not provide any kind of IV.

Could you please describe the possible attack vectors on CBC encryption using this encrypted nonce?

Furthermore, the protocol has the following characteristics:

• a MAC is calculated over each encrypted message and verified before decryption (including any parameters send)
• session keys are used that are recalculated each time the protocol is initiated
• the session is lost when any error is detected in the protocol
• the protocol is half duplex, with the attacker having full capabilities on the communication layer, but limited (if any) influence on the sender and receiver
• the cipher used is AES with sufficiently random session keys

Would these characteristics alleviate any of the concerns of using an encrypted counter using the same key?

Related question: What are the constraints for an IV using AES in CBC mode?

[EDIT]

Note that for this case the counter and IV are not send or included in the MAC calculation - which seems to be the main issue with the protocol.

-
If the IV was encrypted using a separate key then taking advantage of this scheme would be equivalent to somehow predict the values of an AES-CTR based PRNG. Since you're using the same key the reasoning doesn t apply but is there a reason why you can t derive 2 keys from your initial key and then go about your buisness ? –  Alexandre Yamajako Jul 14 '13 at 22:12
@AlexandreYamajako Simple: it is an existing protocol... –  owlstead Jul 14 '13 at 23:06

Since the counter values are not authenticated, an attacker can try to swap the order of messages in order to modify things. If a message arrives out of order, the MAC will be correct, since the ciphertext has not been modified, but after decryption, the first block of message will be messed up and the rest of the message left intact.

Will this be enough to lead to a real attack ? That highly depends on the semantics of the cleartext and the role of the first block of each message. It is certainly possible to build a set of messages and interpretations where having the option to randomize the first block leads to a devastating attack. It is also possible to build another set of messages/interpretations where the consequences will be negligible.

The real question is to compare this to your status before adding in the IV. Is the new protocol more or less secure ? Once again, this is unclear and depends on the way messages are treated after decryption. You really need to analyze in details the messages and how they are use to gain some more insight.

There is a real amusing point about your question. If the base protocol were using Mac-then-Encrypt instead of the usually recommended Encrypt-then-Mac [It would be OK, because even if Mac-then-Encrypt is not generically secure, it works with CBC mode - see http://www.iacr.org/archive/crypto2001/21390309.pdf. Warning:this paper don't say Mac-the-Encrypt but Authenticate-then-Encrypt] then your proposal would work finely, because changing the order of messages would mess the cleartext and the MAC would fail.

-
+1 thank you for your contribution. Having thought about it some more I think this is basically the vulnerability that cannot be reasoned away. I'll update my question to show that the IV is not send or authenticated. –  owlstead Jul 21 '13 at 12:10
I've accepted your answer because it is more specific than Seth's answer regarding my specific use case. I've however assigned Seth the 50 points because it clearly states that it could be secure (and it did not rely on specifics only disclosed at a later time). –  owlstead Jul 21 '13 at 12:51

Just to be sure we're on the same page, I interpret your question as defining encryption of a string $P_1 P_2 \cdots P_\ell$ with a counter $\mathsf{ctr}$, key $K$, and an $n$-bit blockcipher $E$ as follows: $$\mathcal{E}_K(\mathsf{ctr}, P_1P_2\cdots P_\ell) = C_0 C_1 C_2 \cdots C_\ell$$ where $C_0 = E_K(\mathsf{ctr})$, $C_{i+1} = E_K(C_i \oplus P_{i+1})$, and each $P_i$ is an $n$-bit string. (So I'm assuming plaintexts have already been padded as necessary.) I'm assuming the values that will be used for $\mathsf{ctr}$ are determined ahead of time. If this is incorrect, attacks become possible.

The scheme above is secure in the sense of real-or-random security under chosen-plaintext attacks (this is a somewhat stronger condition than semantic security). That is, an adversary cannot distinguish between $\mathcal{E}_K$ and an oracle that given an nonce and an $nm$-bit plaintext returns $(m+1)n$ random bits. This is true as long as $E$ is secure (in the sense of being a pseudo-random permutation), $K$ is random, and the total length of all the ciphertexts encrypted under a given key is much less than $2^{n/2}$ bits (the birthday bound).

Proof sketech. A standard game-hopping security proof might proceed like this:

1. Change the scheme to use a random permutation $\pi$ in place of $E_K$ (this is reasonable if $E$ is secure and $K$ is random).

2. Change $\pi$ to a random function $\rho$ (this is reasonable as long as long as the number of queries to $\pi$ is much less than $2^{n/2}$; see the PRP-PRF switching lemma).

As long as no input to $\rho$ is ever repeated, all its outputs are uniformly random and independent. Therefore using the encryption scheme over $\rho$ is indistinguishable from an oracle that outputs random strings, as long as this condition holds. So we need to bound the probability that an input to $\rho$ is repeated.

From here the proof proceeds like the standard CBC security proof, with the caveat that instead of looking for collisions just among the $\rho$ inputs we've already seen, we also need to worry about one of the inputs being equal to a counter value we'll need in the future. (This is where the assumption that counter values are pre-determined comes into play.) Since barring a repeated input, each $C_i$ and therefore each $C_i \oplus P_{i+1}$ is a uniform random value independent of previous queries, the probability that a given $C_i \oplus P_{i+1}$ is equal to a counter value is at most $q / 2^n$, where $q$ is the number of queries the adversary will make (and hence the number of counter values we require).

Using a union bound, the probability that such a collision will ever occur is at most $q^2 M /2^n$, where $Mn$ is the length of the longest plaintext. This probability is negligible as long as $(qM) \ll 2^{n/2}$. And note that $qMn$ is an upper bound for the total number of bits encrypted.

So. The encryption scheme $\mathcal{E}$ is not significantly less secure than CBC with a random IV. The larger question of whether the protocol as a whole is secure as a much more difficult question, and one that I can't answer without knowing more about it (and probably couldn't answer even if I did). But you are authenticating the counter, right? :)

-
Thank you very much for this extensive answer. The counter itself is not authenticated in the scheme. That said, repetition is clearly prohibited and the encrypted counter (\$C_0) is never transmitted (it's zero based and increased before encryption, and both parties have the key). The ciphertext itself - together with other info - is authenticated using a second key. –  owlstead Jul 20 '13 at 1:07
@owlstead, you need to authenticate the counter. You can include it in the data that MAC is applied to, without transmitting it, so this doesn't need to affect performance -- but that's critical for security. –  D.W. Jul 20 '13 at 23:59
@D.W. This is an existing protocol, I don't have the power to change it. I was just wondering if it did not leave a hole. I guess it does, I'll talk to the persons involved in creating the protocol. –  owlstead Jul 21 '13 at 12:03
Seth, could you check if minor's answer applies? I'm pretty sure that it does. I think the final answer is that the idea of an encrypted counter as IV is valid as long as you validate the counter or IV in a communication protocol. –  owlstead Jul 21 '13 at 12:16
@owlstead, Seth's proof shows that the encryption algorithm is IND-CPA (secure against chosen-plaintext attacks). The job of preventing modification/tampering of ciphertexts, preventing chosen-ciphertext attacks, and ensuring the authenticity/unspoofability of messages is left to proper use of the MAC. Therefore, yes, your final answer is correct. In general, you always needs to MAC the IV, no matter what mode of operation you use for encryption (even plain CBC mode) -- so this does not invalidate Seth's answer in any way. –  D.W. Jul 21 '13 at 17:31