# IND-CPA security of CTR mode

Let's suppose CTR mode is instantiated such that the input to the block-cipher is $\langle \mathrm{IV}+\mathrm{ctr}\rangle$ instead of $\mathrm{IV}\mathbin\|\langle \mathrm{ctr}\rangle$, where $\langle X\rangle$ is the bit representation of $X$.

Will the mentioned version of CTR encryption scheme be IND-CPA secure against nonce-respecting adversaries? If not, can this be made nonce-IND-CPA secure by adding some cryptographic methods over it without altering the underlying structure?

• IV+ctr and IV||ctr and IV xor ctr can all be identical depending on the position and size of the IV within the block – Richie Frame Feb 14 '17 at 10:48
• @RichieFrame As per my understanding(I am new to the field), if IV is random all the three should be identical (the IND-CPA security of the cipher will not be affected) but if we make the IV non-random nonce(such as packet counter) the chosen-plaintext attack will completely break the security of cipher (obviously making it IND-CPA insecure). I was wondering that if in the example of CTR here : en.wikipedia.org/wiki/…, instead of concatenating the counter with the random nonce if we do IV+ctr, will it affect the IND-CPA security? – ironhide012 Feb 14 '17 at 18:42
• Note that the NIST document containing counter mode encryption has some remarks on how the initial counter can be created, including security remarks. – Maarten Bodewes Feb 14 '17 at 22:40

The crucial property you want to achieve CPA security is that each combination of $\mathrm{IV}$ and $\mathrm{ctr}$ is used at most once, since you essentially derive a key from this combination and use it to encrypt the corresponding block with the one-time pad. If you choose $\mathrm{IV}$ uniformly at random from a large enough space, this will be the case with high probability for both variants you describe.
If $\mathrm{IV}$ is a packet counter, $\mathrm{IV} || \langle \mathrm{ctr} \rangle$ is still fine if you reserve enough bits for both $\mathrm{IV}$ and $\langle \mathrm{ctr} \rangle$ to exclude overflows. The variant $\langle \mathrm{IV} + \mathrm{ctr} \rangle$, however, now becomes insecure: If two packets are encrypted where the first one contains at least two blocks, the second block of the first packet will be encrypted with $\langle 1 + 2 \rangle = \langle 3 \rangle$, and the first block of the second packet will be encrypted with $\langle 2 + 1 \rangle = \langle 3 \rangle$. Hence, an attacker who knows the contents of the second block in the first packet can learn the first block of the second packet. As long as you only increment the combination of $\mathrm{IV}$ and $\mathrm{ctr}$ by one for the next block, this problem persists unless you ensure there is a large enough gap between two packets. This is exactly what $\mathrm{IV} || \langle \mathrm{ctr} \rangle$ ensures.
• @ironhide012 As far as I can tell, your understanding is correct. ;) I am not sure what exactly you mean by not changing the underlying structure: $\mathrm{IV} || \langle \mathrm{ctr} \rangle$ is actually not too different from $\langle \mathrm{IV} + \mathrm{ctr} \rangle$ since you can write $\mathrm{IV} || \langle \mathrm{ctr} \rangle = \langle 2^{[\text{# bits reserved for ctr}]} \cdot \mathrm{IV} + \mathrm{ctr} \rangle$. If you want to change the structure less than this, I don't see how it can be done. – Christian Matt Feb 15 '17 at 20:41