5
$\begingroup$

S-box has to satisfy different design criteria. How to calculate non-linearity , propagation criteria for an AES S-box?

$\endgroup$
9
$\begingroup$

The non-linearity of an s-box is related to its linear approximation table.

For an $n$-bit input x $m$-bit ouput s-box the LA table is a $2^n$ x $2^m$ table. In the case of AES this is a 256x256 table. The entries of this table represent the difference between how many matches are found and how many are expected for a linear expression of the s-box boolean functions given an input/output mask pair. The expected value is half of all combinations match, which would be a value of 0. A value that differs from 0 means that combination is more likely to be either a 0 or a 1, resulting in a bias.

The linearity of an $n$ x $n$ s-box $S$ such as AES is the maximum distance from 0 in the LA table for input and output masks not equal to 0 (nonzero linear combination), which is 65025 out of 65536 entries for an 8x8 s-box. For AES the maximum value is +128 (256 matches) for a 0 mask, and +/-16 (112 or 144 matches) for a non 0 mask, therefore $lin(S)$ = 16.

For an $n$ x $n$ s-box $S$ such as AES, the non-linearity is $2^{n-1} - lin(S)$, which for AES is 112. All 8x8 s-boxes created using Galois Field inversion plus an Affine Transform have the same non-linearity, as the Affine Transform does not change the linear or differential properties. In practice, the LAT is calculated much faster than testing linear expressions per mask 1 at a time by using something called a Walsh Hadamard Transform.

Propagation is related to avalanche. If a specific bit changes to the s-box input, then of the $m$ output bits, they should change with probability of exactly $1/2$ for all inputs and all changed bits. If an s-box meets this, it meets the 1st order Strict Avalanche Criterion (SAC). In reality, very rarely (never) does this happen, so we want it to happen with probability of $1/2$ or higher, with the probability being as close to $1/2$ as possible, and the combined difference in probabilities being as small as possible (Distance to SAC (DSAC)). Functions that do meet SAC are generally not suited for cryptographic use, as they do not meet other required properties, such as to resist differential analysis.

There are 8 input bits in the AES s-box, there are 8 1-bit masks for 256 inputs, 8 output bits, resulting in 2048 8-bit values being tested, and 64 compared values of s-box output bits to 1-bit masks. AES meets probability $1/2$ or higher for $43/64$ bitmask/outbit combinations, with a min difference of 12 bits for those that do not, and a max difference of 16 bits for those that do. DSAC is 432 bits.

Higher orders of SAC use larger input masks. For 2 or 6-bit masks there are 28 combinations, for 3 or 5-bit masks there are 56 combinations, for 4-bit masks there are 70 combinations, and for 7-bit masks there are 8 combinations. The $k$-th order SAC is met if for a $k$-bit mask, the output bits change with probability of exactly $1/2$. For 2nd order SAC, AES meets probability $1/2$ or higher for $127/224$ bitmask/outbit combinations, with a min difference of 16 bits for those that do not, and a max difference of 16 bits for those that do. 2nd order DSAC is 1664 bits.

Propagation extends to ALL combinations of input bit masks of $1$ to $n-1$ bits. An s-box is said to meet $k$-th order Propagation Criterion if SAC is met for all orders {$1 .. k$}. 3rd order PC would mean 1st 2nd and 3rd order SAC are met. Maximum order PC means all orders of SAC are met. Once again, this is not likely to occur, so we try to target SAC orders with the probabilities closest to half, and with the smallest difference from SAC. Unlike linearity, the affine transform of AES has dramatic changes on SAC test results, although there are groups of AES-like s-boxes with different affine transformations that have the same results. These groups are called Affine Equivalence Classes, with each group having identical results in a variety of other tests as well.

$\endgroup$
  • $\begingroup$ i sincerely thanks for elaborated explanation... i am trying to find mathematical view for calculating SAC, non linearity? so, i can apply to any expression. could you give me any source of information? $\endgroup$ – venkat Nov 3 '14 at 16:15
  • $\begingroup$ It is possible that Oleksandr Kazymyrov's s-box addin for Sage can do it, I use my own program to analyze 8x8 s-boxes. github.com/okazymyrov/sbox $\endgroup$ – Richie Frame Nov 3 '14 at 20:28
  • $\begingroup$ @RichieFrame As pointed out in the answer "The linearity of an n x n s-box S such as AES is the maximum distance from 0 in the LA table for input and output masks not equal to 0 (nonzero linear combination), which is 65025 out of 65536 entries for an 8x8 s-box.". What is the distance metric in the consideration ? is it the hamming distance of zero with the entry in LAT for non-zero masks? if not how do i calculate this distance? $\endgroup$ – Shubham Singh rawat Mar 18 '18 at 18:42
  • $\begingroup$ @ShubhamSinghrawat see the prior paragraph, the distance is the difference from expected matches. if there were less matches the value is negative. the expected value is half all combinations, which is 128/256 for all table entries, except for the 511 which have a 0 combination value $\endgroup$ – Richie Frame Mar 19 '18 at 3:51

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.