3
$\begingroup$

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.

$\endgroup$
0
4
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ @kelalaka Indeed. Thanks. $\endgroup$ – Maeher Sep 9 '20 at 12:35
  • $\begingroup$ 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). $\endgroup$ – user2179923 Feb 5 at 23:12

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.