Paper 2022/568

Improved MITM Cryptanalysis on Streebog

Jialiang Hua, Xiaoyang Dong, Siwei Sun, Zhiyu Zhang, Lei Hu, and Xiaoyun Wang


At ASIACRYPT 2012, Sasaki et al. introduced the guess-and-determine approach to extend the meet-in-the-middle (MITM) preimage attack. At CRYPTO 2021, Dong et al. proposed a technique to derive the solution spaces of nonlinear constrained neutral words in the MITM preimage attack. In this paper, we try to combine these two techniques to further improve the MITM preimage attacks. Based on the previous MILP-based automatic tools for MITM attacks, we introduce new constraints due to the combination of guess-and-determine and nonlinearly constrained neutral words to build a new automatic model. As a proof of work, we apply it to the Russian national standard hash function Streebog, which is also an ISO standard. We find the first 8.5-round preimage attack on Streebog-512 compression function and the first 7.5-round preimage attack on Streebog-256 compression function. In addition, we give the 8.5-round preimage attack on Streebog-512 hash function. Our attacks extend the best previous attacks by one round. We also improve the time complexity of the 7.5-round preimage attack on Streebog-512 hash function and 6.5-round preimage attack on Streebog-256 hash function.

Available format(s)
Secret-key cryptography
Publication info
Published by the IACR in Fse 2023
PreimageMITM AttackStreebog and MILP
Contact author(s)
huajl18 @ tsinghua edu cn
xiaoyangdong @ tsinghua edu cn
sunsiwei @ ucas ac cn
zhangzhiyu @ iie ac cn
hulei @ iie ac cn
xiaoyunwang @ tsinghua edu cn
2022-05-10: received
Short URL
Creative Commons Attribution


      author = {Jialiang Hua and Xiaoyang Dong and Siwei Sun and Zhiyu Zhang and Lei Hu and Xiaoyun Wang},
      title = {Improved MITM Cryptanalysis on Streebog},
      howpublished = {Cryptology ePrint Archive, Paper 2022/568},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.