Take the 2-minute tour ×

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?

share|improve this question
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 1

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.

share|improve this answer

Your Answer


