S-box Analyzer Web Version

With the website we have prepared to evaluate the cryptographic security of S-boxes, you can have your S-boxes analyzed according to five basic criteria such as non-linearity, bit independence criterion (BIC), strict avalanche criterion (SAC), differential uniformity and linear uniformity. This tool helps you test the resilience of your S-boxes against various types of attacks.

For testing example s-box(AES S-box as integer):

1. Non-linearity

Non-linearity is a measure of how much an S-box deviates from being a linear or affine function. A high degree of non-linearity is desired in cryptographic applications because it enhances the resistance of the S-box to linear cryptanalysis. Linear cryptanalysis involves approximating the behavior of a cryptographic algorithm using linear equations, and high non-linearity ensures that such approximations are difficult to find.

Formula: The non-linearity

N_{f}

of a Boolean function

f

is defined as the minimum Hamming distance between the function

f

and all affine functions

A

. Mathematically, this can be expressed as:

N_{f} = min_{A} {d_{H} (f, A)}

where

d_{H}

denotes the Hamming distance, which is the number of positions at which the corresponding bits are different between two binary sequences.

For an S-box

S

mapping

n

input bits to

m

output bits, the non-linearity of each output bit function

f_{i}

(where

S (x) = (f_{1} (x), f_{2} (x), \dots, f_{m} (x))

) is calculated, and the overall non-linearity of the S-box is often considered as the minimum non-linearity among these functions.

To calculate the non-linearity of a Boolean function

f

, you can use the following steps:

Compute the truth table of $f$ .
Construct all possible affine functions of the same dimension.
Calculate the Hamming distance between $f$ and each affine function.
The smallest Hamming distance obtained is the non-linearity of $f$ .

The formula for the Hamming distance

d_{H}

between two binary sequences

x

and

y

of length

n

is:

d_{H} (x, y) = \sum_{i = 1}^{n} (x_{i} \oplus y_{i})

where

\oplus

denotes the XOR operation.

In practice, the calculation of non-linearity for an S-box involves examining each output bit function, as well as considering the overall structure of the S-box to ensure high resistance to linear attacks.

2. Strict Avalanche Criterion (SAC)

The Strict Avalanche Criterion (SAC) is a measure of how each output bit of an S-box changes when a single input bit is flipped. Specifically, SAC requires that, on average, flipping any single input bit should change each output bit with a probability of 0.5. This ensures that small changes in the input produce widespread changes in the output, enhancing the diffusion properties of the S-box.

Formula: To evaluate the SAC for an S-box, consider the following:

Let $S$ be an S-box mapping $n$ -bit inputs to $m$ -bit outputs.
Denote the output bits of $S$ as $(f_{1} (x), f_{2} (x), \dots, f_{m} (x))$ for an input $x$ .

For each output bit

f_{j} (x)

, calculate the probability that it changes when a single input bit

x_{i}

is flipped:

P (f_{j} (x) \neq f_{j} (x \oplus e_{i})) = \frac{1}{2^{n}} \sum_{x \in {0, 1}^{n}} (f_{j} (x) \oplus f_{j} (x \oplus e_{i}))

where:

$e_{i}$ is the $i$ -th unit vector in $n$ -dimensional space, indicating a flip in the $i$ -th input bit.
$x \oplus e_{i}$ denotes the input $x$ with the $i$ -th bit flipped.
$\oplus$ represents the XOR operation.

To satisfy the SAC, this probability should be close to 0.5 for each output bit

f_{j}

and each input bit

x_{i}

Steps to Compute SAC:

For each output bit $f_{j}$ $f_{j}$ f_(j)f_j $f_{j}$ and each input bit $x_{i}$ $x_{i}$ x_(i)x_i $x_{i}$ :
- Iterate over all possible inputs $x \in {0, 1}^{n}$ .
- Flip the $i$ -th input bit by using the vector $e_{i}$ .
- Compute the number of times $f_{j} (x) \neq f_{j} (x \oplus e_{i})$ .
Calculate the probability for each pair $(x_{i}, f_{j})$ .
Verify that these probabilities are close to 0.5 for all pairs.

In practice, an S-box that satisfies the SAC ensures that the effect of changing a single input bit propagates to the output bits in a balanced and unpredictable manner, significantly complicating differential attacks and enhancing overall cryptographic strength.

3. Bit Independence Criterion (BIC)

The Bit Independence Criterion (BIC) assesses the independence of output bits in response to changes in the input bits. Specifically, it measures how each output bit changes independently when each input bit is flipped. High BIC values indicate that changes in one input bit affect the output bits independently, which is desirable for secure cryptographic transformations.

Formula: To evaluate the Bit Independence Criterion for an S-box, consider the following:

Let $S$ be an S-box mapping $n$ -bit inputs to $m$ -bit outputs.
Denote the output bits of $S$ as $(f_{1} (x), f_{2} (x), \dots, f_{m} (x))$ for an input $x$ .

To assess the independence, compute the correlation between output bits for each possible input bit flip:

Correlation (f_{i}, f_{j}) = \frac{1}{2^{n}} \sum_{x \in {0, 1}^{n}} (- 1)^{f_{i} (x) \oplus f_{i} (x \oplus e_{k}) \oplus f_{j} (x) \oplus f_{j} (x \oplus e_{k})}

