Is AES key and cipher distance measurable? Could this be translated into a cost function?

Question

Given a plain-text, two keys, and two cipher-texts:

• p: plaintext
• k: actual key and k': predicted key
• c: actual cipher and c': AES(p, k')

Can you calculate the degree of incorrectness of k' in NP-deterministic/NP-easy time? Does err(k, k') or err(c, c') exist?

The impetus of this question is to develop a cost function in a deep learning algorithm. Currently, there is the possibility for only one cost function C(k, k')= (k != k) or C(c, c') = (c != c'). This function shows zero cost for a correct guess and full cost for an incorrect guess—this cost function will never improve the learning of the network...

Answer 1

Currently, there is the possibility for only one cost function $C(k, k')= (k \neq k)$ or $C(c, c') = (c \neq c')$. This function shows zero cost for a correct guess and full cost for an incorrect guess

Not quite. Hamming distance is an obvious candidate, as in the comments. Another candidate might be the compatibility of the two permutations $E_k$ and $E_{k'}$ or $$\#\{x:E_k(x)=E_{k'}\}.$$ There are other distances on permutations such as Kendall tau, as well.

It's probably going to be difficult to do this except at a reduced scale, so I remain skeptical. Maybe try it on weaker or reduced round ciphers.

Answer 2

The question leaves it unspecified what properties the degree of incorrectness of k' must have, beyond being calculable in NP time.

If $k$ is known (as stated), the archetypal such function is probably the Hamming distance between $k$ and $k'$, that is $$d(k')=\operatorname{popcount}(k\oplus k')$$ where $\operatorname{popcount}$ counts the number of bits set.

Obviously, $d(k)=0$; there are no other $k'$ with $d(k')=0$; exactly $n$ values of $k'$ with $f(k')=1$ where $n$ is the bitsize of $k$; and more generally ${n\choose j}$ values of $k'$ with $f(k')=j$. With oracle access to $d$, it is trivial to find $k$, and a deep learning algorithm will have no trouble with that.

---

One function that seems to fit the name and does fit the calculable requirement even when $k$ is unknown (a common hypothesis in cryptography) is:

$$f(k')=\operatorname{popcount}(c\oplus\operatorname{AES}(p, k') )=\operatorname{popcount}(c\oplus c')$$

or, in other words, the Hamming distance between the actual ciphertext, and the ciphertext obtained for key $k'$.

Obviously, $f(k)=0$. Modeling AES-128 as a key-dependent PRP, we expect that beyond $k$, there are very few values of $k'$ with $f(k')=0$ (like zero, one or two values ); around $128$ values of $k'$ with $f(k')=1$; and more generally around ${128\choose j}$ values of $k'$ with $f(k')=j$. So that $f$ behaves quite similarly to $d$ from this standpoint, for AES-128.

There is some bad news, though: consensus is that a deep learning algorithm given oracle access to $f$, or even the full explicit definition of $f$ including the AES step, won't be able find $k$, or even find $k'$ with low value of $f(k')$, faster than trying $k'$ at random. If it did, that would be a break of AES. The security of AES relies on the conjecture that, even considering the definition of AES, the task is impossible.