26
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Not an answer, but a pointer in the right direction: en.wikipedia.org/wiki/Linear_cryptanalysis $\endgroup$
    – duskwuff
    Commented Jun 6, 2012 at 4:48
  • $\begingroup$ 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. $\endgroup$
    – Paŭlo Ebermann
    Commented Jun 6, 2012 at 19:34
  • 3
    $\begingroup$ 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. $\endgroup$
    – CodesInChaos
    Commented Jun 7, 2012 at 1:51
  • 1
    $\begingroup$ @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)$. $\endgroup$
    – j.p.
    Commented Jun 7, 2012 at 10:33
  • 1
    $\begingroup$ 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})$. $\endgroup$
    – Paŭlo Ebermann
    Commented Jun 7, 2012 at 18:52

3 Answers 3

Reset to default
17
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – David
    Commented Jun 9, 2012 at 6:09
25
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

Almost all block cipher performs some types of substitution and permutation in every round function. For AES, ShiftRow, MixColumn, AddRoundKey are linear operations; only S-box operation is a nonlinear operation. If all operations in a round function are linear then there is no advantage of having multiple(10,12,14) iterative encryption rounds to produce the ciphertext from the plaintext. Because all linear operations can be replaced by just a single linear operation. Which is same as the AES encryption can be replaced with a single function. More importantly when the attacker has plenty of plaintext and ciphertext pairs with the derived linear function, it can perform Gaussian elimination for the key.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.