Regular oddities in the GOST Grasshopper and Stribog algorithms
Hi% username%!
Cryptographic algorithms in Russia do not pass through open contests, they simply let us down from above. And sooner or later it will strongly buzz us. This article is about the latest study of our guests.
In 2016, researchers showed that the permutation table in the Russian hashing and encryption algorithms Grasshopper and Stribog has a structure that is very far from random. This is after a trivial error was found in Stribog, reducing its resistance from 2,512 to 2,266 .
On January 29, 2019, a new study “Partitions in the S-Box of Streebog and Kuznyechik” was published, which explicitly hints at the theoretical possibility of a backdoor in these algorithms.
So, S-Box - or replacement table, is a key security element in many symmetric encryption and hashing algorithms. An example of such a table is shown in the figure.
In general, this table maps one bit sequence to another. But by what principle - always a big question.
State structures are often limited to their publication without any rational explanation. In the case of DES, the NSA suggested changing the S-Box before the algorithm became standard. Only many years later it turned out that this change actually increased the resistance of DES to differential cryptanalysis.
In the case of new guests, not everything is so rosy. The authors declared that the replacement table was randomly selected. Here is a slide from the presentation of the algorithm, which states that the authors chose a table at random. So that it does not have an explicit structure that would help produce effective cryptanalysis. (Red is what you chose)
Here is the table
But, first, as it turned out, it was not generated randomly, but with the help of a clever algorithm, which was picked up in 2015m.
Secondly, the authors did not leave attempts to find out the reason for this approach to the design of the S-Box and came up with very interesting results.
It turned out that the algorithms that form the replacement table are more than one. Different groups of researchers described completely different algorithms that have almost nothing in common, but come to the same table.
This led the authors of the original research to dig deeper into the structure of these algorithms and to find common elements that they succeeded in.
TKlog is a permutation construction, which the authors of the cryptanalysis named after the Russian office of TK-26, where the Grasshopper and Stribog were created. Her description is far beyond the scope of this article, anyone can refer to the original . In a nutshell, its key feature is the use of discrete logarithm, just like in asymmetric cryptography.
What is important is the fact that both versions of the replacement function from GOST-based algorithms are a special case of the TKlog construction. Like another replacement function from the Belarusian BelT algorithm . Functions are different, but they boil down to one.
The fact that there are very few different variants of the TKlog conversion speaks about the deliberate use of this particular, non-randomized structure instead of the random one shown on the slide.
A key property of the TKlog transform is that it works with the so-called cosets. And compares one to another.
The problem is that these adjacent classes are multiplicative, as in all ordinary algorithms. And there are additive.
So, the only known case where additive adjacent classes were used in the function of replacing block ciphers is a special creation of a backdoor . Information about this is in the work of 2016.
Such backdoors are called NOBUS, abbr. from “NObody But US”, these are vulnerabilities that only the authors of the algorithms can exploit.
The authors of cryptanalysis did not present new attacks on the existing GOST algorithms, but asked a fair question of the expediency of this whole circus with a supposedly random permutation table.
The NSA recently tried to push its lightweight symmetric algorithms Simon and Speck into standards. And the very fact of the existence of replacement tables with a design, the description of which was not provided, was enough to be banished from everywhere with pissing rags.
We have no such opportunity.
PS Do not forget that Stribog was used to generate the parameters of the new GOST-based elliptic curves. With it, hashed the mystical constant W.
Cryptographic algorithms in Russia do not pass through open contests, they simply let us down from above. And sooner or later it will strongly buzz us. This article is about the latest study of our guests.
In 2016, researchers showed that the permutation table in the Russian hashing and encryption algorithms Grasshopper and Stribog has a structure that is very far from random. This is after a trivial error was found in Stribog, reducing its resistance from 2,512 to 2,266 .
On January 29, 2019, a new study “Partitions in the S-Box of Streebog and Kuznyechik” was published, which explicitly hints at the theoretical possibility of a backdoor in these algorithms.
So, S-Box - or replacement table, is a key security element in many symmetric encryption and hashing algorithms. An example of such a table is shown in the figure.
In general, this table maps one bit sequence to another. But by what principle - always a big question.
State structures are often limited to their publication without any rational explanation. In the case of DES, the NSA suggested changing the S-Box before the algorithm became standard. Only many years later it turned out that this change actually increased the resistance of DES to differential cryptanalysis.
In the case of new guests, not everything is so rosy. The authors declared that the replacement table was randomly selected. Here is a slide from the presentation of the algorithm, which states that the authors chose a table at random. So that it does not have an explicit structure that would help produce effective cryptanalysis. (Red is what you chose)
Here is the table
But, first, as it turned out, it was not generated randomly, but with the help of a clever algorithm, which was picked up in 2015m.
Secondly, the authors did not leave attempts to find out the reason for this approach to the design of the S-Box and came up with very interesting results.
It turned out that the algorithms that form the replacement table are more than one. Different groups of researchers described completely different algorithms that have almost nothing in common, but come to the same table.
This led the authors of the original research to dig deeper into the structure of these algorithms and to find common elements that they succeeded in.
Tklog
TKlog is a permutation construction, which the authors of the cryptanalysis named after the Russian office of TK-26, where the Grasshopper and Stribog were created. Her description is far beyond the scope of this article, anyone can refer to the original . In a nutshell, its key feature is the use of discrete logarithm, just like in asymmetric cryptography.
What is important is the fact that both versions of the replacement function from GOST-based algorithms are a special case of the TKlog construction. Like another replacement function from the Belarusian BelT algorithm . Functions are different, but they boil down to one.
Hidden text
The fact that there are very few different variants of the TKlog conversion speaks about the deliberate use of this particular, non-randomized structure instead of the random one shown on the slide.
Splitting into related classes
A key property of the TKlog transform is that it works with the so-called cosets. And compares one to another.
The problem is that these adjacent classes are multiplicative, as in all ordinary algorithms. And there are additive.
So, the only known case where additive adjacent classes were used in the function of replacing block ciphers is a special creation of a backdoor . Information about this is in the work of 2016.
Such backdoors are called NOBUS, abbr. from “NObody But US”, these are vulnerabilities that only the authors of the algorithms can exploit.
Instead of conclusion
The authors of cryptanalysis did not present new attacks on the existing GOST algorithms, but asked a fair question of the expediency of this whole circus with a supposedly random permutation table.
The NSA recently tried to push its lightweight symmetric algorithms Simon and Speck into standards. And the very fact of the existence of replacement tables with a design, the description of which was not provided, was enough to be banished from everywhere with pissing rags.
We have no such opportunity.
PS Do not forget that Stribog was used to generate the parameters of the new GOST-based elliptic curves. With it, hashed the mystical constant W.
Source: https://habr.com/ru/post/439788/