Cryptology ePrint Archive: Report 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}.

Category / Keywords: secret-key cryptography / Kuznyechik, Cryptanalysis, Meet-in-the-middle attacks, Differential enumeration, Partial sequence matching, GOST

Date: received 9 Feb 2015, last revised 17 Apr 2015

Contact author: r altawy at gmail com

Available format(s): PDF | BibTeX Citation

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

Version: 20150418:020216 (All versions of this report)

Short URL: ia.cr/2015/096

Discussion forum: Show discussion | Start new discussion