4
$\begingroup$

Consider a known plaintext attack on AES — just so we have an actual system of equalities that we can feed to a SAT solver.

Is AES solvable in this way? In other words, will the algorithm eventually complete, producing the correct key?

After reading through these set of slides, I assume the answer is yes, but that it is computationally even more costly than brute force, making it impractical.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
8
$\begingroup$

Is AES solvable in this way? In other words, will the algorithm eventually complete, producing the correct key?

Almost yes. It will produce some correct key — there might be more than one.

(It should quite plausibly be unique given "enough" plaintext-ciphertext samples, but this need not be the case in general.)

Generally, computing the key in a known-plaintext scenario is in $\mathbf{NP}$, hence can by definition be reduced to any $\mathbf{NP}$-complete problem such as $\mathrm{SAT}$. If this is done correctly, solving the $\mathrm{SAT}$ instance is bound to produce a correct key — but fortunately, doing so is not at all practical to the best of our current knowledge.

(If it turned out that $\mathbf P=\mathbf{NP}$, this would potentially change that picture a bit, but in that case we are doomed anyway.)

Therefore the short answer is: Yes, but it doesn't help.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ You can quite easily show that for a few random messages there will be a single key except for very small probability. (Note that saying "unfortunately" depends on what side of the fence you sit. As cryptographers, we very much want $P\neq NP$ and more.) $\endgroup$
    – Yehuda Lindell
    Mar 3, 2016 at 17:42
  • $\begingroup$ @YehudaLindell That first sentence doesn't work for me with "random messages". Besides, yyyyyyy already put that in the fine print, didn't he? $\endgroup$
    – Maarten Bodewes ♦
    Mar 3, 2016 at 17:48
  • $\begingroup$ You say unfortunately anybody with data to protect would say fortunately. $\endgroup$
    – kasperd
    Mar 3, 2016 at 18:04
  • $\begingroup$ @YehudaLindell Doesn't that need an additional assumption? Unless I am missing something, one can easily construct a PRP $(F_k)$ such that two distinct keys $k_1,k_2$ yield the same permutation $F_{k_1}=F_{k_2}$. Right? $\endgroup$
    – yyyyyyy
    Mar 3, 2016 at 18:31
  • 2
    $\begingroup$ Even if we had a constructive proof of P=NP, the constant factor for this problem may be millions of years. $\endgroup$
    – OrangeDog
    Mar 3, 2016 at 19:14
2
$\begingroup$

yyyyyyy's answer is great, and nicely points out that everything in $\mathrm{NP}$ can be reduced to an $\mathrm{NP}$-complete problem like $\mathrm{SAT}$, but I feel like it might leave a reader with a misconception in this particular case. Note that the problem you've pointed out (finding a key that matches some known plaintext/ciphertext pairs) is in $\mathrm{P}$, and in particular, can be solved in $\mathcal{O}(1)$ time by look up table (for a fixed number of input pairs).

It turns out that questions asking about classes like $\mathrm{NP}$ and $\mathrm{NP}$-complete has essentially no traction on practical problems, where we generally deal with finite primitives, rather than infinite families of primitives. It is simply too coarse of a tool.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ This answer misses the point. Of course, it is possible to brute force anything that is finite. Then, since the world is finite everything is efficient. However, computational complexity works in that it even though it is asymptotic in nature, it predicts the difficulty of working on large inputs. $\endgroup$
    – Yehuda Lindell
    Mar 3, 2016 at 19:28
  • $\begingroup$ @YehudaLindell The answer isn't missing the point: rather, it's pointing out that P-vs-NP isn't the right model to be using here. This is because the P-vs-NP model does lead to the unreasonable conclusion that recovering a key of fixed length is, by the definitions used within that model, a constant-time operation. The model fundamentally contains the idea that fixed-sized instances are easy; pointing that out is not "missing the point." $\endgroup$
    – David Richerby
    Mar 3, 2016 at 21:31
  • $\begingroup$ The question does not make any assumption about the type of algorithm used to solve the SAT system. It may complete in a reasonable amount of time. Whether such algorithms on SAT's exist is for another question. $\endgroup$
    – user9070
    Mar 3, 2016 at 21:52
  • $\begingroup$ @DavidRicherby I don't agree; I think that it is missing the point. The theory informs practice here in a very fundamental way. In any case, what is important to point out is that even if $P\neq NP$, this does not mean that it cannot be broken. One needs much stronger assumptions than just $P\neq NP$. $\endgroup$
    – Yehuda Lindell
    Mar 4, 2016 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.