0
$\begingroup$

Do $\exists $ keys $k_1, k_2$ which given any (128-bit) message $m$ are related to each other by being

  • commutative to each other with $AES(AES(m,k_1),k_2)=AES(AES(m,k_2),k_1)$ $\forall m$ and generally $AES(m,k_1) \not= AES(m,k_2)$
  • or $k_2$ is equal to applying $n$-times $k_1$ with $AES^n(m,k_1)=AES(m,k_2)$ with $AES^n(m,k_1) = AES(AES^{n-1}(m,k_1),k_1)$, and $k_1 \not= k_2, n > 1$,
    target size: $2^5 \ge n \le 2^{64}$ to maintain $n<\sqrt{l}$ in $ \arg\underset l\min AES^l(m,k) = m$ for most $m$,
    for adequate security $n<2^{32}$

AES operates in ECB-mode.
$AES(m,k)$ means applying AES encryption on (128-bit) message with key $k$

If some keys like those exist is there a way to find them?


Statistically speaking such keys might exist for some $m$ but chances are too small to be valid for $\forall m$ unless the inner structure of AES allows some relation in between keys.


bonus:
If such keys can not exists for AES does a similar relation of keys exist for AES or is there some alternative block cipher which can offer such a key relation?

$\endgroup$
2
  • $\begingroup$ "$k_2$ is equal to applying $n$-times $k_1$ with $AES^n(m,k_1)=AES(m,k_2)$"; actually, this is known (even if we add the requirement that $n>1$); there exist values of $n$ for which this always holds for $k_1 = k_2$; one such $n$ (not the smallest) is $2^{128}! + 1$ $\endgroup$
    – poncho
    Jul 11, 2023 at 12:35
  • $\begingroup$ @poncho thank you for the hint! $k_1$ should not be equal to $k_2$ and $n>1$, added those conditions. Also $n \ll 2^{128}!+1$ $\endgroup$
    – J. Doe
    Jul 11, 2023 at 12:50

1 Answer 1

1
$\begingroup$

I don't believe there is any pair of keys that would hold true for either of your stated relationships that continues to hold true for all values of $m$. The number of codebooks for how you can permute a $2^{128}$ value from plaintext to ciphertext is huge, way larger than the $2^{128}$ key size for AES. The idea that two AES keys could be related in the way you describe seems astronomically implausible.

It sounds like you might be trying to reproduce the sorts of building blocks required to do asymmetric key agreement, except using symmetric building-blocks. This is (kind of) possible to do: See Merkle Puzzles. However, the difference in computational complexity between the participants and an eavesdropper for any symmetric-cipher based key-agreement scheme has been proven to be quadratic at best.

$\endgroup$
1
  • $\begingroup$ thanks for the answer. Ye, chances by random are too small. I did not know about Merkle Puzzles yet but quadratic seems to be too bad. Anyways I will mark this post as answer but if someone finds a inner structure of AES which allows that or some better alternative I will change it again. Thanks again! $\endgroup$
    – J. Doe
    Jul 22, 2023 at 15:48

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.