1
$\begingroup$

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...

$\endgroup$
  • 1
    $\begingroup$ Why not just use hamming distance? Although I'm curious what you're trying to "learn". If AES is designed well, it seems to me that your network shouldn't be able to learn anything useful. $\endgroup$ – bkjvbx Oct 9 '16 at 17:22
  • $\begingroup$ The goal is to build a complex system that can infer previously unknown properties of AES cryptanalysis. But, in order for the network to get better (learn) there has to be some error function it can descend on. The error can't be the hamming distance because if the network predicts a key which gives a cipher block 0 that is only a few bits off, that key may be very different from the original key (this is counterintuitive) $\endgroup$ – miiiiiitchko Oct 9 '16 at 17:46
  • $\begingroup$ Sorry disregard my previous comment, the hamming distance of the keys is a perfect cost function $\endgroup$ – miiiiiitchko Oct 9 '16 at 17:57
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your last paragraph is a reference to related-key attacks, I think? This question seem to be a different point of view for a formalization of those kind of attacks. With the additional restriction, that $p$ is fixed and the oracle just accepts different values for $k'$. Which means you can't relate learned information to other values of $p$. $\endgroup$ – tylo Oct 10 '16 at 15:06
  • $\begingroup$ @tylo: I was not thinking of related-key when writing my last paragraph; only observing that the $f$ (for fixed $p$ and $c$) that I describe won't practically help a key-recovery attack, or even a (pointless) find-a-key-with-near-mathing-ciphertext attack. $\endgroup$ – fgrieu Oct 10 '16 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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