International Association
for Cryptologic Research

Kuznyechik is an SPN block cipher that has been recently chosen to be standardized by the Russian federation as a new GOST cipher. The algorithm updates a 128-bit state for nine rounds using a 256-bit key. In this paper, we present meet-in-the-middle attacks on the 4 and 5 round reduced cipher. Our attacks are based on the differential enumeration approach, where we propose a distinguisher for the middle rounds and match a sequence of state differences at its output. However, the application of the exact approach is not successful on Kuznyechik due to its optimal round diffusion. Accordingly, we adopt an equivalent representation for the last round where we can efficiently filter ciphertext pairs and launch the attack in the chosen ciphertext setting. We also utilize partial sequence matching which further reduces the memory and time complexities through relaxing the error probability. The adopted partial sequence matching approach enables successful key recovery by matching parts of the generated sequence instead of the full sequence matching used in the traditional settings of this attack. For the 4 and 5 round reduced cipher, the 256-bit master key is recovered with a time complexity of $2^{139.6}$ and $2^{140.3}$, and a memory complexity of $2^{24.6}$ and $2^{153.3}$, respectively. Both attacks have similar data complexity of $2^{113}$