The Streebog Algorithm

The Streebog Algorithm

Introduction

Streebog is the Russian national hash function standard, GOST R 34.11-2012. It makes a digest of 512 bits, or a shorter one of 256 bits. It replaced the older GOST R 34.11-94 hash, and it works together with the GOST R 34.10-2012 signature scheme.

Streebog is built around a block cipher. Each 64-byte block goes through a 12-round cipher that looks like AES. Its state is a matrix of bytes, and each round has a key addition, an S-box, a byte transposition, and a linear map. Streebog also adds two extra steps at the end of every hash. It mixes in the length of the message and the sum of all of its blocks. This guide explains each step, and it follows the example of RFC 6986 from the first byte to the last. The FAQ explains why different tools print different digests.

Table of Contents

• History and Standards
• Vectors and Byte Order
• The Three Stages
• The Compression Function
• The Three Layers
• The Key Schedule
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Security Status
• FAQ
• References

History and Standards

The FSB, the Federal Security Service of Russia, and the company InfoTeCS designed Streebog. It was published as the standard GOST R 34.11-2012. The name comes from Stribog, the god of the wind in Slavic mythology. It replaced GOST R 34.11-94, which was obsolete. It has also been described as a response to the NIST SHA-3 competition.

The IETF published a description of the standard as RFC 6986 in August 2013. This RFC is informational, and it comes with worked examples that print every key and every round. Streebog is also part of ISO/IEC 10118-3:2018. In 2013, the Russian standards committee TC 26 held an open competition for the cryptanalysis of Streebog. The designers have said that its constants came from a Streebog-like hash of 12 natural-language messages.

Vectors and Byte Order

The standard works with 512-bit vectors. A vector is written with its highest byte first, and its bytes are numbered from the right, so byte 0 is the last pair of hexadecimal digits. This matters in two places.

The first place is the message. The standard reads a message as a number, and the first byte of the message is the least significant byte. So the 63-byte message 012345678901234567890123456789012345678901234567890123456789012 is printed in the RFC as 3231303938..., with the last character first.

The second place is the digest. The RFC prints the result with its highest byte first. Most libraries, including the Linux kernel and Botan, whose test vectors I used, write the same value with its bytes in the opposite order. So one value has two spellings. The digest of the message above is 486f64c1... in the RFC and 1b54d01a... in programs. The empty message gives 3f539a21... in programs, which is the form you see in most tables. This guide uses the program form for digests, and the RFC form for the internal 512-bit vectors. The worked example below prints one complete digest in both spellings, so you can compare them.

The Three Stages

Streebog keeps three values: the chaining value h, a counter N, and a checksum chk. The message is cut into 64-byte blocks, and the hash has three stages.

1. Blocks. For every full 64-byte block m, compute h = g(N, h, m). Then add 512 to N, and add m to chk. All additions are modulo 2^512.
2. The last block. Pad the remaining bytes, from 0 to 63 of them, with one bit and zeros, so that they fill 512 bits, which gives m = 0...0 || 1 || rest. Then compute h = g(N, h, m), add the number of bits of the rest to N, and add the padded m to chk.
3. Finishing. Compute h = g(0, h, N), and then h = g(0, h, chk). The length and the checksum go through the same function as the message, with a counter of zero.

The starting value of h is 512 zero bits for Streebog-512. For Streebog-256, each byte of h starts as 0x01, and at the end only the leftmost 256 bits of h are kept. Because the digest comes after the two finishing calls, the usual length-extension trick, which restarts the hash from a published digest, does not work directly. An attacker would need the chaining value from before the two finishing calls, and the published digest is not that value.

The Compression Function

The function g takes the counter N, the chaining value h, and a message vector m:

g(N, h, m) = E( LPS(h xor N), m )  xor  h  xor  m

This is the Miyaguchi-Preneel mode. It uses the block cipher E, whose key is LPS(h xor N) and whose plaintext is m, and then it XORs the result with h and m. The cipher E works like this:

K1 = the key
K(i+1) = LPS( K(i) xor C(i) )          for i = 1 to 12
state = m
for i = 1 to 12:
    state = LPS( state xor K(i) )
