Steebog and Cybersecurity

Steebog and Cybersecurity

Derived from the god of rash wind in ancient Slavic mythology

If you are into cybersecurity, you will know about the famous hashing methods of MD5, SHA1 and SHA2 (SHA-256). There’s a chance you might know about the Gost hash, but do you know about the Streebog hashing method?

And, so, NIST defines many of the standards that we use in cybersecurity. This includes AES and SHA-3. Along with this, they have also defined the FIPS standards, such as FIPS 186–5, which defines the standard for digital signatures.

But, NIST does not have a clean track record for transparency in cryptography. In 2006, NIST and the ISO pushed the adoption of the Dual EC random number generator. Within a year, it was shown to have a backdoor, and where some thought that the NSA set out to create a backdoor function for the generation of random numbers that only they could break.

And, so, for cryptography, some countries and regions of the world have continued to define their standards. This includes the SM series for cryptography in China, including the SM3 hashing method and the SM4 symmetric key method. These have both been integrated into OpenSSL 3.0.

Another region of the world that has continued to define its own standards is maintained by the Euro-Asian Council for Standardization, Metrology and Certification (EASC):

EASC is part of the Commonwealth of Independent States (CIS) and which includes Russia, Belarus, Moldova, Kazakhstan, Azerbaijan, Armenia, Kyrgyzstan, Uzbekistan, Tajikistan, Georgia, and Turkmenistan. The first standard — GOST (ГОСТ — GOvernment STandard) — was published in 1968, and it has since been recognised by the ISO. Ukraine removed the GOST standard in 2015.

GOST cipher

The GOST block cipher uses a 64-bit block and is defined in RFC 5830 [here]:

It was basically an alternative to the DES method and uses a Feistel network of 32 rounds. The GOST hashing method is then based on this block cipher. A new standard for GOST defines a 128-bit block cipher (Kuznyechik).

With the GOST hashing method, we split the message (M) into 256-bit blocks (m_1 to m_n), and pad the last block with zero bits. Each block then uses a step hash, and where H_1 is 256 bits of zero:

After OpenSSL 1.1.0, the support for GOST was dropped but was still supported by Bouncy Castle [here]. The most typical form of Gost uses S-boxes (known as Gost94). A test vector for Gost94 is [here]:

GOST("The quick brown fox jumps over the lazy dog") =
  9004294a361a508c586fe53d1f1b02746765e71b765472786e4770d565830a76

An example is [here]:

Steebog

While GOST is still theoretically secure, there were a number of attacks on it which reduced its strength. And, so, while NIST continued in their standardisation for SHA-3, in 2012, the GOST standards released Kuznyechik (a 128-bit block cipher) and the Steebog hashing method (GOST R 34.11–2012 Information Technology — Cryptographic Information Security — Hash Function):

The method is now known as Streebog. This was named after Stribog — the god of rash wind in ancient Slavic mythology. It differs greatly from SHA-3, and whereas SHA-3 uses an efficient sponge function, Streebog uses the Merkle–Damgård construction (and which is used with MD5, SHA-1 and SHA-2). Overall, it is available in a 256-bit or 512-bit form. Some test vectors are:

Streebog-256("The quick brown fox jumps over the lazy dog")
0x 3e7dea7f2384b6c5a3d0e24aaa29c05e89ddd762145030ec22c71a6db8b2c1f4
Streebog-256("The quick brown fox jumps over the lazy dog.")
0x 36816a824dcbe7d6171aa58500741f2ea2757ae2e1784ab72c5c3c6c198d71da
Streebog-512("The quick brown fox jumps over the lazy dog")
0x d2b793a0bb6cb5904828b5b6dcfb443bb8f33efc06ad09368878ae4cdc8245b9 \
   7e60802469bed1e7c21a64ff0b179a6a1e0bb74d92965450a0adab69162c00fe
Streebog-512("The quick brown fox jumps over the lazy dog.")
0x fe0c42f267d921f940faa72bd9fcf84f9f1bd7e9d055e9816e4c2ace1ec83be8 \
   2d2957cd59b86e123d8f5adee80b3ca08a017599a9fc1a14d940cf87c77df070

As with GOST, OpenSSL has now integrated Streebog. But, we can turn to Libre OpenSSL for an implementation. In the following, we have the Linux and Windows implementation [here]:

echo -n "The quick brown fox jumps over the lazy dog" | openssl_libre dgst -streebog256
echo | set /p = "The quick brown fox jumps over the lazy dog" | openssl_libre dgst -streebog256

Message: The quick brown fox jumps over the lazy dog
Mode: streebog256
========
: 3e7dea7f2384b6c5a3d0e24aaa29c05e89ddd762145030ec22c71a6db8b2c1f4

An implementation is [here]:

Cracking Steebog

A core part of the SHA-3 evaluation was the opportunity for researchers to probe the security and performance of the methods, and so, in 2013, the Russian Technical Committee for Standardization “Cryptography and Security Mechanisms” (TC 2) set up an open competition for the evaluation of the new ciphers:

Since then, there have been a number of attacks against Streebog, including one which managed to reverse engineer the secret 8-bit S-boxes [1]:

Conclusions

It’s a shame that OpenSSL does not include Gost and Streebog, but Libre OpenSSL does support it. You can try it here:

https://asecuritysite.com/openssl/openssl_full2l

Reference

[1] Biryukov, A., Perrin, L., & Udovenko, A. (2016, April). Reverse-engineering the S-box of Streebog, Kuznyechik and STRIBOBr1. In Annual international conference on the theory and applications of cryptographic techniques (pp. 372–402). Berlin, Heidelberg: Springer Berlin Heidelberg.