Best complexity of guessing difference of AES-256 outputs

Suppose we have two plaintexts $m_1$ and $m_2$ such a way that $|m_1| = |m_2| = 128 $ and these two plaintexts are different just in one bit. Now suppose we know the value of $c_1 = AES_{k}(m_1)$($|k| =256$) .

What is the best complexity of guessing difference $c_1 \oplus c_2 = ?$ with probability at least $\frac{1}{2}$ by considering that we don't know the values of $c_2$ and $k$.

Without further information, your question is overwhelmingly likely to be insoluble.

Given $m_1$, $m_2$ and $c_1$ we expect there to be roughly $2^{128}$ 256-bit keys $k$ such that $\mathrm{AES}_k(m_1)=c_1$. These keys are then likely to produce $(1-1/e)2^{128}$ different possible encryptions of $m_2$ of which the most likely value will occur roughly $128/7$ times. Picking $c'_2$ equal to this most popular value and then guessing $c_1\oplus c'_2$ is the most likely to succeed, but the probability of success is about $2^{-124}$ which is hugely far from 1/2.

Note that this strategy takes work roughly equal to $2^{256}$ AES evaluations.

See Daniel S's more complete answer. I missed the 256 bit key part.

Your best bet would be differential cryptanalysis.

Taking this as "best for the cryptanalyst", the AES Sbox difference distribution table has output differences with probability $4/256=2^{-6}$ for each input difference, including one of weight exactly 1, which is your case.

Continuing on, what needs to be done is essentially the same analysis as a typical differential attack on AES, since the shift rows followed by mix columns will do their job of diffusing the effects.

Such an attack has not been demonstrated that is better than brute force complexity of $2^{128},$ to the best of my knowledge. The plaintext/ciphertext pair requirement will also be essentially as large as $2^{128}$, but I am willing to be proved wrong on this. In any case that won't be much better than $2^{128}$ either.

In a recent question the answer referred to biclique cryptanalysis with complexity better than brute force complexity. Even that attack which is the best known has complexity $2^{127}$ or so, and data requirement (amount of plaintext/ciphertexts) are much less.

So you might as well do a brute force key search with a few plaintext ciphertext pairs.