Paper 2023/374

Practical-Time Related-Key Attack on GOST with Secret S-boxes

Orr Dunkelman, University of Haifa
Nathan Keller, Bar-Ilan University
Ariel Weizman, Bar-Ilan University

The block cipher GOST 28147-89 was the Russian Federation encryption standard for over 20 years, and is still one of its two standard block ciphers. GOST is a 32-round Feistel construction, whose security benefits from the fact that the S-boxes used in the design are kept secret. In the last 10 years, several attacks on the full 32-round GOST were presented. However, they all assume that the S-boxes are known. When the S-boxes are secret, all published attacks either target a small number of rounds, or apply for small sets of weak keys. In this paper we present the first practical-time attack on GOST with secret S-boxes. The attack works in the related-key model and is faster than all previous attacks in this model which assume that the S-boxes are known. The complexity of the attack is less than $2^{27}$ encryptions. It was fully verified, and runs in a few seconds on a PC. The attack is based on a novel type of related-key differentials of GOST, inspired by local collisions. Our new technique may be applicable to certain GOST-based hash functions as well. To demonstrate this, we show how to find a collision on a Davies-Meyer construction based on GOST with an arbitrary initial value, in less than $2^{10}$ hash function evaluations.

Available format(s)
Attacks and cryptanalysis
Publication info
Related-key differential cryptanalysisGOSTLocal collision
Contact author(s)
orrd @ cs haifa ac il
Nathan Keller @ biu ac il
relweiz @ gmail com
2023-03-16: approved
2023-03-15: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial-ShareAlike


      author = {Orr Dunkelman and Nathan Keller and Ariel Weizman},
      title = {Practical-Time Related-Key Attack on GOST with Secret S-boxes},
      howpublished = {Cryptology ePrint Archive, Paper 2023/374},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.