6
$\begingroup$

I recently have studied AES cipher. On CTR mode, is it possible to add, subtract, or XOR plaintext values on encrypted data?

For example: we have an encryption of $4$ and $6$ under the same AES key, respectively denoted by $AES(4)$ and $AES(6)$.

Without decryption, can we achieve the following?

$$AES(4)⊕AES(6)=AES(4+6)$$

Where "$\oplus$" is any operation we can do over AES.

$\endgroup$
4
$\begingroup$

No, with AES in CTR mode, it is not

possible to add/subtract(or XOR?) plaintext values on encrypted data

nor define operator $\boxplus$ such that $\operatorname{AES-CTR}(4)\boxplus\operatorname{AES-CTR}(6)=\operatorname{AES-CTR}(4+6)$ that works for unknown key and plaintexts. Informally: if that worked, it would be a weakness of the encryption scheme, which would be leaking information about plaintexts from the ciphertexts.

Notice that the above notation is misleading, as the result of AES-CTR depends on 3 parameters: Key, IV and plaintext, with IV normally random (making the argument above non-rigorous). But still, even if we assume fixed IV, what's asked can't be done: it is asking an operator $\boxplus$ such that $\forall s,\forall x,\forall y, (s\oplus x)\boxplus(s\oplus y)=s\oplus(x+y)$ where $\oplus$ is XOR, and $s$ is whatever the IV encrypts to under the key considered; which is impossible.

More generally, no secure mode of operation of any secure block cipher allow homomorphic encryption.

$\endgroup$
  • 1
    $\begingroup$ I know that explaining this formally would be difficult, but still I think there's a big gap in your informal argument, and you should distinguish the counter-reuse case and the unique-counter case. Exposing addition is just as bad as exposing xor (for example both reveal whether a message is zero). But with counter reuse, CTR does expose xor. $\endgroup$ – Gilles 'SO- stop being evil' May 13 '17 at 20:49
  • $\begingroup$ @Gilles: The argument can be made rigorous for unique-counter. The one(s) for $\operatorname{AES-CTR}(x+y)$ or $\operatorname{AES-CTR}(x\oplus y)$ can't be random, and the only choice that could work reliably are this/those used for one of $\operatorname{AES-CTR}(x)$ or $\operatorname{AES-CTR}(y)$ (in the random cipher model, almost nothing can be said about how other counters would encrypt); and then almost nothing is known about whichever of $x$ or $y$ uses the other counters, which makes a suitable $\boxplus$ hopeless. $\endgroup$ – fgrieu May 14 '17 at 18:17

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.