result = state xor K13

So the cipher has 12 rounds. Each round XORs the state with a round key and applies the three layers S, P, and L, which together are called LPS. After the last round, one more XOR with the thirteenth key finishes the cipher.

The Three Layers

S, the S-box. The first layer replaces each of the 64 bytes through a fixed table, Pi, with 256 entries. The table starts with fc ee dd 11 cf 6e 31 16. So Pi(0) = fc, Pi(1) = ee, and Pi(255) = b6.

P, the byte transposition. The 64 bytes are viewed as an 8 by 8 matrix, and the matrix is transposed. In formulas, byte i of the result is byte Tau(i) of the input, where Tau starts 0 8 16 24 32 40 48 56 1 9 17 25 33 41 49 57. So the first four bytes of the result are bytes 0, 8, 16, and 24 of the input. This moves bytes between the eight 64-bit words, so that the next layer mixes them.

L, the linear map. The 64 bytes are viewed as eight 64-bit words, and each word is multiplied by a fixed 64 by 64 bit matrix A. In practice, L looks at the bits of a word from the highest bit down. The highest bit selects row 0 of the matrix, the next bit selects row 1, and so on. It XORs together the rows whose bit is one. Row 0 is 8e20faa72ba0b470, row 1 is 47107ddd9b505a38, and row 63 is 641c314b2b8ee083. This layer mixes the bytes inside each word, a job like the one MixColumns has in AES.

Together, the three layers look like an AES round. S is the nonlinear layer, P moves bytes between words, and L diffuses each word.

The Key Schedule

The round keys use the same layers. The first key is the cipher key itself, which for g is LPS(h xor N). Each next key is LPS(K(i) xor C(i)). The twelve constants C(1) to C(12) are fixed 512-bit values. For example, C(1) is:

b1085bda1ecadae9ebcb2f81c0657c1f
2f6a76432e45d016714eb88d7585c4fc
4b7ce09192676901a2422a08a460d315
05767436cc744d23dd806559f2a64507

All 13 keys can be computed before the first round. The key schedule costs as much as encrypting a block, because it runs the same layers 12 more times.

Interactive Visualizer

The visualizer above runs this exact algorithm. Choose Streebog-512 or Streebog-256, type a message of up to 127 bytes, and click Hash. The log shows every call of the compression function. For each call, it lists the input and the first key. Then, for each of the 12 rounds, it shows the state after the key XOR, the S-box, the transposition, and the linear map, followed by the next key. Every row is a 512-bit vector, split into eight 64-bit words, with the highest bytes first, as in the RFC. The digest is shown with its bytes in the program order. The default message is the one from the RFC, so you can compare the page with this guide.

A Worked Example

This follows the example of RFC 6986, Section 10.1, with the 63-byte message 012345678901234567890123456789012345678901234567890123456789012 and Streebog-512. The values up to the digests of this message are printed in the RFC, and the code in this guide reproduces them. The last paragraph of the example uses other messages, and its source is named there.

The last block. The message is shorter than 64 bytes, so there is only one block. It gets one padding bit just above the message, which gives:

01323130393837363534333231303938
37363534333231303938373635343332
31303938373635343332313039383736
35343332313039383736353433323130

The leading 01 is the padding bit. The counter N, the checksum, and h all start at zero.

The first key. For g(0, 0, m) the key is LPS(0). The S-box turns each zero byte into Pi(0), so the vector becomes fcfcfcfcfcfcfcfcfcfcfcfcfcfcfcfc repeated. The transposition changes nothing, because all bytes are equal. The linear map turns each 64-bit word into b383fc2eced4a574. So K1 is that word eight times:

b383fc2eced4a574b383fc2eced4a574
b383fc2eced4a574b383fc2eced4a574
b383fc2eced4a574b383fc2eced4a574
b383fc2eced4a574b383fc2eced4a574

Round 1. XORing the message with K1 gives:

b2b1cd1ef7ec924286b7cf1cffe49c4c
84b5c91afde694448abbcb18fbe09646
82b3c516f9e2904080b1cd1ef7ec9242
86b7cf1cffe49c4c84b5c91afde69444

