# How to calculate Correlation, Difference propagation probability and Algebraic complexity a particular S-box?

I'm learning about AES. According to the book The Design of Rijndael refers to the design criteria S-box $$S_{RD}$$ as follows:

Design criteria for $$S_{RD}$$. We have applied the following design criteria for $$S_{RD}$$, appearing in order of importance:

1. Non-linearity.

a) Correlation. The maximum input-output correlation amplitude must be as small as possible.

b) Difference propagation probability. The maximum difference propagation probability must be as small as possible.

2. Algebraic complexity. The algebraic expression of $$S_{RD}$$ in $$GF(2^8)$$ has to be complex.

How to calculate Correlation, Difference propagation probability and Algebraic complexity with a specific S-box like the S-box mentioned in Wikipedia.

If interested in computation, the sage crypto functions compute some of these for you. You can start here and explore the links on the left as well. For mathematical background read on, it has to do with Boolean functions representing the output bits in terms of the input boolean vector to the Sbox.

They Heys tutorial on linear and differential cryptanalysis available here has detailed computations of the standard Sbox quantities including difference propagation probability. You can use the sage functionalities to compute these or write your own code.

1. For Correlation Immunity (CI) and resilience (CI is the maximal nonzero weight for which all Walsh-Hadamard transform coefficients are nonzero, and quantifies resistance to divide and conquer style correlation attacks; resilience is CI plus balancedness). There is a tradeoff between CI and algebraic degree of the boolean function $$f$$, namely $$deg(f)+CI\leq n-1$$, for an $$n$$ variable boolean function, discovered by Xiao and Massey.

For more details see here

1. Algebraic complexity is a bit tricky, but the anf (algebraic normal form) is one measure. You want as many nonzero coefficients as possible.

Given the Sbox map, generate the truth tables for the bits of the map. From the truth tables, obtain the algebraic normal form, via the Mobius transform.

So, given an $$n-$$bit truth table, say $$T=[f(x): x \in \mathbb{F}_2^n]$$

where $$x=(x_1,\ldots,x_n)$$ ranges over the vector space $$\mathbb{F}_2^n$$ in standard order, the function has an anf representation given by $$f(x)=\sum_{y \in \mathbb{F}_2^n} a_y \prod_{1\leq i\leq n~:~y_i=1} x_i$$ which means the variable $$x_i$$ is included in the monomial product corresponding to the coefficient $$a_y$$ if and only if $$i$$ is in the support of the vector $$y.$$

More details are here

• Thank you very much for your answer, your answer helped me a lot. I have a little difficulty with phrases. Can you explain more to me? 1. According to the Sage page from your answer I found a function called difference_distribution_table() , this function calculates the criterion of Difference propagation probability right ? 2. The book says that the design criterion for S-box is Correlation, did the author's mean Correlation is Correlation Immunity? Correlation Immunity and Correlation are one, right? Commented Apr 11, 2023 at 11:09