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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
KuznyechikCryptanalysisMeet-in-the-middle attacksDifferential enumerationPartial sequence matchingGOST
Contact author(s)
r altawy @ gmail com
History
2015-04-18: revised
2015-02-23: received
See all versions
Short URL
https://ia.cr/2015/096
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/096,
      author = {Riham AlTawy and Amr M.  Youssef},
      title = {A Meet in the Middle Attack on Reduced Round Kuznyechik},
      howpublished = {Cryptology ePrint Archive, Paper 2015/096},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/096}},
      url = {https://eprint.iacr.org/2015/096}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.