Paper 2015/096

A Meet in the Middle Attack on Reduced Round Kuznyechik

Riham AlTawy and Amr M. Youssef

Abstract

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 a meet-in-the-middle attack on the 5-round reduced cipher. Our attack is 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 properties. 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 5-round reduced cipher, the 256-bit master key is recovered with a time complexity of 2^{140.3}, a memory complexity of 2^{153.3}, and a data complexity of 2^{113}.

Note: Removed the demonstration of the attack on 4 rounds.