where:

$f_{i}$ and $f_{j}$ are output bit functions of the S-box.
$e_{k}$ is the $k$ -th unit vector in $n$ -dimensional space, indicating a flip in the $k$ -th input bit.
$x \oplus e_{k}$ denotes the input $x$ with the $k$ -th bit flipped.
$\oplus$ represents the XOR operation.

The correlation should be close to zero for high independence, indicating that the output bits change independently when any single input bit is flipped.

Steps to Compute BIC:

For each pair of output bits $f_{i}$ $f_{i}$ f_(i)f_i $f_{i}$ and $f_{j}$ $f_{j}$ f_(j)f_j $f_{j}$ :
- Iterate over all possible inputs $x \in {0, 1}^{n}$ .
- Flip each input bit $k$ by using the vector $e_{k}$ .
- Calculate the correlation between the bit changes.
Analyze the correlations: lower values indicate higher independence.

In practice, an S-box with high bit independence ensures that each output bit responds independently to changes in the input bits, which is critical for preventing attacks that exploit correlations between output bits.

4. Differential Uniformity

Differential uniformity is a measure of the uniformity of the output differences resulting from input differences in an S-box. It quantifies the maximum number of times any particular output difference occurs when a specific input difference is applied. A low differential uniformity indicates strong resistance to differential cryptanalysis, a method that exploits patterns in the differences between inputs and outputs.

Formula: The differential uniformity

δ

of an S-box

S

is defined as the maximum value of the differential distribution table (DDT). The DDT records how often each output difference

Δ y

occurs for each input difference

Δ x

To construct the DDT for an S-box

S

Let $S$ map $n$ -bit inputs to $m$ -bit outputs.
Define the input difference $Δ x$ and output difference $Δ y$ as: $Δ x = x \oplus x^{'}$ $Δ y = S (x) \oplus S (x^{'})$
Count the number of pairs $(x, x^{'})$ that produce each $Δ y$ for a given $Δ x$ : $D D T (Δ x, Δ y) = | {x \in {0, 1}^{n} ∣ S (x) \oplus S (x \oplus Δ x) = Δ y} |$

The differential uniformity

δ

is then:

δ = max_{Δ x \neq 0, Δ y} D D T (Δ x, Δ y)

Steps to Compute Differential Uniformity:

Initialize a table $D D T$ of size $2^{n} \times 2^{m}$ with zeros.
For each non-zero input difference $Δ x$ $Δ x$ Delta x\Delta x $Δ x$ :
- For each possible input $x \in {0, 1}^{n}$ $x \in {0, 1}^{n}$ x in{0,1}^(n)x \in \{0, 1\}^n $x \in {0, 1}^{n}$ :
  - Compute $x^{'} = x \oplus Δ x$ .
  - Compute the output difference $Δ y = S (x) \oplus S (x^{'})$ .
  - Increment the corresponding entry in the DDT: $D D T (Δ x, Δ y)$ .
Identify the maximum value in the DDT for non-zero $Δ x$ , which is the differential uniformity $δ$ .

5. Linear Uniformity

Linear uniformity measures how uniformly the output bits of an S-box can be approximated by linear functions of the input bits. It is an indicator of an S-box's resistance to linear cryptanalysis, a method that exploits linear approximations of the relationship between input and output bits to recover secret keys. Lower linear uniformity values indicate higher resistance to such attacks.

Formula: The linear uniformity

L U

of an S-box is determined by the maximum absolute value of the correlation between linear combinations of input and output bits. This is captured using the Walsh-Hadamard transform.

For an S-box

S

mapping

n

-bit inputs to

m

-bit outputs, the linear approximation table (LAT) is used to compute these correlations:

Define the linear approximation of an input $x$ and an output $y$ as:

$L_{α, β} (x, y) = α \cdot x \oplus β \cdot y$

where $α$ and $β$ are non-zero $n$ -bit and $m$ -bit vectors, respectively, and $\cdot$ denotes the dot product.
Calculate the correlation between input and output bit combinations:

$L A T (α, β) = \sum_{x \in {0, 1}^{n}} (- 1)^{L_{α, β} (x, S (x))}$
The linear uniformity $L U$ is defined as:

$L U = max_{α \neq 0, β} | L A T (α, β) |$

Steps to Compute Linear Uniformity:

Initialize a table $L A T$ of size $2^{n} \times 2^{m}$ with zeros.
For each non-zero $α \in {0, 1}^{n}$ $α \in {0, 1}^{n}$ alpha in{0,1}^(n)\alpha \in \{0, 1\}^n $α \in {0, 1}^{n}$ :
- For each $β \in {0, 1}^{m}$ $β \in {0, 1}^{m}$ beta in{0,1}^(m)\beta \in \{0, 1\}^m $β \in {0, 1}^{m}$ :
  - Compute the sum $\sum_{x \in {0, 1}^{n}} (- 1)^{α \cdot x \oplus β \cdot S (x)}$ and store it in $L A T (α, β)$ .
Identify the maximum absolute value in the $L A T$ , which is the linear uniformity $L U$ .