2
$\begingroup$

I was wondering if it is possible to decrypt a cipher-text using a single key which was encrypted twice.

For example: Let's assume that we encrypt a plaintext using AES-CTR and encrypt the output again with AES-CTR using a different key. It's clear that there exists a keystream that can be used to decrypt the message in one step. However, I do not know if this keystream can be generated by the AES algorithm and if we can calculate the respective key efficiently.

Dos anyone know if this is possible or has a keyword, article, blog post I could look for?

PS: I know that this will NOT increase the security.

Improve this question
$\endgroup$
2
  • $\begingroup$ Is this similar to your question? stackoverflow.com/questions/9669077/… $\endgroup$
    – AleksanderCH
    Commented Aug 21, 2018 at 10:00
  • 1
    $\begingroup$ I have read about this in the past in the context of DES, where it was conjectured that for two keys $K_1,K_2$ there may exist a key $K'$ such that $\forall m: E_{K_1}(E_{K_2}(m))=E_{K'}(m)$, which was called a "group property" IIRC, but this was ruled out for DES. There's a paper by Rivest on this, "Is the Data Encryption Standard a Group?" (scanned PDF) $\endgroup$
    – SEJPM
    Commented Aug 21, 2018 at 11:40

1 Answer 1

Reset to default
2
$\begingroup$

No, the set of AES-CTR keystreams is not closed under XOR. That is to say, in general, for any two AES keys $K_A$ and $K_B$ there will not exist a third key $K_C$ such that $$\textsf{AES}_{K_A}(x) \oplus \textsf{AES}_{K_B}(x) = \textsf{AES}_{K_C}(x)$$ for all $x$.

At least, there is no reason to expect that such a key $K_C$ could be found. Offhand, I can't think of an obvious way to prove that one could not just somehow magically exist, but that would seem to require either a truly astronomical coincidence or a deep and fundamental weakness in AES.

In fact, there's a simple counting argument suggesting that this should never happen, simply because the set of possible CTR mode keystreams is immensely larger than the (already very large) set of AES keys. Specifically, AES keys are 128, 192 or 256 bits long, depending on the AES variant used, but an AES-CTR keystream repeats with a period of $128 \cdot 2^{128}$ bits. Thus, out of the $2^{128\cdot2^{128}}$ theoretically possible keystreams with that period, only $2^{256}$ can actually be generated by AES-256-CTR (and even fewer for the other AES variants).

Since the mapping from AES keys to the corresponding keystreams is supposed to be effectively indistinguishable from random, that also means that the probability of the XOR of any two AES-CTR keystreams just happening to itself be an AES-CTR keystream is at most one in $2^{128 \cdot 2^{128} - 256}$, i.e. effectively zero for all practical purposes.*

Of course, we do know that the mapping from AES keys to keystreams is not actually random, and there are even some known related-key attacks on AES that demonstrate this. But as far as I know, nobody's ever found anything to suggest that the XOR of two AES-CTR keystreams would be any more likely to match another AES-CTR keystream than the infinitesimally small probability of that happening by chance.

*) Literally. That's a probability of about $1/10^{10^{40}}$, i.e. about 0.00000...0001, where the ... stands for about 10 000 000 000 000 000 000 000 000 000 000 000 000 000 more zeros, give or take a few (or a few decillion).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for this answer! While reflecting the problem, I just thought about one-block data and I think that a key $K_c$ should exist here (??). However, if we think about larger keystreams it is very unlikely that this key exists which you stated very clearly! $\endgroup$
    – PraMiD
    Commented Aug 23, 2018 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.