The S-box turns it into:

4645d95fc0beec2c432f8914b62d4efd
3e5e37f14b097aead67de417c220b048
2492ac996667e0ebdf45d95fc0beec2c
432f8914b62d4efd3e5e37f14b097aea

The transposition turns that into:

46433ed624df433e452f5e7d92452f5e
d98937e4acd989375f14f117995f14f1
c0b64bc266c0b64bbe2d092067be2d09
ec4e7ab0e0ec4e7a2cfdea48eb2cfdea

The linear map gives the state after round 1:

e60059d4d8e0758024c73f6f3183653f
56579189602ae4c21e7953ebc0e212a0
ce78a8df475c2fd4fc43fc4b71c01e35
be465fb20dad2cf690cdf65028121bb9

The next key. The vector K1 xor C(1) is the first block below, and LPS of it gives K2, the second block.

028ba7f4d01e7f9d5848d3af0eb1d96b
9ce98a6de0917562c2cd44a3bb516188
f8ff1cbf5cb3cc7511c1d6266ab47661
b6f5881802a0e8576e0399773c72e073

d0b00807642fd78f13f2c3ebc774e80d
e0e902d23aef2ee9a73d010807dae9c1
88be14f0b2da27973569cd2ba0513010
36f728bd1d7eec33f4d18af70c46cf1e

Rounds 2 to 12. The state after round 2 is:

18e77571e703d19548075c574ce5e50e
0480c9c5b9f21d45611ab86cf32e352a
d91854ea7df8f863d46333673f62ff2d
3efae1cd966f8e2a74ce49902799aad4

After round 12 it is:

f35b0d889eadfcff73b6b17f33413a97
417d96f0c4cc9d30cda8ebb7dcd5d1b0
61e620bac75b367370605f474ddc0060
03bec4c4d7ce59a73fbe6766934c55a2

The cipher output. The thirteenth key is:

0f79104026b900d8d768b6e223484c97
61e3c585b3a405a6d2d8565ada926c3f
7782ef127cd6b98290bf612558b4b60a
a3cbc28fd94f95460d76b621cb45be70

XORing it with the state gives the output of the cipher:

fc221dc8b814fc27a4de079d10097600
209e5375776898961f70bded0647bd8f
1664cfa8bb8d8ff1e0df3e621568b66a
a075064b0e81cce132c8d1475809ebd2

The first call. The result of g is this output XOR h (zero) XOR m:

fd102cf8812ccb1191ea34af21394f38
17a86641445aa9a626488adb33738ebd
2754f6908cbbbac5d3ed0f522c50815c
954135793fb1f5d905fee4736b3bdae2

Length and checksum. The message has 504 bits, so N becomes 1f8, and the checksum is m. The call g(0, h, N) gives:

5c881fd924695cf196c2e4fec20d14b6
42026f2a0b1716ebaabb7067d4d59752
3d2db69d6d3794622147a14f19a66e7f
9037e1d662d34501a8901a5de7771d7c

The last call, g(0, h, chk), gives the final value, as the RFC prints it:

486f64c1917879417fef082b3381a4e2
11c324f074654c38823a7b76f830ad00
fa1fbae42b1285c0352f227524bc9ab1
6254288dd6863dccd5b9f54a1ad0541b

Written with its bytes in the opposite order, as programs do, the digest is:

1b54d01a4af5b9d5cc3d86d68d285462
b19abc2475222f35c085122be4ba1ffa
00ad30f8767b3a82384c6574f024c311
e2a481332b08ef7f41797891c1646f48

For Streebog-256, the starting h is different, and the digest is the leftmost 256 bits of the result of the last call. For this message it is 9d151eefd8590b89daa6ba6cb74af9275dd051026bb149a452fd84e5e57b5500.

