Attacking AES using Round 1 output

Question

I was reading the paper Differential Scan Attack on AES with X-tolerant and X-masked Test Response Compactor and I have a question in the section Differential Scan Attack on AES.

What I understand is that they precomputed the distribution of Hamming distance for the input difference 1. It is observed that the Hamming distance values of 9, 12, 23 and 24 correspond to unique output vectors.

So as an attack you try various input vectors with difference 1 and when the output vectors have a Hamming distance corresponding to one of these values you have hit the jackpot because you know what input vectors (to the S-box) produce these unique output vectors. As an example, they have mentioned the Hamming distance 9 and they say that the only possible inputs for the S-box are either 0xE2 or 0xE3.

What I am unable to figure out is how they were able to calculate the values 0xE2 and 0xE3. The best way I can think of is by trying all possible values. This may work in this case because the output vectors have a unique Hamming distance, but I doubt it would work in other cases (say for output vectors with Hamming distance 5).

I want to know if there is a smarter way to figure out these values?

Answer 1

Thanks to @kelalaka for pointing me in the right direction.

Let's say you're interested in finding all input pairs $(b^{i}_1, b^{i}_2)$ to the S-box for the input difference $k$ which generate some Hamming distance $l$. Here's how you do it :

1. Generate all input pairs such that $b^{i}_2 = b^{i}_1 \oplus k$
2. Find out the corresponding output pairs $(f^{i}_1, f^{i}_2)$ and the Hamming distance between these pairs $l_j$.
3. Collect all the input pairs $(b^{i}_1, b^{i}_2)$ for the Hamming distance $l$