5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Richie Frame Feb 14 '17 at 10:48
  • $\begingroup$ @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? $\endgroup$ – ironhide012 Feb 14 '17 at 18:42
  • $\begingroup$ Note that the NIST document containing counter mode encryption has some remarks on how the initial counter can be created, including security remarks. $\endgroup$ – Maarten Bodewes Feb 14 '17 at 22:40
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The packet counter case is fine. For the case when IV is chosen uniformly at random from a large enough space, as per my understandings, the variant ⟨IV+ctr⟩ (overflows excluded) should be IND-CPA secure as each of them is going to be used at most once. Please correct me if I am missing something. Also, can ⟨IV+ctr⟩ variant with IV as packet counter be modified to behave as IND-CPA secure cipher(maybe by adding some extra cryptic block) without changing the underlying structure(i.e. ⟨IV+ctr⟩ should not be switched back to IV ||⟨ctr⟩)? $\endgroup$ – ironhide012 Feb 15 '17 at 1:26
  • $\begingroup$ @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. $\endgroup$ – Christian Matt Feb 15 '17 at 20:41

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.