# 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?

-

– 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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 18, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9390266537666321, "perplexity_flag": "middle"}