Stochastic Data Transformation Boxes for Information Security Applications

Abstract

Stochastic methods are commonly referred to as methods which are directly or indirectly based on using a pseudo-random number generator (PRNG). In some cases, stochastic methods are the only possible mechanism of protecting information from an active adversary. In this paper we examine a construction of R-boxes, which are a generalization of S-boxes, classical structural elements of cryptographic primitives of hashing, block and stream encryption. R-boxes are in fact stochastic adders, i.e. adders with an unpredictable operating result, which depends on the key table H. A distinguishing feature of R-boxes is their efficient software and hardware implementation.

1 Introduction

An analysis of information security threats and development of computer technologies allows to arrive at a firm conclusion that the role of stochastic methods of information security is constantly increasing. Stochastic methods are commonly referred to as methods which are directly or indirectly based on using pseudo-random number generators (PRNG). As an example of a universal stochastic method of information security we can mention the method of introducing unpredictability in the operation of means and objects of security. By using PRNG all tasks of information security can be solved successfully. Thus, in some cases stochastic methods are the only possible mechanism of protecting information from an active adversary. A particular case of stochastic methods are cryptographic methods of information security.

The term “stochastic” in relation to information security applications was, apparently, first used by S.A. Osmolovsky in constructing codes which detect and correct mistakes arising when transferring data through communication channels (Osmolovsky 1991, 2003). The stochastic codes suggested by him offer unique properties, two of which are worth mentioning. They are: the ability to provide a predefined probability of correct information reception and the possibility to solve, beside the task of error detection and correction during data transmission, two other important tasks of information security – providing confidentiality and integrity of the information transferred.

2 Stochastic Transformation Blocks. R-Boxes

The reference (Asoskov et al. 2003) suggests a block of stochastic transformation (R-box), which can be effectively applied when solving various tasks related to information security. The construction of one of the possibly simplest variants of stochastic transformation block $R$, which was first proposed for solving the task of error correcting coding in operation (Osmolovsky 1991), and its graphical representation are shown in Fig. 1. The key information of n-bit R-box is filling the table $H = \left\{ {H\left( m \right)} \right\},\,m = 0,\, \ldots ,\,\left( {2^{n} - 1} \right),$ of dimension $n \times 2^{n}$, which contains elements GF(2ⁿ), mixed in a random fashion, i.e. $H\left( m \right) \in GF\left( {2^{n} } \right)$. In other words, the table H contains consecutive states of n-bit PRNG. The result $R_{H} \left( {A,\,B} \right)$ of the transformation of the input n-bit binary set A depends on how the table H is filled as well as on the transformation parameter B, specifying displacement in the table with respect to the cell holding the value A, in the following way $R_{H} \left( {A,\,B} \right) = H\left( {\left( {m_{A} + B} \right)\,\bmod \,2^{n} } \right),$ where m_A is the address of the cell in the table H, containing the code A, i.e. $H\left( {m_{A} } \right) = A$. Otherwise speaking, the result of the operation of R-box consists in reading the cell content in the table H, repeatedly displaced at B positions toward major addresses with respect to the cell containing the code A. To ensure the independence of transformation time from the source data we introduce into R-box the table H⁻¹ = {H⁻¹(j)} of dimension $n \times 2^{n}$, where ∀j = 0, 1, …, (2ⁿ – 1) H⁻¹(j) = m_j. To put it differently, the cell having the address j in the array H⁻¹ holds the address of the cell of the array H containing the code j. Below are the facts which deserve attention:

Fig. 1.

The behavior of R- box (a) and its graphical representation (b). ⊞ – modulo $2^{n}$ adder.

• when H⁻¹ = {0, 1, …, (2ⁿ – 1)} and B = 0, we get a classical S-box (substitution box) with the substitution table H;

• when writing its own address in each cell of the arrays H and H⁻¹ we get a classical $2^{n}$ adder, which means that the R-box can be rightfully called a stochastic adder, i.e. adder with an unpredictable operating result, which depends on how the key table H is filled.

R-box has an easy software implementation. Below follows an example of implementing an 8-bit box of stochastic transformation in Assembler (a system of commands x86, standard Intel notation) (Fig. 2).

Fig. 2.

Array H⁻¹&H

R-boxes can be applied for implementing stream encryption. In this case, a Plaintext is fed to input A, a Keystream is fed to input B, and a Ciphertext is removed from output $R_{H} \left( {A\text{,}B} \right)$. We should bear in mind that it is essential to apply the transformation $R^{ - 1}$ (reverse R) at the receiver.

