Score:0

Has AES some keys which are related to each other? e.g. $\forall m: AES(AES(m,k1),k2)=AES(AES(m,k2),k1)$ or $AES^n(m,k1)=AES(m,k2)$. How to find them?

at flag

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?

poncho avatar
my flag
"$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$
J. Doe avatar
at flag
@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$
Score:1
np flag

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.

J. Doe avatar
at flag
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!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.