Speed ​​hashing

High-speed hashing based on a new cryptographic algorithm


Unfortunately, mathematicians have little knowledge of the intricacies of programming, they invent something, and then the programmer must 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 the 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 being tested is its statistical parameters when generating a pseudo-random sequence (the compressor is turned off), here’s what they look like:

image

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

The statistical parameters obtained in the 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 “nutlet”, 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 gamming speed depends on the performance of the RAM and the cache, and not on the processor speed.

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, and besides, crypto-transformation is based on the rotation of the binary sequences. There are only 192 such changes there in an explicit form in one round.
So the direct analogy with a drum 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 as 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 algorithm RU2to convert the ciphertext into a sequence of pseudo-randomness satisfying the requirements.

Then, the resulting pseudo-random sequence can be encrypted using well-known and “reliable” algorithms, and all serious cryptographic systems are built in this way.
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 a 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 checked 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. Now a block of 1024Byte is 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.

The compressor for removing redundancy has already been written in the article “ New algorithm for high-speed data compression,” hashing is used to confirm the integrity of the 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:

image

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% with 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 hash system built into Acronis when creating a differential backup of the same disk:

image

The processor hashes the input data stream at a speed of 340 Megabytes / sec., It runs at a frequency of 3.8G / G and is loaded by 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.4Gigabytes / 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 at the level of 12 Gbytes per second. This is the fastest generator of pseudo-random sequences known to meet the requirements of the official NIST tests.

Random number generation, hashing, password protection, while this is enough for Russian Roulette.

"... Well, and cryptography ?, - and cryptography then ....".

Also popular now: