1
$\begingroup$

Suppose I have an encryption oracle for AES with some key $k$ (16 bytes) and that I know $n$ bytes of it. Is it possible to recover the rest ($16 - n$) in complexity less than $256^{16-n}$?

$\endgroup$
  • $\begingroup$ @kelalaka but this is not faster than $256^{16-n}$ (I corrected myself). $\endgroup$ – enedil Dec 21 '18 at 21:37
  • 1
    $\begingroup$ Your writing style is strange, anyway $256^{16-n} = 2^{128-8\cdot n}$. What is the value of n? if n = 5,6,7,8....15-btye then brute force works. $\endgroup$ – kelalaka Dec 21 '18 at 21:41
  • $\begingroup$ @kelalaka $n$ can be between $1$ and $15$. I'm interested if there are some publications on this topic. Brute force will not deliver the answer faster than brute force - $256^{16-n}$ is exactly the time needed by brute force. I don't know how should it be possible to brute it with $n = 5$, as $256^{16-5} = 256^11 = 2^88$, which is totally too big. It becomes manageable with $n = 11$. $\endgroup$ – enedil Dec 21 '18 at 21:51
  • 1
    $\begingroup$ Bitcoin mining reached $\approx 2^{91}$ SHA-256 mining in one year. Summit can reach $2^{73}$ in one year. $\endgroup$ – kelalaka Dec 21 '18 at 21:56
  • $\begingroup$ @kelalaka I mean breaking it by myself :c $\endgroup$ – enedil Dec 21 '18 at 22:05
4
$\begingroup$

No, there is no known easier attack than doing a brute force search on the unknown key bits.

In particular, if there were, then this show an attack on the standard (no key bits leaked) AES, because what an attacker could do is go through all possible $2^{8n}$ settings of those key bits, assume those, and run his 'less-than-brute-force' attack on the remaining key bits. If this attack (when his guess for the 'known' key bits is correct) takes an expected time of less than the time taken to compute $2^{128 - 8n-1}$ AES evaluations, then the total time will take less than the time taken to do $2^{128-1}$ evaluations, that is, it shows that there is a faster-than-generic attack

$\endgroup$
  • 1
    $\begingroup$ But you assume known plaintext attack, while I'm talking about a decryption oracle. Well, I wouldn't be surprised if this doesn't change much here, but nevertheless, your answer doesn't address it. $\endgroup$ – enedil Dec 21 '18 at 22:50
  • $\begingroup$ @enedil We kinda assume known plaintext attacks by default when addressing this kind of issue, but you're right, it does seem to be missing. $\endgroup$ – Maarten Bodewes Dec 21 '18 at 22:52

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.