Speed ​​hashing

High-speed hashing based on a new cryptographic algorithm

Unfortunately, mathematicians are poorly versed in the intricacies of programming, they invent something, and then the programmer has to implement it in the program code. It is not always possible to implement their algorithms efficiently.

This is especially evident in the recent Russian symmetric cryptography, Striborg and Grasshopper ... These algorithms cannot be effectively implemented in x86 / 64 software codes, a specialized crypto processor is needed.

Let's do the opposite and see what happens.

A programmer who knows how a modern x86 / 64 processor works will develop the most efficient symmetric encryption algorithm, and mathematicians, as in the good old days, let them do their main work, the cryptanalysis of the resulting solution.
')
Remembering that "the best is the enemy of good", let us take as a basis the "good" - GOST 28147-89. Then, following the medical principle “Do no harm”, we will strengthen it with the methods of multi-threaded calculations.

The following has been done:

• Increased key size to 256 bytes.
• Increased data block size to 256 bytes.
• The substitution operation is replaced by a permutation operation.
• In the cyclic shift introduced the operation of inverting groups of bits.
• The keys are entered in the form of permutation bits.
• The Feistel network is modified into a ring network of eight segments.
• The gamming mode is used with feedback, in two passes on the encrypted data.
• Passages are made with different permutations and ring shifts with the same keys.
• Before encryption, redundancy is removed from the encrypted text using a compressor.

Test implementation

The algorithm is implemented, and the first thing that is tested is its statistical parameters when generating a pseudo-random sequence (the compressor is turned off), this is how they look:



This is a typical result of NIST tests of new crypto-transformation. The results of tests on any random keys and initial fillings always fit into the statistical parameters of a random sequence.

The statistical parameters obtained in experiments on the norms of the 8-byte block cipher for a block cipher with a block size of 256 bytes are fantastic.

This is the same as, for example, throwing a coin 12 times and receiving an equal loss of "eagle" and "nutlets", to demand that the cube, also thrown 12 times, fall on each face twice a time ...

This is theoretically possible only with very high differential entropy between adjacent blocks and characterizes the level of complexity of the block cipher.

These gamma parameters are obtained with one round of conversion. The algorithm has a peculiarity - the speed of gamming depends on the performance of the RAM and cache, and not on the speed of the processor.

Russian Roulette, 2018 and its application

Recently, cryptographic algorithms have begun to receive sonorous names, such as "Magma", "Grasshopper", "Stribog", we will continue this tradition.

We will call this block cipher "Russian Roulette" or abbreviated as RU2 , in honor of the first purely Russian generator of random binary sequences, the rotating drum of a revolver ...

Well, besides that, crypto-transformation is built on rotations (ring shifts) of binary sequences. Such shifts there are only explicitly 192 pieces per round.
So the direct analogy with the drum of a revolver is obvious.

Previously, when introducing a parallel method for implementing GOST 28147-89 on XMM / YMM registers, we had to fully describe it, since it was officially certified by the FSB.
Now the situation is different, no official status is expected. Therefore, there will be no detailed description of the “Russian Roulette” algorithm, this is a kind of copyright protection. In short, the “Russian Roulette” algorithm will be proprietary for the time being and, accordingly, its full designation is Russian Roulette, 2018 or abbreviated RU2 .

The encryption algorithm, closed from research, is of course nonsense, since there is no confidence in the encryption reliability.

But nothing prevents the use of the RU2 algorithm to convert the encrypted text into a sequence of pseudo- randomness satisfying the requirements.

Then, the obtained pseudo-random sequence can be encrypted using well-known and “reliable” algorithms, in fact, all serious cryptographic systems are built.
In the meantime, “Russian Roulette” is used for high-speed hashing with an arbitrary size of the result of the hash function. This is important in backup and integrity control tasks.
Standard feedback gamma is turned into a Hash function if you make the second pass through the encrypted data. This is how the algorithm RU2 was originally implemented.
Double feedback gammaging was not previously considered as an embodiment of the hash function apparently due to the low speed of operation, although it has more reliable convolution parameters. This applies primarily to the avalanche effect, it affects not only the subsequent rounds of convolution, but also the previous ones.

Moreover, the obtained characteristics of the hash function are reliably verified by statistical tests, because all the received ciphertext, which is a reliable pseudo-random gamut, becomes a hash.

From this range, arbitrary chunks can be cut to store the hash value. A block with a size of 1024Bytes is now used, it is much more reliable than a block of 64Bytes in the most “advanced” standard SHA3-512.

Hashing RU2 protects data from viewing / modification, but until cryptographers are convinced that the algorithm is strong, we will consider it as password data protection for access restriction.

Practical implementation of RU2

The Russian Roulette algorithm is built into the forensic duplicator of HDD and SDD drives. The algorithm is used there to create differential backups, integrity control, password-based access restriction and information compression.

A compressor for removing redundancy has already been written earlier in the article “ New algorithm for high-speed data compression,” hashing is used to confirm the integrity of copied data, and in the case of entering a password, also for “password protection” of the received dumps from viewing / modification.

Here are the speed characteristics of RU2 obtained in real work on the creation of a differential backup:



Copying speed is limited by the parameters of the reader, a USB 3.0-SATA bridge cannot provide greater speed reading the SSD disk.

At an input stream speed of 360MegaBytes / sec. RU2 algorithm loads the processor by only 5% at a reduced frequency of 1.4GHz. This ensures the compression of information, its hashing and encryption (password protection) dump.

Traditional hashing systems cannot provide such performance. For comparison, here’s how the hashing system built into Acronis works when creating a differential backup of the same disk:



The processor hashes the input data stream at a speed of 340 MegaBytes / sec., While running at a frequency of 3.8GigHz, and is loaded at 28%.

If we convert the obtained results into the limiting parameters for a dual-core processor operating at a frequency of 3.8GHz, then the Acronis hashing system can provide a throughput of 1.4Gbytes / sec.

Much more loaded with tasks (hashing + compression + "password protection") the "Russian Roulette" algorithm provides a speed of 21Gbytes / sec.

In other words, RU2 hashing works an order of magnitude faster than standard hashing implemented in Acronis.

In addition, Russian Roulette provides the pseudo-random number generation rate of 12 GBytes per second. This is the fastest generator of pseudo-random sequences known to meet the requirements of the official NIST tests.

Generation of random numbers, hashing, password protection, while this is enough for Russian Roulette.

"... But what about cryptography ?, - and cryptography later ...".