S-boxes algorithmic realization based on modified additive generators

V. M. Fomichev ; D. M. Lolich ; A. V. Yuzbashev

Prikladnaya Diskretnaya Matematika. Supplement, no. 10 (2017), pp. 102-104

Résumé

$S$-boxes give the properties of non-linearity and diffusion to cryptosystems and are essential parts of symmetric iterative block ciphers. Usually, they are described as vector Boolean functions and are represented by a memory-consuming tables limiting the practical size of them ($6\times4$ bits in DES cypher, $4\times4$ bits in GOST cypher, $8\times8$ bits in Kuznyechik cypher). In this paper, we present an algorithm for constructing $s$-boxes (including large ones) using modified additive generators (MAG). The required cryptographic properties of the created substitutions follow from algebraic and mixing properties of MAG and are determined in experiments with a software implementation of the algorithm. Each created substitution $s$ on $V_n$ is tested to determine whether it has the following desirable properties: 1) essential dependence of coordinate functions of $s$ on all their variables; 2) non-linearity of all the non-zero combinations of the coordinate functions of $s$; 3) nearness of the difference characteristics $p_s$ to a random value, where $p_s=\max_{\alpha,\beta\in V_8}|\{x\in V_8\colon s(x)\oplus s(x\oplus\alpha)=\beta\}|$. As a result of the research, $2^{19}$ $s$-boxes $8\times8$ were created using MAG with several selected $s$-boxes $4\times4$. Almost all of them satisfy requirements 1 and 2. For a large number (several thousands) of constructed $s$-boxes $8\times8$, $p_s=10/256$, and four $s$-boxes have $p_s=8/256$. The results show that the presented method is capable of constructing large and cryptographically strong $s$-boxes.

Détail

Keywords: modified additive generator, s-box, shift register.
Mots-clés : MAG