0
$\begingroup$

I hope somebody can help me understand the design criterias for AES. Therefore, I would be really thankful if somebody could explain "non-linearity" in this context.

A criteria for the s-box in AES is non-linearity, where the maximum input-output correlation amplitude must be as small as possible. Why is a look-up table non-linear?

The maximum difference propagation probability must be as small as possible. This means to get closer to a uniform distribution?

MixColumns offers linearity - because it is a function which transforms values in a deterministic way?

|improve this question
$\endgroup$
  • 1
    $\begingroup$ I suggest a look at this $\endgroup$ – fgrieu Sep 20 '12 at 9:39
2
$\begingroup$

Generally speaking, a function $f()$ is linear if $f(x+y) = f(x)+f(y)$ and $f(ax) = af(x)$.

The AES S-Box, which is a specific, predefined (key-independent) lookup table, doesn't satisfy these properties. You can do a quick verfication by picking two values $x,y \in GF(2^8)$ and verifying that $S(x+y) \neq S(x)+S(y)$ (where the addition operation is done in the field $GF(2^8)$, and is thus essentially the XOR operation). But the S-Box not being fully linear is not enough. It's very bad if it's just somewhat linear, in the following sense. There are various ways to define it. One of them is the Linear Property of the S-box, $LP(S) = \max_{a,b} (Pr_x(a(S(x)) == b(x)) - \frac{1}{2})^2$ which has to be low. It measures the existence of two linear functionals $a(),b()$ which tend to agree (correlate) or disagree on the input and output of the S-box. If you were to calculate $LP(S)$ you would find that it is considerably lower than for a random lookup table ("the maximum input-output correlation amplitude must be as small as possible").

As for difference propagation, a similar property exists $DP(S) = \max_{a,b\neq0} (Pr_x(S(x)\oplus a == S(x \oplus b)))$, which measures the existence of two differences (deltas) $a,b \neq 0$ which propagate through the S-box. Again this has to be minimal, and if you were to calculate $DP(S)$ you would find it is indeed lower than for a random lookup table.

MixColumns offers linearity because it is defined as a linear mathematical operation, not because it is deterministic (the S-Box is also deterministic, but not linear...).

|improve this answer
$\endgroup$
  • $\begingroup$ The definition of linear given is valid in some context, but not cryptanalysis. In particular, $f(x)=x+1$ is not linear by that definition. I have seen $\exists k, \forall(x,y), f(x+y)=f(x)+f(y)+k$. $\endgroup$ – fgrieu Sep 20 '12 at 10:28
  • $\begingroup$ Agreed. This is why I started with that definition but then later on moved to the Linear Property (LP) of the S-Box. Even if a function is not linear (in your definition too) it can still be "almost linear" (high LP value) and what would be bad. $\endgroup$ – Harel Sep 20 '12 at 10:34
  • $\begingroup$ thank you for every answer so far! I think i got the difference between non-linearity and linearity. but can u tell me why which technique is where applied and how security can be achieved because of this!?! $\endgroup$ – tom Sep 20 '12 at 13:07
  • 1
    $\begingroup$ @tom: the combination of linear transformations (like MixColumns) is a linear transformation, and if some other non-linear transformation was not included in AES, the overall AES transformation would be linear. That would be very bad (cryptanalysis is trivial for a linear transformation, and possible for a close-enough-to-linear transformation). The introduction of the non-linear S-boxes breaks the linearity. To some degree (which I do not quite grasp) this qualitative reasoning can be formalized in a quantitative manner. $\endgroup$ – fgrieu Sep 20 '12 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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