# 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

## 1 Answer

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.

-