how can I test quality of sbox?

I have 11 sboxes, I want to test them and find the best one. How can I do that, I found several criterions for that but I could not understand.

• Statistical testing can only show something is really bad. At best the result is "not trivially broken". But it can not prove security, and even less is it able to indicate what is the best. I am not sure, the question can be answered objectively.
– tylo
Jun 28 '19 at 20:03

I'd advise the result of Daemen and Rijmen on the matter called the wide-trail design strategy that has been used to construct the current AES. Shortly you want s-boxes that have:

High algebraic degree

If you have the ANF of the Boolean function induced by your permutation which is a polynomial $$\mathbb{F}_2[x_0,...,x_{n-1}]/(x_0^2 - x_0,..., x_{n-1}^2 - x_{n-1})$$ then the algebraic degree is the number of variables in the largest product term of the function’s ANF having a non-zero coefficient.

Balancedness

Let $$F$$ be a function from $$\mathbb{F}_n^2$$ into $$\mathbb{F}_n^2$$. $$F$$ is balanced if it takes every value of the range exactly once.

High Nonlinearity

The aggregated nonlinearity of your S-box is the minimum nonlinearity of all of it's component functions which you can get with the Walsh-Hadamard transform

Low Differential uniformity

Define the difference distribution of any a function with respect to $$a$$ and $$b$$ elements from $$\mathbb{F}_2^n$$ as $$DF(a,b) = \{x∈F_2^n:F(x)⊕F(x⊕a) =b\}.$$ Then the differential uniformity is the maximum value got with this function using any pair of $$a$$ and $$b$$.

High differential branch number

this is calculated by $$min_{x\neq y}wt(x⊕y) +wt(F(x)⊕F(y))$$ where $$wt$$ is the hamming weight.

Note that these are still a subset of all tricks used in literature used to argue about s-boxes but the wide-trail strategy is currently still a good pivot point. There are very useful tools in the SageMath library to easily check these properties: http://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/sbox.html

• I actually want to know about: Avalanche Criterion (AVA), StrictAvalancheCriterion(SAC), Bit Independence Criterion (BIC) and Non-linearity Measure (􏰣􏰤􏰥􏰦) Jun 27 '19 at 12:56
• Wide trail is (primarily) not about the S-boxes, see here. Also, some of the other criteria you mention such as the differential branch number of the S-box are not always relevant. Jun 27 '19 at 12:56
• All criteria exist in their own bubble, and it is not objectively possible to put them in relation. Some criteria are older, some imply certain qualities in other scores. If the goal is to get a comparison, the only way is to learn and understand them all in depth - arguing one criteria over the other is much less a science but a form of art. This has to take all efforts in cryptanalysis into account, and I would guess only an expert in the field can actually produce a meaningful result.
– tylo
Jun 28 '19 at 19:50

The selection criteria of best S-box depends on what you are focusing on ; Security, implementation etc. in your comment , you focused only on BIC, SAC and nonlinearity but there are some criteria recently developed in term of security along with previous criteria (Difference Distribution Table (DDT, Linear Approximation Table (LAT) , Algebraic normal form (ANF), Algebraic immunity).

in term of implementation:

• Multiplicative complexity: the smallest number of nonlinear gates
• Bitslice gate complexity: the smallest number of operations in {AND, OR, XOR, NOT} required to compute this function
• Gate complexity: the smallest number of logic gates required to compute this function
• Circuit depth complexity: the length of the longest paths from an input gate to an output gate

in FSE 2019 , P􏰀􏰁􏰂􏰀􏰃EIGEN– a Platform for Evaluation, Implementation, and Generation of S-boxes was presented with open source code, this tool will be very helpful for your analysis.