GOST processes a variable-length message into a fixed-length output of 256 bits. The input message is broken up into chunks of 256-bit blocks (eight 32-bit
little endian integers); the message is
padded by appending as many zeros to it as are required to bring the length of the message up to 256 bits. The remaining bits are filled up with a 256-bit integer arithmetic sum of all previously hashed blocks and then a 256-bit integer representing the length of the original message, in bits.
Basic notation The algorithm descriptions uses the following notation: • \mathcal{f}0\mathcal{g}^j — j-bit block filled with zeroes. • \mathcal{j}M\mathcal{j} — length of the M block in bits modulo 2256. • \mathcal{k} — concatenation of two blocks. • + — arithmetic sum of two blocks modulo 2256. • \oplus — logical xor of two blocks. Further we consider that the little-order bit is located at the left of a block, and the high-order bit at the right.
Description The input message M is split into 256-bit blocks m_{n},\, m_{n-1},\, m_{n-2},\, \ldots,\, m_{1}. In the case the last block m_{n} contains less than 256 bits, it is prepended left by zero bits to achieve the desired length. Each block is processed by the step hash function H_\text{out} = f(H_\text{in},\, m), where H_\text{out}, H_\text{in}, m are a 256-bit blocks. Each message block, starting the first one, is processed by the step hash function f, to calculate intermediate hash value : \!H_{i+1} = f(H_{i},\, m_{i}) The H_1 value can be arbitrary chosen, and usually is 0^{256}. After H_{n+1} is calculated, the final hash value is obtained in the following way • H_{n+2} = f(H_{n+1},\, L), where L — is the length of the message M in bits modulo 2^{256} • h = f(H_{n+2},\, K), where K — is 256-bit control sum of M: m_1 + m_2 + m_3 + \ldots + m_n The h is the desired value of the hash function of the message M. So, the algorithm works as follows. • Initialization: • h := \text{initial} — Initial 256-bit value of the hash function, determined by user. • \Sigma := 0 — Control sum • L := 0 — Message length • Compression function of internal iterations: for i = 1 … n — 1 do the following (while |M|>256): • h := f(h,\, m_i) – apply step hash function • L := L + 256 – recalculate message length • \Sigma := \Sigma + m_i – calculate control sum • Compression function of final iteration: • L := L + \mathcal{j}\, m_n\, \mathcal{j} – calculate the full message length in bits • m_n := {0}^{256 - \mathcal{j} m_n \mathcal{j}} \mathcal{k} m_n – pad the last message with zeroes • \Sigma := \Sigma + m_n – update control sum • h := f(h,\, m_n) – process the last message block • h := f(h,\, L) – MD – strengthen up by hashing message length • h := f(h,\, \Sigma) – hash control sum • The output value is h.
Step hash function The step hash function f maps two 256-bit blocks into one: H_\text{out} = f(H_\text{in},\, m). It consist of three parts: • Generating of keys K_1,\, K_2,\, K_3,\, K_4 • Enciphering transformation H_\text{in} using keys K_1,\, K_2,\, K_3,\, K_4 • Shuffle transformation
Key generation The keys generating algorithm uses: • Two transformations of 256-bit blocks: • Transformation A(Y) = A(y_4\ \mathcal{k}\ y_3\ \mathcal{k}\ y_2\ \mathcal{k}\ y_1) = (y_1 \oplus y_2)\ \mathcal{k}\ y_4\ \mathcal{k}\ y_3\ \mathcal{k}\ y_2, where y_1,\, y_2,\, y_3,\, y_4 are 64-bit sub-blocks of
Y. • Transformation P(Y) = P(y_{32} \mathcal{k} y_{31} \mathcal{k} \dots \mathcal{k} y_1) = y_{\varphi(32)} \mathcal{k} y_{\varphi(31)} \mathcal{k} \dots \mathcal{k} y_{\varphi(1)}, where \varphi(i + 1 + 4(k - 1)) = 8i + k,\quad i = 0,\, \dots,\, 3,\quad k = 1,\, \dots,\, 8, and y_{32},\, y_{31},\, \dots,\, y_{1} are 8-bit sub-blocks of
Y. • Three constants: •
C2 = •
C3 = •
C4 = The algorithm: • U := H_\text{in},\quad V := m,\quad W := U\ \oplus\ V,\quad K_1 = P(W) • For
j = 2, 3, 4 do the following: • : U := A(U) \oplus C_j,\quad V := A(A(V)),\quad W := U \oplus V,\quad K_j = P(W)
Enciphering transformation After the keys generation, the enciphering of H_\text{in} is done using
GOST 28147-89 in the mode of simple substitution on keys K_1,\, K_2,\, K_3,\, K_4. Let's denote the enciphering transformation as E (enciphering 64-bit data using 256-bit key). For enciphering, the H_\text{in} is split into four 64-bit blocks: H_\text{in} = h_4 \mathcal{k} h_3 \mathcal{k} h_2 \mathcal{k} h_1 , and each of these blocks is enciphered as: • s_1 = E(h_1,\, K_1) • s_2 = E(h_2,\, K_2) • s_3 = E(h_3,\, K_3) • s_4 = E(h_4,\, K_4) After this, the result blocks are concatenated into one 256-bit block: S = s_4 \mathcal{k} s_3 \mathcal{k} s_2 \mathcal{k} s_1.
Shuffle transformation On the last step, the shuffle transformation is applied to H_\text{in}, S and m using a
linear-feedback shift register. In the result, the intermediate hash value H_\text{out} is obtained. First we define the ψ function, doing
LFSR on a 256-bit block: : \psi(Y) = \psi(y_{16} \mathcal{k} y_{15} \mathcal{k} \ldots \mathcal{k} y_2 \mathcal{k} y_1) = (y_1 \oplus y_2 \oplus y_3 \oplus y_4 \oplus y_{13} \oplus y_{16}) \mathcal{k} y_{16} \mathcal{k} y_{15} \mathcal{k} \ldots \mathcal{k} y_3 \mathcal{k} y_2, where y_{16}, y_{15}, \ldots, y_{2}, y_{1} are 16-bit sub-blocks of the
Y. The shuffle transformation is H_\text{out} = \psi^{61}\mathord\left(H_\text{in} \oplus \psi\left(m \oplus \psi^{12}(S)\right)\right), where \psi^i denotes an i-th power of the \psi function.
Initial values There are two commonly used sets of initial parameters for GOST R 34.11 94. The starting vector for both the sets is : H_1 = . Although the GOST R 34.11 94 standard itself doesn't specify the algorithm initial value H_1 and
S-box of the enciphering transformation E, but uses the following "test parameters" in the samples sections.
"Test parameters" S-box RFC 5831 specifies only these parameters, but RFC 4357 names them as "test parameters" and does not recommend them for use in production applications.
CryptoPro S-box The CryptoPro
S-box comes from "production ready" parameter set developed by CryptoPro company, it is also specified as part of RFC 4357, section 11.2. ==Cryptanalysis==