Other messages. These are not in the RFC. The empty message gives 3f539a213e97c802cc229d474c6aa32a825a360b2a933a949fd925208d9ce1bb with Streebog-256 and 8e945da209aa869f0455928529bcae4679e9873ab707b55315f56ceb98bef0a7362f715528356ee83cda5f2aac4c6ad2ba3a715c1bcd81cb8e9f90bf4c1c1a8a with Streebog-512. The Streebog-256 form matches Botan’s test vectors. The sentence The quick brown fox jumps over the lazy dog gives 3e7dea7f2384b6c5a3d0e24aaa29c05e89ddd762145030ec22c71a6db8b2c1f4 with Streebog-256, and that value is quoted on Wikipedia, together with the empty-message digest. Flipping one bit of the RFC message changes 245 of the 512 digest bits.

Python Implementation

This is a complete Streebog-512 and Streebog-256. A 512-bit vector is a Python integer, so the S-box, the transposition, and the linear map can be written close to their definitions. All tables were copied from RFC 6986 by a script. The function cipher returns every intermediate value, so you can print the steps shown above.

# streebog.py
#
# Streebog, the Russian hash function GOST R 34.11-2012 (RFC 6986), in its
# 512-bit and 256-bit forms. It is a Merkle-Damgard hash, but the compression
# function is a dedicated 12-round block cipher built from an S-box, a byte
# permutation, and a linear map, and every message goes through two extra
# calls that mix in its length and a checksum. All tables were copied from the
# RFC by script. Vectors are 512-bit integers, with byte 0 on the right.

# the S-box, applied to every byte
PI = [
    252, 238, 221,  17, 207, 110,  49,  22, 251, 196, 250, 218,  35, 197,   4,  77,
    233, 119, 240, 219, 147,  46, 153, 186,  23,  54, 241, 187,  20, 205,  95, 193,
    249,  24, 101,  90, 226,  92, 239,  33, 129,  28,  60,  66, 139,   1, 142,  79,
      5, 132,   2, 174, 227, 106, 143, 160,   6,  11, 237, 152, 127, 212, 211,  31,
    235,  52,  44,  81, 234, 200,  72, 171, 242,  42, 104, 162, 253,  58, 206, 204,
    181, 112,  14,  86,   8,  12, 118,  18, 191, 114,  19,  71, 156, 183,  93, 135,
     21, 161, 150,  41,  16, 123, 154, 199, 243, 145, 120, 111, 157, 158, 178, 177,
     50, 117,  25,  61, 255,  53, 138, 126, 109,  84, 198, 128, 195, 189,  13,  87,
    223, 245,  36, 169,  62, 168,  67, 201, 215, 121, 214, 246, 124,  34, 185,   3,
    224,  15, 236, 222, 122, 148, 176, 188, 220, 232,  40,  80,  78,  51,  10,  74,
    167, 151,  96, 115,  30,   0,  98,  68,  26, 184,  56, 130, 100, 159,  38,  65,
    173,  69,  70, 146,  39,  94,  85,  47, 140, 163, 165, 125, 105, 213, 149,  59,
      7,  88, 179,  64, 134, 172,  29, 247,  48,  55, 107, 228, 136, 217, 231, 137,
    225,  27, 131,  73,  76,  63, 248, 254, 141,  83, 170, 144, 202, 216, 133,  97,
     32, 113, 103, 164,  45,  43,   9,  91, 203, 155,  37, 208, 190, 229, 108,  82,
     89, 166, 116, 210, 230, 244, 180, 192, 209, 102, 175, 194,  57,  75,  99, 182,
]

# the byte permutation tau
TAU = [
     0,  8, 16, 24, 32, 40, 48, 56,  1,  9, 17, 25, 33, 41, 49, 57,
     2, 10, 18, 26, 34, 42, 50, 58,  3, 11, 19, 27, 35, 43, 51, 59,
     4, 12, 20, 28, 36, 44, 52, 60,  5, 13, 21, 29, 37, 45, 53, 61,
     6, 14, 22, 30, 38, 46, 54, 62,  7, 15, 23, 31, 39, 47, 55, 63,
]

