In this paper, we discuss various options for implementing the "Kuznyechik" block encryption algorithm using the NVIDIA CUDA technology. We use lookup tables as a basis for the implementation. In experiments, we study the in uence of the size of the block of threads and the location of lookup tables on the encryption speed. We show that the best results are obtained when the lookup tables are stored in the global memory. The peak encryption speed reaches 30.83 Gbps on the NVIDIA GeForce GTX 1070 graphics processor .
Cryptographic protection is an important part of a modern IT infrastructure. Nowadays, both the volume of information and computing power are continually increasing. Accordingly, there are growing demands on both the robustness and speed of cryptographic algorithms.
The idea of using graphics processors to speed up encryption algorithms appeared almost
simultaneously with the idea of using them for general-purpose computing[
At present, there is a lot of papers, which focuses on using graphics processors for encryption.
Most of the papers are devoted to the AES encryption algorithm. In particular, in the paper [
The "Kuznyechik" cipher is a new symmetric encryption standard, which was introduced
in Russia in 2015 [
Because of a novelty and the limited use of chipher, fewer papers focus on the 'Kuznyechik"
algorithm, most of them focuses on cryptoanalysis [
The reported speed is 54 Mbps on a four-core CPU. The paper [
As it was outlined earlier, the "Kuznyechik" algorithm is a ten-round cipher based on an SP
network with the key length of 256 bits and the block length of 128 bits. An exhaustive
description of the algorithm can be found in [
Before the encryption, ten 128-bit round keys K1; :::; K10 are generated based on the main 256-bit key K. The expansion procedure is a Feistel network. Its transformation function is analogous to the round of the main cipher with a xed key. The rst two round keys K1; K2 are obtained from the halves of the main one. The rest of the keys are obtained by encrypting with the Feistel network. The keys (K2i; K2i 1) are given to each round of the network as an input, and the output is (K2i+2; K2i+1).
The expansion procedure is strictly sequential. Besides, it can be executed only once to obtain the array of round keys. Thus, we do not consider this procedure in the paper.
The cipher is based on two transformations: (i) Nonlinear transformation (ii) Nonlinear transformation
: GF (28) ! GF (28) implemented through the lookup table. `(a15; :::; a0) = 148 a15 + 32 a14 + 133 a13 + 16 a12 + 194 a11 + 192 a10 + 1 a9 + +251 a8 + 1 a7 + 192 a6 + 194 a5 + 16 a4 + 133 a3 + 32 a2 + 148 a1 + 1 a0; (1) where ai 2 GF (28), and operations take place in the eld GF (28). In particular, "+" is equivalent to the XOR operation).
The transformations that are used directly in the encryption are based on two previous transformations:
S(a) = R(a) =
L(a) = X[k](a) =
S(a15jj:::jja0) = (a15)jj:::jj (a0); R(a15jj:::jja0) = `(a15; :::; a0)jja15jj:::jja1; R16(a); k
a; where jj is the concatenation, ai 2 GF (28), k; a 2 GF (2128),
R16(a) means that the R function is applied for a for 16 times.
Using the above notations, the "Kuznyechik" algorithm can be described as follows:
EK1;:::;K10 (a) = X[K10]LSX[K9]:::LSX[K2]LSX[K1](a); where LSX[K](a) is equivalent to L(S(X[K](a))). (2) (3) (4) (5) (6)
It is easy to see that `(a15; :::; a0) = `(a15; 0; :::; 0) `(0; a14; 0; :::; 0) :::
`(0; 0; 0; :::; a0); `(a15 b15; :::; a0 b0) = `(a15; :::; a0) `(b15; :::; b0): (7) (8)
Based on this, the LS part of the round can be predicted in advance, with the result that we get 16 lookup tables. Each of the lookup tables contains 256 entries of size 128 bit. When using lookup tables, the entire encryption process comes down to 16 lookups across tables and 16 128-bit XOR operations (15 on the search results and 1 with a round key).
CUDA is a proprietary API provided by NVIDIA that facilitates the use of video cards for
general purpose computing. This programming model is required since the graphics processor
can process hundreds of threads simultaneously according to the so-called SIMT model. A
detailed description of CUDA technology can be found in [
The kernel is a function intended for the execution on the GPU. The unit of execution is a thread. Threads are combined into blocks, and blocks are combined into a grid. The grid and block con guration is speci ed when the kernel function is started. Resources for execution are allocated per block, and not on every single thread.
From a hardware point of view, the graphics processor is divided into multiprocessors, and multiprocessors are divided into warps. The warps, in turn, consist of 32 stream processors (terminal computing units). All stream processors inside one warp are synchronized. They either execute the same instruction or idle.
The memory organization on graphics processors has a number of features. A programmer has access to a global, shared, constant, and texture memory. The global memory is equivalent to RAM. The texture memory and constant memory are the areas of global memory with special access features. The shared memory has low volume (64KB), but very high speed.
Physically, it is divided into several independent areas, called banks (banks). An attempt to simultaneously access di erent memory cells within one bank will lead to the subsequent execution of requests. This situation is called a bank con ict. A large number of access con icts reduce performance signi cantly.
We use lookup tables as a base for the implementation of the algorithm. At rst, we execute an initialization procedure, which copies the tables to the device. Before encryption, we allocate bu ers on the device. We use the allocated bu ers to copy round keys and data to be transformed. We copy data back and release the bu ers after the encryption. Encryption keys are best to store in the shared memory. The memory consumption is small, and the access pattern allows to avoid access con icts (all threads of a warp always read the same key).
The issue of locating the lookup tables does not have such a straightforward solution. The size of the LS tables does not allow them to be entirely located in the shared memory since for the Pascal generation it is allowed to allocate only 48 KB per thread block. In addition, random access to the tables will result in numerous access con icts, which signi cantly reduce performance. From this it follows that there are only three options for storing the tables, namely, the global, constant and texture memory. To provide an additional acceleration, we read the global memory using the ldg() function.
In addition, we should also nd out the optimal launch con guration of the kernel function. It does not make sense to use more than one thread per block of text. Although one XOR operation for 128-bit values is translated into two 64-bit operations, the use of two threads to process one block of text will lead to undesirable consequences. First, an increase in the number of threads will lead to an overall decrease in simultaneously processed blocks of text, since the number of stream processors is limited. Second, since each thread needs to store its copies of local variables, the number of occupied registers will increase. This also becomes a limiting factor and reduces the amount of simultaneously processed blocks of text. However, it makes sense to study how the size of the block of threads a ects the encryption speed.
In this paper, we consider the following sizes of a block: 32, 64, 128,192, 256, 384, 512, 768, and 1024 threads. There is no sense to consider less than 32 threads in a block since the minimum unit of execution on a graphics processor is a warp consisting of 32 stream processors.
We used the following con guration in our experiments: CPU: Intel Core i5-6400 GPU: NVIDIA GeForce GTX 1070 RAM: 8 Gb DDR3
In general speed tests, the number of threads in a block was 512. The volume of encrypted data was equal to 256 MB in tests with changing block con guration. The CPU version of the "Kuznyechik" algorithm executed in 4 threads using SSE instructions. We did not take into account the time spent on copying data to the memory of the GPU and back.
The results of performance measurements are presented in Tables 1 and 2 and Figures 1 and 2 shows the results of the experiments. Let us consider the results in more detail.
The CUDA SDK includes a pro ler, which allows getting information on the kernel execution time, resources used by the kernel, multiprocessor loading, cache e ciency, and many other parameters. The pro ler data is used for a more detailed analysis of the results.
The fastest option is the global memory. The correct access pattern allows us to achieve more than 90% hits fro L2 cache and about 20% hits for L1. However, even in this case, working with memory is still an essential factor limiting performance.
The texture memory is slower due to the greater number of registers used and the greater memory load. When reading a single value, its neighbors are also loaded into the cache, so the memory subsystem has to serve the greater number of readings. So cost of each cache miss is high. In addition, in the Maxwell and Pascal architectures, the texture cache shared the memory with L1 cache and therefore does not give any gain compared to it.
For constant memory, the problem is a random access pattern, which causes frequent cache misses. Another problem is the read data size - 16 bytes per request. As a result, the performance degrades.
Let us turn to the size of the thread blocks.
No more than a certain number of threads, warps, and blocks can be executed on a multiprocessor simultaneously. In addition, there are limiting factors, namely, the total number of registers and shared memory. With small blocks, the overhead caused by the context switching is huge. At the beginning of execution, time is spent for each block to copy round keys to the shared memory. For large blocks, a multiprocessor simultaneously executes fewer blocks due to the presence of limiting factors. Besides, the location of the block cannot be taken by another one until the block is completed. In our case, the difference between thread block sizes for global memory is insignificant, since the main limiting factor is the global memory latency. Constant memory case reaches maximum troughput with 32 threads per thread block, whereas texture memory case have its maximum at 32 threads per threads block.
In this paper, we considered various options for implementing the \Kuznyechik" encryption algorithm using CUDA technology. We used lookup tables as a basis for the implementation. We discussed the global, constant, and texture memory as an option for the location of the lookup tables. Besides, we considered the following sizes of thread blocks: 32, 64, 128, 192, 256, 384, 512. According to the experiments, the best results were obtained when search tables are stored in the global memory. The peak speed of the encryption was equal to 30.83 Gbps on the equipment used. Acknowledgments The work was funded by the Russian Federation Ministry of Science and Higher Education within a state contract with the "Crystallography and Photonics" Research Center of the RAS under agreement 007-GZ/Ch3363/26.