Using component-wise functions in cryptographical transformation algorithm from Russian National Standard GOST R 34.12-2015

Abstract

The paper presents the general approach to selecting functions, keeping the first argument field, in the process of symmetric encryption of a plaintext. Quantitative estimation and general characteristics of ordinate vector for such functions are given. Ten component-wise functions of binary logic algebra of three arguments, replacing one function of digit-wise addition modulo two in the cryptographictransformation algorithm from Russian National Standard GOST R 34.12-2015, are presented in the paper. Using component-wise functions widens the range of intermediate options of round transformations in block encryption, which complicates the decryption (cracking) algorithm for the cipher.

1. Introduction

The Russian National Standard GOST R 34.12-20151is a symmetric cipher in which plaintext is converted by blocks of fixed length of 128 or 64 digits and a 256-digitlong key, and the encryption/decryption algorithms are reverse procedures using multi-round operations of substitutions and transformations the sequence of which isdeveloped by bitwise operation "addition modulo two" (AMT) for the source text and the first iterative key. Consequently, the multi-variant substitution of the AMT operation proposed by the authors leads to a greater variety of intermediate variants of the bit addition, which changes the results of the final operations, and in general complicates the algorithm of decryption (hacking) of the ciphertext.

2. General analysis of the existing algorithm

Cryptographic transformation of information used in GOST R 34.12-2015 is based on the principles of block data encryption [2, 3, 4] and contains a combination of operators that ensures the implementation of the properties of symmetric encryption in the standard [1]:

 bitwise addition is formed by the AMT operation on the current transformation (a) and the round key (k), which corresponds to the bit transformation X[k]: V128 → V128, where the result determines the equality of blocks before and after the AMT operation and is defined by the formula

X[k](a) = k⊕a, ( 1 ) determines the index of the replacement array π, and the result V128 → V128 determines the equality of blocks before and after the replacement, and the formation of analytical complexity of dependencies between the key and the encrypted text, and is provided by the conversion

S(a) = S(a15||…||a0) = π(a15)||…||π(a0), ( 2 ) where: a = a15||…||a0∈ V128, ai∈ V8, i = 0, 1, …, 15;

 dispersion of information is achieved both by making nine-round consecutive embedding F(a) for sixteen times byte-wise conversion in each round L(a) over a 128-bit value of the replacement block S(π(a)), and by spreading of influence of each symbol in the plaintext to all the characters of the ciphertext, which is provided with transformations

F [k](a1, a0) = LSX[k]( a1) ⊕a0, a1, ( 3 ) where: L(a) = R16(a);R(a) = R(a15||…||a0) = ℓ(a15, …, a0)|| a15||…|| a1; k, ai∈ V128.

Generalizing the transformations given in equations ( 1 ), ( 2 ) and ( 3 ), let us form a complete encoding algorithm EKi(a) that performs transformations of 128-bit source block of information, where the direct numbering substitution of iterative keys is used

EK1, …, K10(a) = (k1⊕a)F(a)(k2⊕a)F(a)…(k9⊕a)F(a)(k10⊕a). ( 4 )

It should be noted that the DKi (a) full information decryption algorithm uses inverse transformations S-1(a), R-1(a) and L-1(a), and the numbering of iterative key substitution is done in the reverse order

DK10, …, K1 (a) = (k10⊕a)F-1(a)(k9⊕a)F-1(a)… (k2⊕a)F-1(a)(k1⊕a). ( 5 )

In accordance with the transformations given in equations ( 1 ) – ( 5 ), the complete algorithmic sequence of information encryption/decryption contains both repetitive AMT operation over the iterative key (ki) and the current transformation (a) and round wise mixing and dispersion of information for direct substitutions S(a), R(a), L(a) and inverse substitutions S-1(a), R-1(a), L-1(a). Consequently, the entire periodic process of encryption / decryption of information should be divided, for the current presentation, into two groups of operations: AMT and substitutions.

3. Introduction of component-wise functions

The bitwise operation AMT used in cryptographic information conversion algorithms D(a) belongs to the functions of Boolean algebra [3], is generated by a combination of logical values of two variables and is oneof the operations that has the property of "restoring the input value of one of the variables" in sequential application of the operation in the process of encryption, and then in the process of decryption

D(a) = (k⊕a) ⊕k, ( 6 ) where k is an iterative key andais information for encryption.

Taking into account that the AMT operation belongs to the functions of Boolean algebra of two variables, we would like to point out that other functions generated by combinations of logical values of three [5], four or more variables possess the same property, but the generated functions do not perform the "classical" AMT operation. Therefore, let us present a new function for restoration of the input values, as an operation equivalent to the "classical" AMT operation and call it by a new termcomponent-wise function M(a).

Let us present (see figure) the location of the component functionsМj(a) in the process of encrypting 128-bit block of information in the form of an algorithm based on the transformation ( 4 ), for the standard transformation and the oneproposed by the authors.

As shown in the figure, the differences in the authors’ encryption algorithm component-wise functions Mj (a)are used, replacing the only AMT operation used in the transformation ( 4 ), as well as the multiple use of iterative keys, while the production and the number of iterative keys remains the same as the standard and equals ten. It should be noted that the decryption process remains similar to the encryption process, except for changing the order numbers of the iterative keys to the opposite, similar to the transformation ( 5 ). SubstitutionsS(а) andL(а) SubstitutionsS(а) andL(а) . .

.

SubstitutionsS(а) andL(а)

4. The formation of the component-wise functions

The essence of the forming component functions consists in theoretical determination of the characteristics of functions that have the property of restoring the input value for one of the arguments when performing only the logical operation of the function over the operations of forward and inverse transformation, similar to the use of the AMT operation in equation ( 1 ). Further, the symbol "" defines a logical operation of the component function.

In the theory of abstract algebra, the proofs of existence of Boolean algebras for any number of variables are presented, indexing of Boolean functions is introduced, and belonging of the set of indexed functions of Boolean algebras to systems of normal forms is established [6]. Using the terminology of [5], we will present the principles of formation of the component functions in the form of statements, which are valid for any number of variables. For certainty we use component-wise functions of three variables.

Statement 1. On the distribution of meaning of variables of potentially suitable component-wise functions.

Direct conversion М(a)[k] the argument field A contains the data to be converted, and the arguments B and C contain the iterative key values in direct numbering

Мj(a)[k]= Мj(A, B, C) = аkiki+1X[k](a), ( 7 ) where j is the sequence number of component-wise functions; i= 1, 2, …, 10 isthe sequence number of the iteration key if i> 10 i: = imod10; k is the logical values of bits of the iteration key.

Inverse transformation М -1j(a)[k]:the argument A field contains the data to restore, and the arguments B and C contain the iterative key values in reverse numbering

М --1j(a)[k]= М-1j(A, B, C) = аki+1kiX-1[k](a), (8) where: i = 10, 9, …, 1 is the sequence number of the iteration key if i< 1 i: = imod10.

Let's apply the direct transformation specified in equation ( 7 ) in the process of encryption and the inverse equation (8) in the process of decryption

D(a) = М j -1Мj(a)[k], (9) consequently, such a double transformation results in restoration of the input data, similar to the transformation specified in equation ( 6 ).

Statement 2. On the distribution of the field of logical zeros and ones of the truth table of potentially suitable component functions.

The forward and reverse conversion functions, potentially suitable for use, contain an equal number of zeros and ones, as confirmed by the condition

М -1jМj(a)[k] = М (М (A, B, C), B, C) = A, (10) which gives us: М (М (0, В,С), В,С)  0  .

 М (М (1, B,С), B,C)  1 When performing substitution for all combinations of arguments, we choose from potentially suitable functions, which restore the field of argument A. Let's not consider here a function identical to the first argument, and its negation as not depending significantly on other arguments and, therefore, unsuitable for encryption. In accordance with the statements above and using the theory of abstract algebra and combinatorial techniques, let us perform quantitative calculations for the functions of two, three, and four arguments on the condition of equation (10), the results of which are given in table 1.

№

As follows from condition (10), the functions, keeping the argument A field, contain equal amount of zeros and ones in the ordinate vector. We consider such functions potentially applicable in the encryption algorithm. The number of such functions of n variables is described with the formula:

С(2n, 2n-1), (11) where C is the number of combinations.

In particular, for n=4 we get C(16, 8)=17920

But not all the potentially suitable Boolean functions restore the argument A field. Another condition can be derived from equality (10): for inverse sets of argument values with A variable the function takes on inverse values. This condition can be easily confirmed with the following algorithm.

Algorithm 1.

Step 1. Let us divide the field of logical values of Boolean function F in half. Wegettwovectors: F1andF2.

Step 2. If F2 = F1, then function F restores the first argument. Otherwise it doesn’t.

Performing the final selection of component functions, the number of which is specified inTable 1, let us form their perfect and then the minimal disjunctive normal form (MDNF). The results of the MDNF function formation are given in Table 2.

It should be clarified that the symmetric arrangement of the same transition probabilities in Table 2, with a natural increase in weight coefficients of the field of zeros and ones, characterizes the completeness and correctness of the representations of component-wise functions.

Unfortunately, some of the presented functions are interdependent. It is obvious, that if function F keeps the argument A field, function F obtains the same property. Such dependence between cryptographic functions is unacceptable, that is why only the 5 functions, listed above, are to be used in the encryption/decryption algorithm, while F or F can be picked randomly.

There are other functions to restore arguments B and C, MDNF for which are not given in Table 2. Functions, keeping the argument B field, meet the following condition: for sets of argument values, inverse on variable B, i.e. for sets (A,B,C) and (A,B,C), they take on inverse values. This condition can be easily confirmed with the following algorithm. FunctionBooleanvalu es

00011110 АBCАBАC 00101101 АBCАBАC 01001011 АBАCАBC 01101001 АBCАBCАBCАBC 01111000 АBАCАBC 10000111 АBАCАBC 10010110 АBCАBCАBCАBC 10110100 АBАCАBC 11010010 АBАCАBC 11100001 АBАCАBC Algorithm 2.

Step 1. Let us divide the field of logical values of Boolean function F in 4 equal parts: F1, F2, F3, and Step 2. If F2 = F1 and F4 = F3, then function F restores the second argument. Otherwiseitdoesn’t.

Similar algorithm can be used to find functions, restoring the third argument. The only difference is that the logical values field of Boolean function F is divided into 8 equal parts (for n=3 we get one component in each part), and set them equal pairwise. To define a component-wise function by an ordinate vector, we can randomly pick half of the values, and the other half is constructed inversely to the first one. So the number of Boolean functions of n variables that restore second, third, …, nth argument is described with formula:

22^(n-1). (12)

In the table 3 we present component-wise functions of three variables, restoring the second argument and significantly dependent on all the variables.

In addition, there are other functions for restoring variables C that do not exist in Table 2 and 3.Show them in the Table 4.

5. Analysis of transformations by component-wise functions

One way to demonstrate the practical capabilities of component functions is to perform transformations of functions from Table 2 and compare the results with the results given in GOST R 34.12-2015 [1].

To use component-wise functions, we extend the general appearance of the bitwise addition property, as shown in transformation ( 1 ), to apply the binary logic functions of three arguments [4]

X [k] (a) = Мj(a)[k 1][k 2], (13) where: Мj is the sequence number of the functions in Table 2; k1 and k2 are the iterative keys.

Extending properties of bitwise addition in the conversion ( 1 ) to the form of transformation (13) makes other combinations of operators, which gives the whole cryptographic transformation a new property, i.e. component-wise transformation.

We are going to present the results of a component-wise transformation for direct transformation Мj(a)[k], corresponding to the application of equation ( 7 ), taking into account transformation (13), for functions the j = 1 and 2 from Table 2:

М1(a)[k] = аk1k2 = 99ba99dc51325510ffefddefbbabddef; (13, а) М2(a)[k] = аk1k2 = 6766232267666700fecc988832221000, (13, б) where: a = 1122334455667700ffeeddccbbaa9988 1, p. 14; k1 = 8899aabbccddeeff0011223344556677 1,p. 13; k2 = fedcba98765432100123456789abcdef 1, p. 13.

It should be noted that the result of the bitwise addition ( 1 ) given in 1, p. 14 has the form

X[k](a) = k1⊕a =99bb99ff99bb99ffffffffffffffffff , (14) expectedly different from transforming equation (13), the results of which are given in transformation (13, a and b) proposed by the authors method of component conversion.

6. Conclusion

The three-argument binary logic algebra functions extending the cryptographic transformation modes of Russian National Standard GOST R 34.12-2015 are the beginning of a series of similar functions for four, five and more arguments, and their use will undoubtedly increase the possibilities of a bit-wise algorithm transformation. It is also possible to extend the approach to the considered question using the method of work [7], provided that the values of the arguments of the component-wise functions are read from the file. Further research will be aimed at the development of a new type of functional transformation, followed by its implementation in the software and hardware complex, which will enable introduction of the next version of GOST R 34.12-2015.

References

[1] GOSTR 34 . 12 - 2015 2015 Information Technology . Cryptosecurity. Block Ciphers (Moscow: Standartinform) p 25

[2] Shannon C E 1963 Works on Communication Theory and Cybernetics (Moscow: Publishing house of foreign literature ) p 830

[3] Shannon C E 1948 A Mathematical Theory of Communication Bell System Technical Journal 27 379 - 423 , 623 - 656

[4] Fomichev M I 2003 Discrete Mathematics and Cryptology (Moscow: Dialogue-MEPhI) p 400

[5] Sultanov D M , Vasilischin I I and Pugin M S 2016 Architecture Concept of the Encryption Unit , Performing the Russian National Standard GOST R 34 . 12 -2015 Cryptographic Transformation Based on PAC. Expanding the Modes of the GOST R 34 . 12 -2015 Cryptographic Transformation Based on a Specific Microcontroller Proceedings of the international scientific conf. Parallel Computing Technology 797

[6] Lidl R and Pilz G 1984 Applied Abstract Algebra (Springer-Verlag New York Inc.) p 743

[7] Yumaganov A S and Myasnikov V V 2017 A method of searching for similar code sequences in executable binary files using a featureless approach Computer Optics 41 ( 5 ) 756 - 764 DOI: 10.18287/ 2412 -6179-2017-41-5- 756 -764