🚱 😲 ➰ How S-boxes are created 🤙🏾 🧡 👨🏿‍💼

Symmetric key encryption is ubiquitous in today's world - storing and transmitting information, email, even watching videos on YouTube. Strong symmetric ciphers include well-formed S-boxes. In this post, I'll walk you through the different ways to create S-boxes and compare them.

1. What is S-block

S-block is a function that takes n bits at the input, transforms them according to a certain algorithm and returns m bits at the output. S-boxes are widely used in most block ciphers. They can differ in input and output sizes (n and m), can be generated deterministically or randomly, and can also be immutable (fixed) or generated based on a key. S-boxes can be represented either as a table (as in DES) or as an algebraic Boolean function (as in AES). Important criteria when composing an S-box are its nonlinearity and the criterion for the propagation of Boolean functions. In order to view the S-box as a sequence of Boolean functions, we first understand how Boolean functions generally relate to cryptography.

2. Boolean functions in cryptography

In traditional encryption systems that translate an open message into one encrypted with a secret key, the apparatus of boolean functions is very widely used. The main requirement for them is that they complicate the decoding of the message by a person who is not its addressee.

To illustrate the use of Boolean functions, we present a stream encryption scheme, when each incoming character is immediately converted into a ciphertext character. The original text, key and ciphertext are binary strings of the same length. In practice, most often the sender and the recipient choose a pseudo-random sequence instead of a key in the Vernam cipher, which is generated from a short secret key according to the agreed algorithm. This sequence is called keystream or gamma .

, (Linear Feedback Shift Register, LSFR).

. ( ) ( ). LSFR , , LSFR.

, , L. L_i , L_1 + L_2 + ... + L_n = L , .

, .

3.

F_2 - 2 ( $\ {0, 1 \}$ ), F_2 ^ j - j - F_2 .

S- $s \ times t$ :

$S: F_2 ^ {s} \ longrightarrow F_2 ^ {t}$

$f: F_2 ^ {s} \ longrightarrow F_2$

, S- :

$f_i: F_2 ^ {s} \ longrightarrow F_2, i = 1, 2, ..., t$ - ( x_1, x_2, ..., x_s ). y_z = f (x_1, x_2, ..., x_s) .

$[y_0, y_1, ..., y_ {2 ^ {s} minus 1}]$ .

( ) 2 ^ s :

$\ displaystyle f (x) = a_o \ oplus \ sum_ {i = 1} ^ {s} a_ {i} x_ {i} \ oplus \ sum_ {1 \ leq i <j \ leq s} {} a_ {ij} x_ {i} x_ {j} \ oplus ... \ oplus a_ {12..s} x_ {1} x_ {2} ... x_ {s},$

$\ sum$ 2.

, :

$f(x_1, x_2, ..., x_{s}) = a_{0} \oplus a_{1}x_{1} \oplus a_{2}x_{2} \oplus ... \oplus a_{s}x_{s}, a_{i} \in F_{2}.$

, () . "".

4.

$f: F_2^s \longrightarrow F_2$ , , .

$x \in F_2^s$ , hwt(x) - . $f, g: F_{2}^{s} \longrightarrow F_2$ :

$\displaystyle d(f, g) = \sum_{x \in \{ 0, 1 \}^s}f(x) \oplus g(x).$

