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

Question

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.

Answer 1

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.