# Given partial key exposure and encryption oracle, can we recover full AES key?

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}$$?

• @kelalaka but this is not faster than $256^{16-n}$ (I corrected myself). – enedil Dec 21 '18 at 21:37
• 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. – kelalaka Dec 21 '18 at 21:41
• @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$. – enedil Dec 21 '18 at 21:51
• Bitcoin mining reached $\approx 2^{91}$ SHA-256 mining in one year. Summit can reach $2^{73}$ in one year. – kelalaka Dec 21 '18 at 21:56
• @kelalaka I mean breaking it by myself :c – enedil Dec 21 '18 at 22:05

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