AES 5-round Square attack, how to choose plaintexts?

Question

I know that we need to generate a delta-set (with 256 plaintexts).

During the attack, we guess 4 bytes of round 5 key and 1 bytes of round 4 key, which allows us the byte at one position of the state at the end of round 3. If that position is balanced, then the 4-byte prediction is valid, but there are a lot of false-positives.

My problem is that there are too many false positives. No matter what delta-set I generate, all remaining 4-byte combination result in a false-positives.

How can I generate the input plaintexts to eliminate these false positives? I can't find a single implementaion of AES Square attack online, so if anyone can show me, I'd be very grateful.

Thank you.

Edit: nevermind. On average 5 delta-sets or less is needed. I just had a data-type bug (char -> unsigned int) that make the program fail to eliminate delta-set

Answer 1

In statistical attacks (such as square), if we can reduce the key space, it will be considered successful. Here, as you pointed, there are false-positives and they should be considered as correct key candidates. But the point is that the distinguisher has removed some incorrect keys and has reduced the key search space. After finding candidates for the correct key, you should do exhaustive search among them or try other attacks to even reduce the key space further! Here, choosing the plaintexts does not have that much effect on the false positive, since different keys will change the chosen set differently.