# the 64 rows of the linear map, 64 bits each
A = [
    0x8e20faa72ba0b470, 0x47107ddd9b505a38, 0xad08b0e0c3282d1c, 0xd8045870ef14980e,
    0x6c022c38f90a4c07, 0x3601161cf205268d, 0x1b8e0b0e798c13c8, 0x83478b07b2468764,
    0xa011d380818e8f40, 0x5086e740ce47c920, 0x2843fd2067adea10, 0x14aff010bdd87508,
    0x0ad97808d06cb404, 0x05e23c0468365a02, 0x8c711e02341b2d01, 0x46b60f011a83988e,
    0x90dab52a387ae76f, 0x486dd4151c3dfdb9, 0x24b86a840e90f0d2, 0x125c354207487869,
    0x092e94218d243cba, 0x8a174a9ec8121e5d, 0x4585254f64090fa0, 0xaccc9ca9328a8950,
    0x9d4df05d5f661451, 0xc0a878a0a1330aa6, 0x60543c50de970553, 0x302a1e286fc58ca7,
    0x18150f14b9ec46dd, 0x0c84890ad27623e0, 0x0642ca05693b9f70, 0x0321658cba93c138,
    0x86275df09ce8aaa8, 0x439da0784e745554, 0xafc0503c273aa42a, 0xd960281e9d1d5215,
    0xe230140fc0802984, 0x71180a8960409a42, 0xb60c05ca30204d21, 0x5b068c651810a89e,
    0x456c34887a3805b9, 0xac361a443d1c8cd2, 0x561b0d22900e4669, 0x2b838811480723ba,
    0x9bcf4486248d9f5d, 0xc3e9224312c8c1a0, 0xeffa11af0964ee50, 0xf97d86d98a327728,
    0xe4fa2054a80b329c, 0x727d102a548b194e, 0x39b008152acb8227, 0x9258048415eb419d,
    0x492c024284fbaec0, 0xaa16012142f35760, 0x550b8e9e21f7a530, 0xa48b474f9ef5dc18,
    0x70a6a56e2440598e, 0x3853dc371220a247, 0x1ca76e95091051ad, 0x0edd37c48a08a6d8,
    0x07e095624504536c, 0x8d70c431ac02a736, 0xc83862965601dd1b, 0x641c314b2b8ee083,
]

# the 12 iteration constants, 512 bits each
C = [
    0xb1085bda1ecadae9ebcb2f81c0657c1f2f6a76432e45d016714eb88d7585c4fc4b7ce09192676901a2422a08a460d31505767436cc744d23dd806559f2a64507,
    0x6fa3b58aa99d2f1a4fe39d460f70b5d7f3feea720a232b9861d55e0f16b501319ab5176b12d699585cb561c2db0aa7ca55dda21bd7cbcd56e679047021b19bb7,
    0xf574dcac2bce2fc70a39fc286a3d843506f15e5f529c1f8bf2ea7514b1297b7bd3e20fe490359eb1c1c93a376062db09c2b6f443867adb31991e96f50aba0ab2,
    0xef1fdfb3e81566d2f948e1a05d71e4dd488e857e335c3c7d9d721cad685e353fa9d72c82ed03d675d8b71333935203be3453eaa193e837f1220cbebc84e3d12e,
    0x4bea6bacad4747999a3f410c6ca923637f151c1f1686104a359e35d7800fffbdbfcd1747253af5a3dfff00b723271a167a56a27ea9ea63f5601758fd7c6cfe57,
    0xae4faeae1d3ad3d96fa4c33b7a3039c02d66c4f95142a46c187f9ab49af08ec6cffaa6b71c9ab7b40af21f66c2bec6b6bf71c57236904f35fa68407a46647d6e,
    0xf4c70e16eeaac5ec51ac86febf240954399ec6c7e6bf87c9d3473e33197a93c90992abc52d822c3706476983284a05043517454ca23c4af38886564d3a14d493,
    0x9b1f5b424d93c9a703e7aa020c6e41414eb7f8719c36de1e89b4443b4ddbc49af4892bcb929b069069d18d2bd1a5c42f36acc2355951a8d9a47f0dd4bf02e71e,
    0x378f5a541631229b944c9ad8ec165fde3a7d3a1b258942243cd955b7e00d0984800a440bdbb2ceb17b2b8a9aa6079c540e38dc92cb1f2a607261445183235adb,
    0xabbedea680056f52382ae548b2e4f3f38941e71cff8a78db1fffe18a1b3361039fe76702af69334b7a1e6c303b7652f43698fad1153bb6c374b4c7fb98459ced,
    0x7bcd9ed0efc889fb3002c6cd635afe94d8fa6bbbebab076120018021148466798a1d71efea48b9caefbacd1d7d476e98dea2594ac06fd85d6bcaa4cd81f32d1b,
    0x378ee767f11631bad21380b00449b17acda43c32bcdf1d77f82012d430219f9b5d80ef9d1891cc86e71da4aa88e12852faf417d5d9b21b9948bc924af11bd720,
]

