“Battle algebra” or “according to GOST” cryptography

At first glance, the title of the article is absurd, apparently the only thing that comes to the mind of the reader is the use of calculation methods in ballistics. But there is more likely military physics than military mathematics. The field of application of “pure” mathematics in the military sphere is cryptography. I will not discuss the importance of the topic, it has been clear since the time of Enigma . Currently, very troubling events are taking place in cryptography, to which, unfortunately, Russian experts do not respond. And if they react, then in a very specific way, it has already been written about , but apparently not enough, we will have to continue the topic.

"Features of national cryptography"


In mid-2015, several new GOSTs standardizing cryptographic operations were adopted. Even the title pages of these most important state documents cause, to say the least, bewilderment. Look, here is one of them:

image

I, too, "for the first time" see official documents of special state importance in the development of which a certain commercial company from the category of "Horns and Hooves" took part.

The Infotex company does not even have its own premises and is located on the premises of the Office Shopping Center (quote from the company's website). Who does not believe can see for himself, here is a link to the public website of this company .

By the way, standards of cryptographic algorithms were developed, and not GOST for the production of Doctor's sausage ...

In terms of encryption strength, the new GOSTs are a step backward. I will not be unfounded, here is just one example - the requirement of secrecy to specific sets of random numbers called “replacement blocks” was removed from the new algorithms.

Previously, replacement blocks were secret and issued by the regulatory body in a “special” order, but now they are public and unchanged. Accordingly, cryptanalysts (as cipher crackers are so politely called) have become much easier to work with. Their task now boils down only to calculating encryption keys; earlier, it was also necessary to calculate the values ​​of the replacement blocks.

The weakening of the cryptographic strength of Russian encryption tools is taking place against the background of the introduction of quantum methods of cryptanalysis (breaking encrypted information) by our potential “friends” and the race of computer technologies.

It is no secret that the appearance of really working Quantum computers was primarily initiated by the needs of cryptanalysts, there is even the public term “Quantum Cryptanalysis”.

Public Information on Quantum Cryptanalysis


It has long been no secret that algorithms for the cryptanalysis of symmetric and asymmetric encryption have been developed specifically for quantum computers. Algorithms were, there were no computers, now they appeared:

image

Quote

Until recently, it was believed that symmetric encryption does not lend itself well to quantum cryptanalysis methods, but here is information regarding breaking block ciphers with the new (well-forgotten old) method.

image

Article

Please note, the news “slipped” in 2007, after that there was no mention of this method in open Internet sources.

At first glance, it’s not clear what this is about, I’ll try to explain it “on fingers”, radio electronics specialists and signalmen will easily understand me ...

First, this is a return to the ancient analog solver. There used to be such computing facilities, then they were “electric”, but now they have become “quantum”. But the essence of this does not change.

Secondly, in the described setup, a new technique of quantum cryptanalysis is used and it needs to be explained.

Take the simplest case of gamma generation, developed for example, based on the old algorithm GOST 28147-89. In our case, gamma is a sequence of 32 bit numbers, the more such numbers the better. We will consider each such number as the instantaneous value of the wave function in the process of digitization.

We digitize the resulting gamma sequence as a wave, and using the Fourier transform, we decompose it into harmonic components.

As a result, we get a classic and very stable picture of pseudo-random “pink” noise, there will be a stable and limited set of frequencies modulated in amplitude and phase.

Now we put encrypted text on the gamut, we get encrypted text, it can also be represented as a digitized wave function, but already modulated by encrypted text.

In fact, any encryption is a process identical to radio transmission, when the high-frequency radiation obtained as a result of the cryptographic algorithm is modulated by a low-frequency payload signal (encrypted text).

In our example, gamma is a high-frequency signal, and encrypted text is a low-frequency modulator. Hacking using quantum cryptography is essentially identical to the operation of the detector receiver, the original high-frequency wave function is cut off and the low-frequency modulating component is extracted. Such a “detector” method will work the better, the smaller the number of components of harmonic frequencies available in the ciphertext, and the longer the encrypted message.

Ideally, ciphertext possessing the properties of true “white” noise with an infinite number of harmonic components cannot be cracked by this method.

The only thing follows from this, cryptographic algorithms, in addition to algorithmic complexity (the number of equations for calculating the key values) and algebraic complexity (the complexity of solving these equations), must also have the highest achievable statistical complexity (be as close as possible to the parameters of "white noise").

So far, no one pays attention to the statistical complexity of ciphertexts. The ciphertexts obtained using standardized cryptographic algorithms in Russia are very far from the statistical parameters of truly random sequences.

The reason for this is very specific, and we will discuss it further.

"Sawed" GOST encryption


Again, I have to return to the "features of national cryptography", but I will start from afar. Once upon a time, when they could not even think of computers, mechanical typewriters were used instead of computers. In the USSR, power obsessed with the idea of ​​total control over its citizens typed typewriters, filing letters in an inconspicuous way. So that the printed text can be identified with a particular typewriter.

Something similar happened in cryptography, the “elder brother”, with some effort, can read encrypted texts without even knowing the key information. To do this, specially selected replacement blocks are used, the use of which is mandatory.

Theoretically, replacement blocks should consist of random numbers, but in practice they contain "not random, but pseudorandom" numbers. In other words, there is a hidden algorithm in the replacement blocks that allows you to read ciphertexts without knowing the keys.

This is true for the two block ciphers standardized in Russia, the first is now called Magma (the old simplified GOST 28147-89), the second is called The Grasshopper, it is discredited even before its official adoption as a standard.

Information about the “filed” replacement blocks roams at the rumor level, of course it has no official confirmation, but the facts are a stubborn thing, here they are:

- In relation to “Magma” there is an official statement in the “pseudo-randomness” of the replacement blocks expressed during the consideration of the application for inclusion in the international standard for block encryption ISO / IEC 18033-3. In 2010, the International Organization for Standardization (ISO / IEC JTC 1 / SC 27) began a study of GOST 28147-89, but after an analysis of the provided replacement blocks, certification was refused.

- Regarding the “pseudo-randomness” of the Grasshopper replacement blocks, there are irrefutable mathematical calculations. They were officially presented at the CRYPTO conference in 2015. Authors Alex Biryukov, Leo Perrin and Alexei Udovenko presented a report that states that:

"Despite the claims of the developers, the Grasshopper S-block values ​​and the Stribog hash functions are not random numbers, but are generated based on a hidden algorithm that was restored using reverse engineering methods."

“Sawing” of replacement blocks as such is of little interest to us, if it were not for one “but,” - the algorithm hidden in the replacement blocks significantly weakens the statistical parameters of the ciphertext.

From the point of view of statistical parameters, the ciphertext obtained on the basis of the Russian symmetric encryption algorithms is seriously weakened and can be easily cracked on quantum crypto calculators.

Well, without this, who can guarantee that the algorithms for reading encrypted text without key information have not "leaked"? As it was, for example, with bookmarks in the new building of the American Embassy. And the English-speaking businessmen of now-former Russian generals “crashed” cryptography in the early 2000s on sultry seas on superyachts. What happened there is unknown, but the wise in such situations always suggests the worst ...

The eternal Russian question "What to do?"


A thoughtful reader, having read the above, will probably object that this trouble can be easily defeated by using honest replacement blocks made up of really random numbers. That's right, the statistical parameters of the ciphertexts of Russian symmetric encryption algorithms can be significantly improved due to replacement blocks, but this is not enough. It is necessary to complicate encryption algorithms, and the NSA of the USA speaks about this:

image

Article

So far we are talking about increasing the size of the key, but even this has not been done in our new GOSTs, not to mention the introduction of more robust algorithms.

It seems that a new Grasshopper cipher algorithm has appeared, but in its structure it is fully consistent with the AES algorithm of twenty years ago, and has the same cryptographic strength. And twenty years ago they did not even guess about this "trouble", now called quantum cryptanalysis.

So while we are defenseless, and moreover, it is not known what our potential adversaries really manage to read in our encrypted messages, because according to Snowden’s documents they already have quantum computers ...

Moreover, they now even have public access:

image

Article

So in our cryptography the next classic situation with the “naked king” is very likely . Soon, the head of the 8th FSB center will have a new first deputy, according to tradition, cryptographers were always the first deputies there. The previous “Left” to understand who left and who he was in this position, one very characteristic link: image
Article

New cryptographic GOSTs adopted in 2015 and the encryption algorithm “Grasshopper”, which was discussed above, the brainchild of A.S. Kuzmina. Even the name of this encryption algorithm came from his last name (Kuzmin + Nechaev). Let's hope that the new head of Russian cryptography will restore order in his troops.

PSIn conclusion, about one feature of the troops of "combat algebra" - about the losses are silent. Where is it seen that the “tragic death" of the country's main cryptographer and the FSB lieutenant general is not announced in news feeds?

Also popular now: