3
$\begingroup$

Let $E_{k}(P)$ be the AES-128 function with key $k$ and plaintext $P$, both 128 bits. I want to know if the following property is generally true for AES or if have I stumbled upon a special set of keys:

$$E_{k_1}(E_{k_2}(P)) = E_{k_1}(P) \oplus E_{k_2}(P)$$

$\endgroup$
2
  • 5
    $\begingroup$ It would be really interesting to know what those "special set of keys" are. $\endgroup$
    – polfosol
    Jan 22, 2023 at 18:53
  • $\begingroup$ Are you sure you've done $E_{k_1}(P)\oplus E_{k_2}(P)$ and not, say, $E_{k_1}(P)\oplus E_{k_2}(0)$? $\endgroup$ Jan 23, 2023 at 1:53

2 Answers 2

5
$\begingroup$

This would be a major weakness. It is false. You are essentially describing a "double AES" method, see question here. It is known that double AES or double DES is not much more difficult to break than the corresponding cipher on its own. The answer to the question shows double AES is no weaker than AES on its own. However your property would open AES up to attacks.

Let's assume your property holds and lets choose $k_1=k_2=0,$ the all zero key. Then this would give $$ E_0(E_0(P)) = E_0(P) \oplus E_0(P) = 0 $$ which would mean that AES is idempotent (it's square under composition is the identity map) for this key, for any message. This is patently false and would be a major weakness. One reason it is false is that the design of the key schedule with the round constants prevents AES being weak if the input message or key is all zeroes.

$\endgroup$
3
  • 1
    $\begingroup$ I think I can prove "AES is idempotent" is false by information theory. No non-expanding block cipher can be idempotent unless it is the identity function. On the other hand; I've been meaning to ask how bad it is to be able to find a particular key that makes a cipher idempotent for the all zeros block. $\endgroup$
    – Joshua
    Jan 22, 2023 at 21:42
  • $\begingroup$ @Joshua Being able to find a key that makes the cipher idempotent isn't necessarily too bad (assuming keys are randomly selected) unless it signals an underlying weakness that can be exploited other ways. $\endgroup$
    – forest
    Jan 22, 2023 at 22:53
  • $\begingroup$ The square under composition would be a constant map, not the identity map. This remains true if you replace $0$ with any key. This is more convincing than merely observing that one key is insecure (to me, at least): since $E_k$ is a permutation for any key, its square is also a permutation and so cannot be the constant map. $\endgroup$ Jan 23, 2023 at 1:48
1
$\begingroup$

A similar property holds true for a (synchronous) stream cipher.

So if you got not the block cipher AES, but e.g. "Counter mode AES applied on a single block with fixed initialization vector", you'd have $$E_k(P) = AES_k(I) \oplus P$$ (where $I$ is your initialization vector, e.g. the full 0 plaintext, or any constant, as long as it's the same for each use).

Then you get

$$ \begin{align} E_{k_1}(E_{k_2}(P)) & = AES_{k_1}(C) \oplus (AES_{k_2}(C) \oplus P) \\ & = AES_{k_2}(C) \oplus (AES_{k_1}(C) \oplus P) \\ & = E_{k_2}(E_{k_1}(P)) \end{align} $$ (i.e. chaining is commutative) and you'd also have $$ \begin{align} E_{k_1}(P) \oplus E_{k_2}(P) & = (AES_{k_1}(C)\oplus P) \oplus (AES_{k_2}(C) \oplus P) \\ & = AES_{k_1}(C) \oplus AES_{k_2}(C), \end{align} $$ i.e. the XOR of ciphertexts from the same plaintext is actually independent of that plaintext.

I didn't find a common function which is having your exact property, but there might be some around.

Please verify what actually your "AES" function is. If it's actually the block cipher (also called ECB – electronic code book), then I'd be really interested to see the keys you've used here to get your example.

$\endgroup$

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.