# AES-256 9 round related key attack - getting possible state differences

I'm trying to implement related key attack on 9 round AES256, described here: Biryukov, Dunkelman, Keller, Khovratovich, Shamir, but I am stuck at the very beginning with Observation A, used to validate state difference before final round.

Since I have to guess byte 12 of the subkey, I can end up with impossible value of the byte 12 of the state and Observation A states, that only 127 out of 256 bytes are possible and having one of possible values, whole column of the state can be immediately recovered.

Observation A.

Consider a pair that satisfies the main differential described in Section 4.1.1. As noted above, the difference in columns 1,2,3 after the MC operation of round 7 is unknown. However, due to the properties of the SB and MC operations, there are only 127 possible values for the difference in each of these columns. Moreover, these 127 differences assume 127 different values in each of the four bytes. As a result, if the attacker knows the difference in one byte, she can obtain immediately the difference in the other three bytes of the same column, along with a one-bit filtering (since only 127 out of the 256 byte values are possible differences).

Similarly, if a pair satisfies the complementary differential described in Section 4.1.1, then if the attacker knows the difference ∆(I 7 ) in one byte, she can obtain immediately the difference in the other three bytes of the same column (though, without the additional filtering since in this case there are 256 possible differences).

It requires 'main differential' which by itself have $2^{-36}$ probability of appearing and then I would get one of 127 possible values of byte 12 and the rest of the column that comes with it. But that seems like awful lot of trouble just to get all values into the lookup table.

How is it supposed to be done? Is there somewhere an actual implementation of this algorithm? Haven't found any, but that would be very helpful.