0
$\begingroup$

In CTR mode (not nonce-based), if we have ${IV}\stackrel{\$}{\leftarrow}\{0,1\}^{128}$ and want to encrypt message blocks $M_1, M_2, ..., M_\ell \in\{0,1\}^{128}$:

The ciphertext is $IV\parallel C_1\parallel C_2\parallel...\parallel C_\ell$, where $C_i=AES_k(IV+i-1)\oplus M_i$.

Note that $IV$ is random here.


How about changing the CTR mode into the following algorithm?

The ciphertext is $IV\parallel C_1\parallel C_2\parallel...\parallel C_\ell$, where $C_i=AES_k(\boxed{IV\oplus(i-1)_{128}})\oplus M_i$.

Here, $(i-1)_{128}$ means a 128-bit block that has $(i-1)$ in its lower bits.


Such a change has a benefit: it is easier to implement $(IV\oplus1)$ than implement $(IV+1)$ using CPU instructions or in garbled circuits.

I wonder whether there is any security proof showing such a construction is equal to CTR. Currently, I don't even find the good keyword for that.

Note: one answer How do we compute IV+1 in CTR mode? mentions this change. I feel some security discussion is needed.

$\endgroup$
  • $\begingroup$ I'm pretty sure the security proof for CTR does't care about how you come up with a new input for each block cipher call as long as you do at all, thus this method should be fine. $\endgroup$ – SEJPM Aug 5 '18 at 22:06
  • $\begingroup$ Are you asking whether it's OK to combine a normally incrementing block counter with the IV using XOR, or whether it's OK to increment the counter using $i \mapsto i \oplus 1$ instead of $i \mapsto i + 1$? The former is indeed fine (and equivalent to normal addition if the IV is constructed by padding a nonce with zero bits on the right, as is common); the latter is obviously broken, since $(i \oplus 1) \oplus 1 = i$. $\endgroup$ – Ilmari Karonen Aug 6 '18 at 1:28
  • $\begingroup$ Also note that, if you're looking for counter that can be "incremented" using a simple circuit, you can use a long-period LFSR as mentioned in the answers to the question you linked to. $\endgroup$ – Ilmari Karonen Aug 6 '18 at 1:29
  • $\begingroup$ @IlmariKaronen let me clarify. So I did not mean to make it by XORing with 1. Rather, it is the counter = the initial counter xor (1) for the first block, and the counter = the initial counter xor (2) for the second. $\endgroup$ – Weikeng Chen Aug 6 '18 at 6:35
  • $\begingroup$ @SEJPM agree. It is very intuitive to prove from PRF security, though. I just curious why in the history people still uses "+"... it increases the implementation difficulty... $\endgroup$ – Weikeng Chen Aug 6 '18 at 6:36
2
$\begingroup$

A fairly common way to implement CTR mode is to construct the IV by taking a per-message nonce of, say, 96 bits and appending 32 zero bits to the right of it. These 32 least-significant bits are then incremented by one for each cipher block in the message.

This method has the useful property that if the nonces are never reused, and if no message contains more than 232 cipher blocks, then the counter values can be guaranteed to never repeat.

For your purposes, another useful feature of this method is that, as long as the above conditions hold (i.e. as long as $i \le 2^{32}$ and the lowest 32 bits of the IV are all zero), then $IV + (i-1) = IV \oplus (i-1)$. Thus, it makes no difference at all whether you combine the IV and the block counter using addition or XOR, or even just concatenate the nonce directly with the 32-bit block counter.

$\endgroup$
  • $\begingroup$ Consider that I only use it to encrypt no more than 4 blocks, I would choose to have 120bit nonce and 8bit counter. $\endgroup$ – Weikeng Chen Aug 6 '18 at 18:03
  • $\begingroup$ @WeikengChen If you only need to encrypt four blocks, you don't need more than a 2-bit counter. $\endgroup$ – forest May 17 at 22:23
  • $\begingroup$ It is easier to implement per byte :) $\endgroup$ – Weikeng Chen May 18 at 23:06

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.