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.
- 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
- 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
