I'm looking at a square attack against a reduced version of AES-128 with only 4 rounds (with block and key size of each 128 bit). I have a set of 256 plaintext-ciphertext block pairs.
What is the complexity of the computations, in number of encryptions, partial encryptions, memory usage, and data requested?
There are two well-known distinguishers of reduced-rounds version of AES based on integral cryptanalysis. The first one is a 3-rounds distinguisher from Daemen and Rijmen while the other is a 4-rounds distinguisher from Gilbert and Minier.
The 3-rounds distinguisher relies on the fact that one byte $y$ of the state in the third round is the xor of four one-to-one mappings $z_i:x\mapsto z_i(x)$ from a given byte $x$ in the state of the first round, and therefore, on the property that $\sum_{x\in GF(2^8)} \left[z_1(x)+z_2(x)+z_3(x)+z_4(x)\right]$. Hence, the distinguisher requires $2^8$ (well crafted) plaintexts and as many encryptions, but basically no memory.
The 4-rounds distinguisher relies on the fact that the above-mentioned byte $z$ is actually a function of $x$ and three constants $c_1$, $c_2$, $c_3$ hereafter referred to as $c$ and the probability that there is an unusually high chance that the functions $z_{c'}$ and $z_{c''}$ are equal: this can be tested through the equality of the linear combination of four bytes resulting from the encryption of the two corresponding plaintext. The property is observable after browsing through $2^{16}$ values of $c$ (and enough of the possible values for $x$). Hence, the disinguisher requires about $2^{20}$ plaintexts and as many encryptions as well as less than $2^6$ bytes of memory.
These distinguishers are meant to be turned into key recovery attacks, but these extend to at least 6-rounds AES. Since you mentionned 4-rounds attacks without further details, I assume you referred to one of the above. If you need a more precise answer, you should refine your question. Also, make it precise which version of Rijndael you're referring to as it may impact the underlying complexity.
