Grasshopper block cipher implementation with CFB mode in C ++
Today we will focus on the new Grasshopper block cipher algorithm from GOST R 34.12 2015. Recently, many publications devoted to this standard have been published. In them, from a theoretical point of view, the described algorithm is described, the features of individual transformations are studied, and optimization methods are also proposed by including code inserts in assembly language.
In this article, I invite the reader to familiarize themselves with the implementation of this block cipher in C ++. It is worth noting that when writing this program, the goal was not to achieve the greatest efficiency, and the main task was to show how the algorithm works. You can see the description of the algorithm in the official documentation .
The program consists of three parts
Objects of this class (hereinafter referred to as “messages”) are universally used in the program for storing information in binary form. The interface was designed in such a way that the following tasks are effectively solved:
Uniqueness is ensured by the fact that the copy constructor and the copy assignment operator are prohibited (implicitly), since similar transfer functions are described.
ByteBlock class objects always own the memory they point to. Even when an object is initialized with a certain piece of memory, the constructor copies it to a new location, and the object works with a copy of the original information. In a sense, this class is like a smart pointer from STL - std :: unique_ptr.
Memory zeroing is provided by the memset function. It is worth noting that when assembling this program, you should not specify optimization options, since some compilers have the ability to ignore the memset function call, knowing that the memory will not be used further, and will soon be deleted.
These functions convert the input from the hexadecimal notation into their byte representation, which is necessary for the further work of the program.
The keys field is iterative keys that are calculated once during the initialization of the object with the given key. The is_init field is a flag that indicates whether objects like Kuznyechik have ever been created. This flag is necessary due to the fact that at the time of starting the program, many coefficients and algorithm parameters are missing. At the first initialization, they are calculated and stored in memory until the program ends.
In view of the above, it is necessary to comment on the existence of a copy constructor, while ByteBlock objects that do not have this constructor are located inside the class. The fact is that when copying, element-by-element deep copying of iterative keys from the keys array occurs.
It is here that we see those variables that, when launched, do not store the values necessary for the algorithm to work. These are direct_permutation, inverse_permutation, with the help of which nonlinear transformation is performed, and iteration_constants, which are used to deploy the key. They are filled as follows:
All conversions work with regular pointers: the conversion from ByteBlock to BYTE * does not require additional costs, and the check that the size of the allocated memory matches the cipher parameters was performed at a higher level.
A non-linear transformation is nothing more than a regular permutation.
It will be interesting to dwell on the multiply function. Its peculiarity lies in the fact that when performing a linear transformation, all calculations are carried out in the factor ring GL (2) [x] / p (x), where p (x) = x ^ 8 + x ^ 7 + x ^ 6 + x + 1. In the first cycle, we multiply polynomials given by their coefficients from GL (2). In the second cycle, the value modulo p (x) is calculated step by step.
And finally, the encryption algorithm in our notation will look like this:
Here are only options for functions that operates in the “forward” direction. In other words, encrypting. The functions for decryption are implemented in exactly the same way.
The choice of block encryption mode was random. By analogy, other modes are easily written. Those who are familiar with the CryptoPP library may have a sense of deja vu, and this will be justified. Indeed, this is the approach to the interaction of the block cipher and the encryption mode used in this library.
In order to be able to use the block cipher in tandem with this template class, the class that implements it must satisfy the following requirements:
Obviously, our Kuznyechik class meets these requirements.
These algorithms use auxiliary functions that divide all messages into blocks that are multiples of the length at which a particular block cipher works, combine them back, as well as element-wise xor.
The decision to break the decryption function into its component parts seems redundant. This would be the case if the encryption mode with ciphertext feedback did not support concurrency for this procedure. Next, we will consider a variant of the decryption algorithm using std :: threads from the C ++ 11 standard.
The project repository is located here .
In this article, I invite the reader to familiarize themselves with the implementation of this block cipher in C ++. It is worth noting that when writing this program, the goal was not to achieve the greatest efficiency, and the main task was to show how the algorithm works. You can see the description of the algorithm in the official documentation .
Program structure
The program consists of three parts
- set of helper functions and classes - mycrypto.cpp mycrypto.hpp
- Grasshopper block cipher - Kuznyechik.cpp Kuznyechik.hpp
- Cipher Feed Back Encryption Mode - modes.hpp
Notation Used
#define BLOCK_LENGTH 16
typedef unsigned char BYTE;
typedef unsigned short WORD;
Aids
Class ByteBlock
ByteBlock Interface
class ByteBlock {
BYTE * pBlocks;
size_t amount_of_bytes;
public:
// Construct block of bytes which contsists of
// size_ blocks each of them with init_value in it
ByteBlock(size_t size_ = 0, BYTE init_value = 0);
// Construct block with size_ first bytes of pBlocks_
// The value will be copied, source stays untouchable
ByteBlock(BYTE * pBlocks_, size_t size_);
// Move constructor
// Copy constructor thus implicitly deleted
// Object to move turn to null
ByteBlock(ByteBlock && rhs);
// Destructor, yeah
~ByteBlock();
// Move assigment operator
// Object to move turn to null
void operator = (ByteBlock && rhs);
// This cast may be convenient to use the ByteBlock
// in functions which takes raw pointers as argument
BYTE * byte_ptr();
const BYTE * byte_ptr() const;
// Indexing operator with evident functionality
BYTE & operator [] (size_t index);
BYTE operator [] (size_t index) const;
bool operator == (const ByteBlock & lhs) const;
bool operator != (const ByteBlock & lhs) const;
// Replace body of the current block with pBlocks_
// Old value will be zerod, and then, deleted
// New value copied into the block,
// source stays untouchable
void reset(const BYTE * pBlocks_, size_t size_);
// Return amount of bytes in block
size_t size() const;
// It'll return deep copy of the block, which
// points to different place in memory
ByteBlock deep_copy() const;
// It'll return slice of current ByteBlock
ByteBlock operator () (size_t begin, size_t length) const;
// Changes values between two ByteBlock-s
friend void swap(ByteBlock & lhs, ByteBlock & rhs);
};
Objects of this class (hereinafter referred to as “messages”) are universally used in the program for storing information in binary form. The interface was designed in such a way that the following tasks are effectively solved:
- Storage of byte strings of arbitrary length
- Ensuring the "uniqueness" of messages in memory
- Resetting a portion of memory before freeing up memory
- Ensuring timely message deletion
- Providing convenient access to hotel bytes, and byte sequences in a message
Uniqueness is ensured by the fact that the copy constructor and the copy assignment operator are prohibited (implicitly), since similar transfer functions are described.
ByteBlock class objects always own the memory they point to. Even when an object is initialized with a certain piece of memory, the constructor copies it to a new location, and the object works with a copy of the original information. In a sense, this class is like a smart pointer from STL - std :: unique_ptr.
Memory zeroing is provided by the memset function. It is worth noting that when assembling this program, you should not specify optimization options, since some compilers have the ability to ignore the memset function call, knowing that the memory will not be used further, and will soon be deleted.
Translating hex strings in ByteBlock and vice versa
std::string hex_representation(const ByteBlock & bb);
ByteBlock hex_to_bytes(const std::string & s);
These functions convert the input from the hexadecimal notation into their byte representation, which is necessary for the further work of the program.
Grasshopper Algorithm
Kuznyechik Interface
class Kuznyechik {
std::vector keys;
static bool is_init;
public:
static const int block_lenght { BLOCK_LENGTH };
Kuznyechik(const ByteBlock & key);
Kuznyechik(const Kuznyechik & rhs);
~Kuznyechik();
void encrypt(const ByteBlock & src, ByteBlock & dst) const;
void decrypt(const ByteBlock & src, ByteBlock & dst) const;
};
The keys field is iterative keys that are calculated once during the initialization of the object with the given key. The is_init field is a flag that indicates whether objects like Kuznyechik have ever been created. This flag is necessary due to the fact that at the time of starting the program, many coefficients and algorithm parameters are missing. At the first initialization, they are calculated and stored in memory until the program ends.
In view of the above, it is necessary to comment on the existence of a copy constructor, while ByteBlock objects that do not have this constructor are located inside the class. The fact is that when copying, element-by-element deep copying of iterative keys from the keys array occurs.
Global variables and their initialization
Used global variables
const vector nonlinear_transform_perm = {
252, 238, 221, 17, 207, 110, 49, 22, 251, 196,
250, 218, 35, 197, 4, 77, 233, 119, 240, 219,
147, 46, 153, 186, 23, 54, 241, 187, 20, 205,
95, 193, 249, 24, 101, 90, 226, 92, 239, 33,
129, 28, 60, 66, 139, 1, 142, 79, 5, 132, 2,
174, 227, 106, 143, 160, 6, 11, 237, 152, 127,
212, 211, 31, 235, 52, 44, 81, 234, 200, 72,
171, 242, 42, 104, 162, 253, 58, 206, 204, 181,
112, 14, 86, 8, 12, 118, 18, 191, 114, 19, 71,
156, 183, 93, 135, 21, 161, 150, 41, 16, 123,
154, 199, 243, 145, 120, 111, 157, 158, 178, 177,
50, 117, 25, 61, 255, 53, 138, 126, 109, 84,
198, 128, 195, 189, 13, 87, 223, 245, 36, 169,
62, 168, 67, 201, 215, 121, 214, 246, 124, 34,
185, 3, 224, 15, 236, 222, 122, 148, 176, 188,
220, 232, 40, 80, 78, 51, 10, 74, 167, 151, 96,
115, 30, 0, 98, 68, 26, 184, 56, 130, 100, 159,
38, 65, 173, 69, 70, 146, 39, 94, 85, 47, 140,
163, 165, 125, 105, 213, 149, 59, 7, 88, 179,
64, 134, 172, 29, 247, 48, 55, 107, 228, 136,
217, 231, 137, 225, 27, 131, 73, 76, 63, 248,
254, 141, 83, 170, 144, 202, 216, 133, 97, 32,
113, 103, 164, 45, 43, 9, 91, 203, 155, 37,
208, 190, 229, 108, 82, 89, 166, 116, 210, 230,
244, 180, 192, 209, 102, 175, 194, 57, 75, 99,
182
};
const map direct_permutation, inverse_permutation;
const vector linear_transform_coeff = {
148, 32, 133, 16, 194, 192, 1, 251, 1, 192,
194, 16, 133, 32, 148, 1
};
const WORD linear_transform_modulus = 0x1C3;
const vector iteration_constants;
It is here that we see those variables that, when launched, do not store the values necessary for the algorithm to work. These are direct_permutation, inverse_permutation, with the help of which nonlinear transformation is performed, and iteration_constants, which are used to deploy the key. They are filled as follows:
Initializing Global Variables
void init_perms() {
map *p_direct, *p_inverse;
p_direct = const_cast< map * >(&direct_permutation);
p_inverse = const_cast< map * >(&inverse_permutation);
for(int i = 0; i < nonlinear_transform_perm.size(); i++) {
(*p_direct)[i] = nonlinear_transform_perm[i];
(*p_inverse)[nonlinear_transform_perm[i]] = i;
}
}
void init_consts() {
vector * p = const_cast< vector * >(&iteration_constants);
ByteBlock v128;
for(BYTE i = 1; i <= 32; i++) {
v128 = ByteBlock(BLOCK_LENGTH, 0);
v128[BLOCK_LENGTH - 1] = i;
iteration_linear_transform_direct128(v128.byte_ptr());
p->push_back(std::move(v128));
}
}
Implementation of transformations used in the algorithm
All conversions work with regular pointers: the conversion from ByteBlock to BYTE * does not require additional costs, and the check that the size of the allocated memory matches the cipher parameters was performed at a higher level.
Nonlinear Direct Conversion
void nonlinear_transform_direct128(BYTE * target) {
BYTE * p_end = target + BLOCK_LENGTH;
while(target != p_end) {
*target = direct_permutation.at(*target);
target++;
}
}
A non-linear transformation is nothing more than a regular permutation.
Linear direct conversion
void iteration_linear_transform_direct128(BYTE * target) {
for(int i = 0; i < 16; i++)
linear_transform_direct128(target);
}
void linear_transform_direct128(BYTE * target) {
BYTE buffer = linear_transform_core128(target);
for(int i = BLOCK_LENGTH - 1; i > 0; i--)
target[i] = target[i-1];
*target = buffer;
}
BYTE linear_transform_core128(const BYTE * target) {
WORD result = 0;
for(int i = 0; i < BLOCK_LENGTH; i++)
result ^= multiply(target[i], linear_transform_coeff[i]);
return result;
}
WORD multiply(WORD lhs, WORD rhs) {
WORD result = 0, modulus = linear_transform_modulus << 7;
for(WORD detecter = 0x1; detecter != 0x100; detecter <<= 1, lhs <<= 1)
if(rhs & detecter) result ^= lhs;
for(WORD detecter = 0x8000; detecter != 0x80; detecter >>= 1, modulus >>= 1)
if(result & detecter) result ^= modulus;
return result;
}
It will be interesting to dwell on the multiply function. Its peculiarity lies in the fact that when performing a linear transformation, all calculations are carried out in the factor ring GL (2) [x] / p (x), where p (x) = x ^ 8 + x ^ 7 + x ^ 6 + x + 1. In the first cycle, we multiply polynomials given by their coefficients from GL (2). In the second cycle, the value modulo p (x) is calculated step by step.
Deploying Iterative Keys
Iterative Key Generation Functions
void keys_transform128(BYTE * k1, BYTE * k2, int iconst) {
BYTE buffer[BLOCK_LENGTH];
memcpy(buffer, k1, BLOCK_LENGTH);
xor128(k1, k1, iteration_constants[iconst].byte_ptr());
nonlinear_transform_direct128(k1);
iteration_linear_transform_direct128(k1);
xor128(k1, k2, k1);
memcpy(k2, buffer, BLOCK_LENGTH);
}
void key_derivation128(BYTE * k1, BYTE * k2, BYTE * k3, BYTE * k4, int ipair) {
if(k1 != k3) memcpy(k3, k1, BLOCK_LENGTH);
if(k2 != k4) memcpy(k4, k2, BLOCK_LENGTH);
for(int i = 0; i < 8; i++)
keys_transform128(k3, k4, ipair * 8 + i);
}
And finally, the encryption algorithm in our notation will look like this:
void encrypt128(BYTE * target, const vector & keys) {
xor128(target, target, keys[0].byte_ptr());
for(int i = 1; i < 10; i++) {
nonlinear_transform_direct128(target);
iteration_linear_transform_direct128(target);
xor128(target, target, keys[i].byte_ptr());
}
}
Here are only options for functions that operates in the “forward” direction. In other words, encrypting. The functions for decryption are implemented in exactly the same way.
CFB Encryption Mode
Interface CFB_Mode
template
class CFB_Mode {
const CipherType algorithm;
const ByteBlock iv;
void decrypt_with_iv(const ByteBlock & src, ByteBlock & dst, const ByteBlock & iv_) const;
public:
CFB_Mode(const CipherType & alg, const ByteBlock & init_vec);
void encrypt(const ByteBlock & src, ByteBlock & dst) const;
void decrypt(const ByteBlock & src, ByteBlock & dst) const;
void parallel_decrypt(const ByteBlock & src, ByteBlock & dst) const;
};
The choice of block encryption mode was random. By analogy, other modes are easily written. Those who are familiar with the CryptoPP library may have a sense of deja vu, and this will be justified. Indeed, this is the approach to the interaction of the block cipher and the encryption mode used in this library.
In order to be able to use the block cipher in tandem with this template class, the class that implements it must satisfy the following requirements:
- The public encrypt and decrypt methods are described with the same prototype as in the CFB_Mode class
- There is an open block_length field storing the number of bytes corresponding to the length of the cipher block
Obviously, our Kuznyechik class meets these requirements.
Encryption and Decryption Function
These algorithms use auxiliary functions that divide all messages into blocks that are multiples of the length at which a particular block cipher works, combine them back, as well as element-wise xor.
std::vector split_blocks(const ByteBlock & src, size_t length);
ByteBlock join_blocks(const std::vector & blocks);
void xor_blocks(ByteBlock & to_assign, const ByteBlock & lhs, const ByteBlock & rhs);
Encryption function
template
void CFB_Mode::encrypt(const ByteBlock & src, ByteBlock & dst) const {
auto blocks = split_blocks(src, CipherType::block_lenght);
ByteBlock tmp;
algorithm.encrypt(iv, tmp);
xor_blocks(tmp, tmp, blocks[0]);
blocks[0] = std::move(tmp);
for(int i = 1; i < blocks.size(); i++) {
algorithm.encrypt(blocks[i-1], tmp);
xor_blocks(tmp, tmp, blocks[i]);
blocks[i] = std::move(tmp);
}
dst = join_blocks(blocks);
}
Decryption function
template
void CFB_Mode::decrypt(const ByteBlock & src, ByteBlock & dst) const {
decrypt_with_iv(src, dst, iv);
}
template
void CFB_Mode::decrypt_with_iv(const ByteBlock & src, ByteBlock & dst, const ByteBlock & iv_) const {
auto blocks = split_blocks(src, CipherType::block_lenght);
ByteBlock tmp;
algorithm.encrypt(iv_, tmp);
xor_blocks(tmp, blocks[0], tmp);
swap(tmp, blocks[0]);
for(int i = 1; i < blocks.size(); i++) {
algorithm.encrypt(tmp, tmp);
xor_blocks(tmp, blocks[i], tmp);
swap(tmp, blocks[i]);
}
dst = join_blocks(blocks);
}
The decision to break the decryption function into its component parts seems redundant. This would be the case if the encryption mode with ciphertext feedback did not support concurrency for this procedure. Next, we will consider a variant of the decryption algorithm using std :: threads from the C ++ 11 standard.
Concurrency Decryption Function
template
void CFB_Mode::parallel_decrypt(const ByteBlock & src, ByteBlock & dst) const {
// length in blocks of CipherType::block_lenght
unsigned long const length =
src.size() / CipherType::block_lenght + (src.size() % CipherType::block_lenght ? 1 : 0);
// amount of threads which can perform really simultaniously
unsigned long const hardware_threads = std::thread::hardware_concurrency();
// blocks of size CipherType::block_lenght to perform on by one thread
unsigned long const min_per_thread = 1;
// amount of threads to satisfy current condition
unsigned long const max_threads = (length + min_per_thread - 1) / min_per_thread;
// amount of threads to create
unsigned long const num_threads = std::min(
hardware_threads != 0 ? hardware_threads : 2,
max_threads
);
// if we aren't able to use multiple threads call common decryptor
if(num_threads <= 1) {
decrypt(src, dst);
return;
}
std::cerr << "Running " << num_threads << " threads." << endl;
unsigned long const block_size = (length / num_threads) * CipherType::block_lenght;
std::vector init_vectors(num_threads);
std::vector results(num_threads);
std::vector threads(num_threads - 1);
init_vectors[0] = iv.deep_copy();
for(int i = 1; i < num_threads; i++)
init_vectors[i] = src(i * block_size - CipherType::block_lenght, CipherType::block_lenght);
unsigned long start_pos = 0;
for(unsigned long i = 0; i < num_threads - 1; i++) {
threads[i] = std::thread(
&CFB_Mode::decrypt_with_iv,
this,
src(start_pos, block_size),
std::ref( results[i] ),
std::ref( init_vectors[i] )
);
start_pos += block_size;
}
decrypt_with_iv(
src(start_pos, src.size() - start_pos),
results[num_threads - 1],
init_vectors[num_threads - 1]
);
for(auto & t : threads) t.join();
dst = join_blocks(results);
}
An example of a program encrypting a message
#include "mycrypto.hpp"
#include "Kuznyechik.hpp"
int main() {
ByteBlock key = hex_representation(
"8899aabbccddeeff0011223344556677fedcba98765432100123456789abcdef"
);
ByteBlock iv = hex_representation("abcdef12345600dacdef94756eeabefa");
ByteBlock msg = hex_representation("1122334455667700ffeeddccbbaa9988");
ByteBlock result;
CFB_Mode encryptor(Kuznyechik(key), iv);
encryptor.encrypt(msg, result);
return 0;
}
The project repository is located here .
