# Question about IND-CPA with block cipher mode with random IV (CTR\$ mutation)

I know for a fact that CTR random is IND-CPA secure due to if an adversary want to break it, it will have to run a long loop where the $$\mathit{Adv}^{ind-cpa}_{CTR~random} = C(2^{n},q) - 0$$ However, if we change the encryption to something where in the beginning a random $$IV$$ is picked from the space $$\{0, 1, 2, ....2^k - 1\}$$ ($$k$$ as the block size) and for each block starting from $$i=1$$ to $$n$$ $$C_{i} \leftarrow E_{k} \bigl(\langle IV + i\rangle\oplus M_{i}\bigr)$$return $$IV||C_{1}||C_{2}||...||C_{n}$$Why is this not IND-CPA secure? The only different I can see this is different from CTR random is the random IV pick from the beginning is not run with the encryption $$E_k$$ before it XOR with the message and is increments with a predictable +1 in each block.

It is not CPA secure, because we can exhibit an attack against the CPA security of your construction.

There are two key insights here:

1. The attacker has (limited) control over the input to the Permutation $$E_k$$.
2. $$E_k(x) = E_k(x')$$ if and only if $$x = x'$$, since $$E_k$$ is a deterministic Permutation.

The trick is now to find two messages $$m_0,m_1$$, such that $$m_0$$ will result in the same value being fed into $$E_k$$ twice, while $$m_1$$ will result in different values being fed into $$E_k$$.

The attack works as follows: The attacker $$\mathcal{A}$$ outputs messages¹ $$m_0 = 0^{2\ell-1} \Vert 1 \quad\text{and}\quad m_1 = 0^{2\ell}$$ and receives the challenge ciphertext $$c^* = IV\Vert c_1\Vert c_2$$. If $$c_1=c_2$$, $$\mathcal{A}$$ outputs $$0$$, otherwise it outputs $$1$$.

Now we need to analyse the success probability of $$\mathcal{A}$$. Let $$m_b^i$$ denote the $$i$$th block of message $$m_b$$. As we noted above, it holds that $$E_k(x) = E_k(x')$$ if and only if $$x = x'$$. Therefore,

$$c_1=c_2 \iff \langle IV +1\rangle \oplus m_b^1 = \langle IV +2\rangle \oplus m_b^2.$$

For $$m_1$$, we have that $$\langle IV +1\rangle \oplus m_1^1 = \langle IV +1\rangle \oplus 0^\ell = \langle IV +1\rangle \neq \langle IV +2\rangle = \langle IV +2\rangle \oplus 0^\ell = \langle IV +2\rangle \oplus m_1^2$$

therefore, when given an encryption of $$m_1$$, $$\mathcal{A}$$ will always output $$1$$. In the other case, for $$m_0$$ however, we have

$$\langle IV +1\rangle \oplus m_0^1 = \langle IV +1\rangle \quad \text{and}\quad \langle IV +2\rangle \oplus m_0^2=\langle IV +2\rangle \oplus 0^{\ell-1}\Vert 1.$$

Now observe, that if the least significant bit² of $$IV$$ is $$1$$, then $$IV+1$$ and $$IV+2$$ will differ only in the least significant bit. I.e. $$\langle IV +1\rangle = \langle IV +2\rangle \oplus 0^\ell\Vert 1.$$ It thus follows that if (and only if) the least significant bit² of $$IV$$ is $$1$$, then $$\langle IV +1\rangle \oplus m_0^1 = \langle IV +1\rangle = \langle IV +2\rangle \oplus 0^\ell\Vert 1 = \langle IV +2\rangle \oplus m_0^2.$$ Since $$IV$$ is chosen uniformly at random, the lsb of $$IV$$ is $$1$$ with probabilty $$1/2$$. Therefore, the attacker has an overall success probability of $$\frac{1}{2}\cdot\left(1+\frac{1}{2}\right) = \frac{3}{4},$$ which is clearly non-negligibly greater than $$1/2$$.

¹Note that I'm using $$\ell$$ to denote the block-length, since $$k$$ would be confusing, given that it's also the key.

²Assuming appropriate endianess. If my endianess above seems wrong to you, just flip the bitstring around.

• @kelalaka Indeed. Thanks. Sep 9, 2020 at 12:35
• I am not clear with the last step, how did we compute the probability as 1/2*(1+1/2), basically I don't understand from where did we get (1+1/2). Feb 5, 2021 at 23:12