Why do we only encrypt nounce + counter in Counter Mode?

Question

I do not understand, what the advantage is in only encrypting the nonce + Ctr and XORing this to our plaintext, instead of encrypting everything. (If our block cipher can be easily decrypted)

What would be the other downsides of turning

$c_i = E_k(n + i) \oplus m_i$

into

$c_i' = E_k((n + i) \oplus m_i)$

This should prevent flipping a bit without destroying the entire block, right?

Answer 1

This should prevent flipping a bit without destroying the entire block, right?

Yes it does that, but at the cost of loosing security similar to ECB.

So let's go through through the security game for eavesdroppers and for the sake of simplicity choose $n_1=0$ and $n_2=2^{32}$.

1. The challenger generates a key $k$.
2. The adversary generates two messages of the same length $m_0=m\parallel (m+1)$ and $m_1=m\parallel m$ for an arbitrary choice of $m$ and submits them.
3. The challenger encrypts them and returns $c_b=n_b\parallel \operatorname{CTR'}_k(m_b)=n_b\parallel c'\parallel c''$ for a uniformly chosen $b\in\{0,1\}$.
4. The adversary checks whether $c'=c''$, if yes, 0 is returned, else 1 and this answer is always right and thus security against eavesdroppers (!) is fully broken.

While the above is nice and simple, it requires predictable nonces to work. A variant for unpredictable nonces has been suggested by fgrieu in the comments, with the following modifications to the above:

1. $m_0=0\parallel 1 \parallel 0$ (that is the first and the third block are all-zero, the second block has only the LSB set) and $m_1=0\parallel 0\parallel 0$ (that is three all-zero blocks)
2. The encryption now is $c_b=n_b\parallel c'\parallel c''\parallel c'''$
3. The adversary now returns 1 iff all three $c',c''$ and $c'''$ are pair-wise different, else the adversary returns 0.