1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Is the alternative that you propose CPA-secure? Does it allow equally low-latency encryption and decryption as CTR? Does it allow direct read/write access to ciphertext, as CTR does? Does it allow enciphering a message of any size with no expansion beyond the IV? Hint: the answer to exactly one of these questions is yes. $\endgroup$ – fgrieu May 13 '18 at 10:46
4
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Yes, I left the detailed explanation why this check works out explicitely, because it "should be obvious" (and because I didn't have time). $\endgroup$ – SEJPM May 13 '18 at 10:53
  • $\begingroup$ Here is a CPA attacks working with unpredictable $n$: encipher a single message consisting of three all-zero blocks, except for the the low-order bit set in the second. The second blocks of ciphertext will be identical to one of the two others, depending on the low-order bit of $n$. $\endgroup$ – fgrieu May 13 '18 at 11:44

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.