# What is the complexity of the Square attack against the reduced 4-rounds 128-bit Rijndael variant?

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?

-
Why don't you show us the work you've done so far? You might also want to check out the FAQ, particularly the section titled "Do we accept basic level/homework questions?" and the resources linked to from there –  D.W. Oct 28 '12 at 4:09
Welcome to Cryptography Stack Exchange. Please note that the question titles should at least sound something like a question – what you put there would better be tags. I edited your question to use these tags, gave a better title and tried to edit the question to say what I understood you wanted to say. I hope I understood this right – feel free to edit this again (there is an edit button). Also, have a look at D.W.'s comment, and add the necessary information. –  Paŭlo Ebermann Oct 28 '12 at 14:02

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.