Characteristics of the data integrity check algorithm based on additive generators and $s$-boxes

V. M. Fomichev ; A. M. Koreneva ; T. R. Nabiev

Prikladnaya Diskretnaya Matematika. Supplement, no. 13 (2020), pp. 62-66

Résumé

During software analysis, the integrity control of large data arrays is relevant. In solving this task it is important to provide an acceptable compromise between cryptographic properties of the integrity check algorithm and the resources necessary for its implementation. We propose the algorithm for generation of 128-bit integrity check value (ICV) for data blocks of size 1 KB (1024 bytes). This algorithm provides positive (from the synthesis position) operational and cryptographic properties and uses the transformations of additive generators and $s$-boxes. The algorithm is implemented by the function $\psi(g^t)\colon V_{2^{13}}\to V_{128}$ with the full mixing of the input data. For $6\le t\le 100$, each bit of the ICV essentially depends on all the bits of the input block. If you randomly choose the initial state $u$, the probability of obtaining the corresponding ICV code $Q$ is estimated by $2^{-128}$. The average number of the tested pairs of blocks $(u,u')$, where $u\ne u'$ and $Q(u)=Q(u')$, is approximately equal to $2^{64}$. The computational complexity of the function $\psi(g^t)$ is in the order of $t(5u+8v)$, where $u$ is the computational complexity of adding two numbers modulo $2^{64}$, and $v$ is the computational complexity of the $s$-box calculation. According to the conducted experiments, the speed of ICV generation varies from 3500 ($t$=6) to 250 Mbit/s ($t$=96), respectively. At the same values of $t$, the time of ICV generation varies from 18 to 250 $\mu s$.

Détail

Keywords: additive generators, data integrity control, matrix-graph approach, mixing properties, shift registers.