( ord(f) f(x) - a_J , - $\{1,2,...,s\}$ . - , a_0 . a_1, a_2, ..., a_s - , $a_{12}, a_{13}, ..., a_{(s-1)s}$ - . - 2^s .

( ) $\sigma_{i}(f)$ . , ,

$\sigma_{i}(f) = \binom{s}i.$

X_s

$\displaystyle \delta(f) = min_{g \in X_s} d(f, g).$

A_s - $g \in A_s.$ N_f,

$\displaystyle N_f = min_{g \in A_{s}} d(f, g).$

, $\displaystyle N_f \leq min_{g \in A_{s}} d(f, g).$ - , $N_f = 2^{s - 1} - 2^{s/2 - 1}$ . -.

- .

5.-

- - , . - .

, -, .

$N_0[y_0, y_1, ..., y_{{2^s} - 1}]$ - $[y_0, y_1, ..., y_{2^s - 1}]$ , $N_1[y_0, y_1, ..., y_{2^s - 1}]$ - . , $N_0[y_0, y_1, ..., y_{2^s - 1}] = N_1[y_0, y_1, ..., y_{2^s - 1}]$ .

$f: F_2^{s} \longrightarrow F_2$ , $f(x) \oplus f(x \oplus \alpha)$ $\alpha \in F_2^{s}$ , $1 \leq hwt(\alpha) \leq s$ . $\frac{1}{2}$ .

6. -

6.1

B_s - .

: $a, b \in B_6, a \neq b$ .

: - B_8 - 8 .

: $g: F_2^8 \longrightarrow F_2$ , :

$\begin{equation*} g(x_0, ..., x_7) = \begin{cases} a(x_0, ..., x_5), x_6 = 0, x_7 = 0\\ a(x_0, ..., x_5), x_6 = 0, x_7 = 1\\ b(x_0, ..., x_5), x_6 = 1, x_7 = 0\\ b(x_0, ..., x_5) \oplus 1, x_6 = 1, x_7 = 1 \end{cases} \end{equation*}$

: - a(x) , b(x) c(x) , $a(x) \oplus b(x) \oplus c(x)$ - -.

: - s+2 .

$g(x, x_{s + 1}, x_{s + 2}) = a(x)b(x) \oplus b(x)c(x) \oplus c(x)a(x) \oplus [a(x)b(x)]x_{s + 1} \oplus [a(x) \oplus c(x)]x_{s + 2} \oplus x_{s + 1}x_{s + 2}$

( -) s+2 . . 4 6 . - "" (, ), .

: $\pi: F_2^{s/2} \longrightarrow F_2^{s/2}$ , $g: F_2^{s/2} \longrightarrow F_2$ , - .

: - $f_M:F_2^{s} \longrightarrow F_2$ , .

: $f_M(x||y) = \pi(x) * y \oplus g(x),$ $x, y \in F_2^{s/2}$ , - $(a_{s/2 - 1}, a_{s/2 - 2}, ..., a_0) * (b_{s/2 - 1}, b_{s/2 - 2}, ..., b_0) = a_{s/2 - 1}b_{s/2 - 1} \oplus a_{s/2 - 2}b_{s/2 - 2} \oplus ... \oplus a_0b_0$

(a_0, a_1, ..., a_7) - $\{0, 1, ..., 7\}$ . $\ widehat {f} (x_0, x_1, ..., x_7) = f_ {M} (x_ {a0}, x_ {a1}, ..., x_ {a7}),$ f_M - , -. .

6.2 -

"" - , . , , , .

, - 6 . . . - , , - .

- , . - s / 2 , - s / 2 . .

s / 2 . , , . , , .

, .

- -, -. . . - ( ).

- , - . , , - .

. -, (i> 2) - . (, 6 s = 8, i = 3, 4 ). -, - .

4. ( -)

- ( - )
, $0 \ leq s / 2$ $cmin_ {ord}$ $cmax_ {ord}$ ,

$0 \ leq cmin_ {ord} \ leq cmax_ {ord} \ leq \ binom {s} {ord}.$

(1.1) (1.2) , $0 \ leq ord \ leq s / 2$ :

- $f_ {ANF}$
$f_ {TT}$ .

(1.1) (1.2) , $0 \ leq ord \ leq s / 2$ :
- 1.1 $c_ {ord}$ , $cmin_ {ord} \ leq c_ {ord} \ leq cmax_ {ord}$ ,
  
  1.2 1 .
$f_ {ANF}$ $f_ {TT}$ .
$f_ {TT}$ .
, (3), $2 ^ {s -1} - 2 ^ {{s / 2} - 1}$ , $f_ {TT}$ $f_ {ANF}$ - -, ; (1).

, 4 . - (. - ), (4) - , , .

7. S-

S- - $S: F_2 ^ s \ longrightarrow F_2 ^ t$ , S (x_1, x_2, ..., x_s) = (f_1 (x_1, x_2, ..., x_s), f_2 (x_1, x_2, ..., x_s), ..., f_t (x_1, x_2, ..., x_s)) , , . ,

$N_S = min \ {N_ {f_ {J}} | f_ {J} = \ sum_ {i \ in J}, J \ subseteq (1, 2, ..., t) \}.$

S-, . S-.

S-, 8- .

1. S-, ,

2. S-, ,

1 2, , S-, , S- (98 100).

3. S-, ,

, S- , S- - ( 2) (. 3). , 98, S- .

4. S-, -,

S-, - (. 4). S- 112, $5\%$ ( , 104). 20 S- 100, S-, - .

, - S- .

, , - S- (80, ). S- (, ) S- .

8.

, S- . , , . S-, -.

. -
Anna Grocholewska-Czurylo and Janusz Stoklosa - Random Generation of S-Boxes for Block Ciphers
Meier, W., Staffelbach, O - Nonlinearity criteria for cryptographic functions
Wikipedia - S-box (computer science)
Wikipedia - S-box
Wikipedia - Bent functions

How S-boxes are created

1. What is S-block

2. Boolean functions in cryptography

3.

4.

5.-

6. -

6.1

6.2 -

7. S-

8.

More articles: