# Why do block ciphers need a non-linear component (like an S-box)?

Why is there a requirement of "Non-Linear functions" as a component of many popular block ciphers (e.g. the S-box in DES or 3DES)?

How does it make the cipher more secure?

The only intuition I have is a non linear function can have many roots (solutions). E.g. for a non linear $y = F(x)$, if attacker knows $y$ to find out the $x$, there might be many choices which satisfy $y= F(x)$ hence it adds up complexity at attacker's end when he tries to make his way back (trace back) from cipher text to plain text.

Any references or detailed material are appreciated.

-

1
– duskwuff Jun 6 '12 at 4:48
Welcome to Cryptography Stack Exchange. Your question was migrated here because of being not directly related to IT security (the topic of IT Security Stack Exchange), and being fully on-topic here. Please register your account here, too, to be able to comment and accept an answer. – Paŭlo Ebermann♦ Jun 6 '12 at 19:34

2
It's important to note that combining two operations which are linear in different fields, can be non linear. For example addition in GF(2^32) aka 32 bit integer addition and addition in GF(2) aka XOR is a common choice. – CodesInChaos Jun 7 '12 at 1:51

1
@David: If you combine functions linear of the same field you get again a function linear over that field, and linear equations are easy to solve. So you do need something non-linear to make solving difficult. Non-linear does not necessarily mean that there are several solutions (looks like you think of polynomials over the complex numbers). For the AES the S-Box is a permutation, so there exists always exactly one solution $x$ for $y = S(x)$. – jug Jun 7 '12 at 10:33

1
So, we use addition in different rings. The ring $\mathbb Z/2^{32} \mathbb Z$ (integers modulo $2^{32}$) is not a field, although it has the same number of elements as $GF(2^{32})$. – Paŭlo Ebermann♦ Jun 7 '12 at 18:52
show 3 more comments

## 2 Answers

Here's the cryptography theory perspective.

We want block ciphers to resemble pseudo-random permutations (PRPs). PRPs are a desirable modeling goal because a block cipher under a given key is a permutation on the input, and a PRP is simply a random collection of permutations. The block cipher's key can never be better at creating permutations than an actual random sampling of them, but we want it to be as close as possible. Detectable deviation from PRP-like behavior is considered a weakness in a block cipher.

To compare a block cipher to a PRP we use the CPA model, where an attacker queries a black box with plaintext and receives the corresponding permuted output. They try to determine if the black box is choosing the ciphertext output by apply a random permutation or the given block cipher with an unknown key to the plaintext. If they guess correctly they win the game. If they can win the game with probability greater than 50% then they've broken the block cipher. (Look at these notes, pages 1 - 8, specifically 7, for a picture and more precise definition of this model.)

An attacker can distinguish a block cipher from a PRP if said block cipher has linear properties. They can learn those linear properties then query the black box with plaintexts that should produce certain properties in the ciphertext. If the black box replies back with ciphertext that matches those expected properties for more than 50% of the input queries, then the attacker guesses that the black box houses the block cipher because a random permutation would honor those linear properties with only 50% probability. (Otherwise, they guess that the black box is using a random permutation.) Then the attacker wins the distinguishing game.

Of course, if you're looking for a practical reason, this raises the question of why we care about PRP models to begin with.

-

Hi B-Con thanks for the elaboration on the Block Cipher and PRP. i agree with the model you have presented but my basic query is how in the construction of these block ciphers non linearity play a role. – David Jun 9 '12 at 6:09

If a block cipher is linear with respect to some field, then, given a few known plaintext-ciphertext pairs, it is possible to recover the key using a simple Gaussian elimination. This clearly contradicts the security properties one expects from a secure block cipher.

-
{"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": 9, "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": true}, "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.9125620126724243, "perplexity_flag": "middle"}