The second area of application of R-boxes is substitution of modulo $2^{n}$ adders in modifying known algorithms of stochastic data transformation, for example, stream algorithms PIKE (Fig. 3), RC4, and several others (Asoskov et al. 2003; Stallings 2016; Hammood et al. 2016; McKague 2016; Rivest and Schuldt 2016). In addition, with the help of an R-box it is possible to substitute modulo $2^{n}$ adder in two ways in Fig. 1 and thus get two kinds of $R^{{^{2} }}$-boxes.

Fig. 3.

Modified PRNG of stream cipher PIKE: a – the graphical representation of the stochastic adder; b – the scheme of the stochastic adder; c – the scheme of PRNG. Sm – modulo 256 adder, RSm – stochastic 8-bit adder, M2–8-bit modulo 2 adder, γ – PRNG output, cri – Carry In, cro – Carry Out.

Let us consider an example of a nonlinear transformation on the basis of RFSR (Random Feedback Shift Register), which is obtained after substituting the modulo $2^{n}$ adder with an R-box in the architecture of an additive generator (Asoskov et al. 2003).

Let the number of bits in Q state (the number of storage elements) RFSR be 128: $\left| M \right| = \left| Q \right| = 128,\,\,Q = \left( {Q_{16} \, \ldots \,Q_{1} } \right),\,\,Q_{i} \in GF\left( {2^{8} } \right),\,\,i = 1,\, \ldots ,\,16.$ The nonlinear stochastic transformation on the basis of RFSR, constructed in accordance with Galois module (Fig. 4), is defined by the following expressions:

Fig. 4.

RFSR: a – general scheme; b – RFSR with a single R-box

$$ F\left( Q \right) = f^{16} \left( Q \right) = f^{16} \left( {Q_{16} \left\| \ldots \right\|Q_{1} } \right). $$

The equation of the base transformation f takes the following form:

$$ \left\{ {\begin{array}{*{20}l} {Q_{j} \;\; = R_{j} \left( {Q_{1} ,\,Q_{j + 1} } \right),j = 1, \ldots ,15,} \hfill \\ {Q_{16} = R_{16} \left( {Q_{1} ,\,C_{i} } \right).} \hfill \\ \end{array} } \right. $$

where $C = C_{1} \ldots C_{i} \ldots C_{16}$ is the control sequence (which probably depends on the key).

Finally, RFSR has a remarkable property: when choosing the appropriate table H of stochastic transformation it is possible to obtain a nonlinear maximum length sequence (M-sequence) generator, whose properties differ fundamentally from those of linear M-sequences, formed by LFSR. Figure 5 shows an example of the M-sequence generator of the length 63 (N = 3, n = 2, │Q_i│ = 2).

Fig. 5.

Example of RFSR: a – the scheme of the nonlinear M-sequence generator; b – the table of stochastic transformation; c – the switching diagram of the generator.

3 Conclusion

We have analyzed the construction of R-boxes, which are a generalization of S-boxes, classical structural elements of cryptographic primitives of hashing, block and stream encryption. R-boxes are in fact stochastic adders, i.e. adders with an unpredictable operating result, which depends on the filling of the key table H, which can be formed by using a method similar specified in the stream cipher RC4.

A distinctive feature of R-boxes is their effective software and hardware implementation.

R-boxes can be applied in the following areas:

• Constructing blocks of direct-to-reverse stochastic transformation in the implementation of stochastic methods of data transfer (Osmolovsky 1991);

• Implementing stream encryption; in this case a Plaintext is fed to input A, a Keystream is fed to input B, and a Ciphertext is removed from output $R_{H} \left( {A,B} \right)$; in this case it is essential to use the transformation $R^{ - 1}$ (reverse R) at the receiver;

• Increasing the cryptographic security of known algorithms by substituting modulo 2ⁿ adders with n-bit R- boxes.

Implementing nonlinear transformations through mixing cipher state (MixState), including those depending on the key information, in the construction of 2D and 3D iterative cryptographic algorithms (Ivanov et al. 2012a; Ivanov and Chugunkov 2012b; Ivanov et al. 2014; GOST R 34.12-2015 2015).

• Constructing shift registers with stochastic feedback (RFSR), which are a generalization of classical linear feedback registers (LFSR), i.e. PRNG, functioning in finite fields, which work well in practice as structural elements in primitives of symmetric cryptography. When choosing the appropriate table H RFSR forms nonlinear M-sequences, which have different properties from those characteristic of linear M-sequences. Innovative solutions of forming sequences of the length 2^m, where m stands for the number of storage elements in PRNG, forming sequences with a tail, forming universally programmed PRNG, forming sequences of any length, less than or equal to 2^m, working in the case of LFSR, also work in a more common case, that of RFSR (Ivanov et al. 2009).