MASK = (1 << 512) - 1


def s_layer(a):
    """S: replace every byte through the S-box."""
    return sum(PI[(a >> (8 * i)) & 0xFF] << (8 * i) for i in range(64))


def p_layer(a):
    """P: byte i of the result is byte tau(i) of the input."""
    return sum(((a >> (8 * TAU[i])) & 0xFF) << (8 * i) for i in range(64))


def l_word(b):
    """The linear map on one 64-bit word: xor the rows of A selected by the bits of b."""
    out = 0
    for i in range(64):
        if (b >> i) & 1:
            out ^= A[63 - i]
    return out


def l_layer(a):
    """L: apply the linear map to each of the eight 64-bit words."""
    return sum(l_word((a >> (64 * i)) & 0xFFFFFFFFFFFFFFFF) << (64 * i) for i in range(8))


def lps(a):
    return l_layer(p_layer(s_layer(a)))


def cipher(k, m):
    """E(K, m): 12 rounds of xor with the round key, S, P and L, then a last xor. Returns every intermediate value."""
    keys = [k]
    for i in range(12):
        keys.append(lps(keys[i] ^ C[i]))
    state = m
    rounds = []
    for i in range(12):
        x = state ^ keys[i]
        s = s_layer(x)
        p = p_layer(s)
        state = l_layer(p)
        rounds.append((x, s, p, state))
    return rounds, keys, state ^ keys[12]


def g(n, h, m):
    """The compression function g_N(h, m) = E(LPS(h xor N), m) xor h xor m."""
    _, _, out = cipher(lps(h ^ n), m)
    return out ^ h ^ m


def streebog(message, bits=512):
    """Hash a byte string. The first bytes of the message are the least significant bytes of the first block."""
    h = 0 if bits == 512 else int.from_bytes(b"\x01" * 64, "big")
    n = 0
    checksum = 0
    data = message
    while len(data) >= 64:
        m = int.from_bytes(data[:64], "little")
        h = g(n, h, m)
        n = (n + 512) & MASK
        checksum = (checksum + m) & MASK
        data = data[64:]
    m = int.from_bytes(data, "little") | (1 << (8 * len(data)))
    h = g(n, h, m)
    n = (n + 8 * len(data)) & MASK
    checksum = (checksum + m) & MASK
    h = g(0, h, n)
    h = g(0, h, checksum)
    # the RFC prints the result with its most significant byte first. Programs return the bytes in the
    # opposite order, which is the little-endian form used here.
    return (h >> (512 - bits)).to_bytes(bits // 8, "little")


if __name__ == "__main__":
    text = b"012345678901234567890123456789012345678901234567890123456789012"
    print("Streebog-512(M1) = " + streebog(text).hex())
    print("Streebog-256(M1) = " + streebog(text, 256).hex())
    print("Streebog-256('') = " + streebog(b"", 256).hex())

Running it produces this output:

Streebog-512(M1) = 1b54d01a4af5b9d5cc3d86d68d285462b19abc2475222f35c085122be4ba1ffa00ad30f8767b3a82384c6574f024c311e2a481332b08ef7f41797891c1646f48
Streebog-256(M1) = 9d151eefd8590b89daa6ba6cb74af9275dd051026bb149a452fd84e5e57b5500
Streebog-256('') = 3f539a213e97c802cc229d474c6aa32a825a360b2a933a949fd925208d9ce1bb

I checked this code against several independent sources before writing it up. The S-box and the linear map reproduce all 2,048 entries of the lookup tables in the Linux kernel, which combine both layers, and the 12 constants equal the kernel’s. The code reproduces the result of all 14 calls of the compression function in the four examples of RFC 6986, and for four of those calls, all 13 keys, all 12 round states, and the output of the cipher. It also matches the digests in the kernel’s test vectors and 262 test vectors from Botan, which its authors checked against two other implementations. The code is not fast, because it does the linear map bit by bit.

Security Status

No practical attack on the full Streebog is known. The best published result, from Jian Guo and colleagues in 2014, is a second-preimage attack on the full Streebog-512 with a cost of about 2^266 compression calls, but it needs messages longer than 2^259 blocks. So it is only of theoretical interest. The authors explain why it works. Streebog follows the HAIFA framework, which uses a counter to resist generic second-preimage attacks on long messages. In Streebog the counter enters the compression function in a weak way, and the attack uses this. The authors note that a design framework is only as secure as its instantiation. Collisions have been found only on reduced versions. For example, a 2013 attack finds a collision for the compression function reduced to 9.5 of the 12 rounds.

The constants and the S-box have drawn some criticism. Raphael AlTawy and Amr Youssef described an attack on a version with different constants, which raised questions about where the constants came from. The designers said that they came from the hash of the 12 messages. Alex Biryukov, Leo Perrin, and Aleksei Udovenko later reverse-engineered the S-box, which had been described as random, and found a hidden structure. They concluded that its parts are cryptographically weak. This is a concern for the design, but no attack on the hash has followed from it.

A 512-bit digest gives 256 bits of collision resistance, and the 256-bit form gives 128 bits. Outside systems that require GOST, SHA-2, SHA-3, and BLAKE2 are the usual choices.

FAQ

Why do different tools print different digests for the same message?

Because of byte order. The standard prints a digest with its highest byte first, and most programs write the bytes in the opposite order. Both spellings are the same value. Check the first and last bytes against the RFC example if you are not sure.

What are the length and the checksum for?

After all blocks are hashed, Streebog hashes the length of the message and the sum of all blocks through the same compression function. This means the chaining value after the last block is not the digest, and the checksum depends on every block. Together, these steps make the usual length-extension attack harder.

How is Streebog-256 different from Streebog-512?

It starts from a different h, with every byte equal to 0x01, and it keeps only the leftmost 256 bits of the result. Everything else is the same. The two digests of one message are unrelated, so the short form is not a prefix of the long one.

Is Streebog related to Kuznyechik?

Both are Russian standards, and both use the same S-box. Kuznyechik is the 128-bit block cipher of GOST R 34.12-2015. The research on the S-box covered both.

Is Streebog secure?

No practical attack on the full function is known. Its S-box has a hidden structure that its designers did not describe at first, but nothing has been built on that. For systems that do not require GOST, a modern standard is the more common choice.

References

1. Dolmatov, V. and Degtyarev, A. “GOST R 34.11-2012: Hash Function.” RFC 6986, 2013. Available at: https://www.rfc-editor.org/rfc/rfc6986

2. ISO/IEC 10118-3:2018. “Information security, Hash-functions, Part 3: Dedicated hash-functions.”

3. Guo, J., Jean, J., Leurent, G., Peyrin, T., and Wang, L. “The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Function.” Selected Areas in Cryptography (SAC) 2014, Lecture Notes in Computer Science 8781, Springer. Available at: https://eprint.iacr.org/2014/675

4. Biryukov, A., Perrin, L., and Udovenko, A. “Reverse-Engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1.” EUROCRYPT 2016, Lecture Notes in Computer Science 9665, Springer.

5. AlTawy, R. and Youssef, A. M. “Watch Your Constants: Malicious Streebog.” IACR Cryptology ePrint Archive, 2015/030.

6. Wikipedia. “Streebog.” Available at: https://en.wikipedia.org/wiki/Streebog