Improved MITM Cryptanalysis on Streebog

Authors

  • Jialiang Hua Institute for Advanced Study, BNRist, Tsinghua University, Beijing, China
  • Xiaoyang Dong Institute for Advanced Study, BNRist, Tsinghua University, Beijing, China
  • Siwei Sun School of Cryptology, University of Chinese Academy of Sciences, Beijing, China; State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878, China
  • Zhiyu Zhang State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China; School of Cryptology, University of Chinese Academy of Sciences, Beijing, China
  • Lei Hu State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China;School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China; School of Cryptology, University of Chinese Academy of Sciences, Beijing, China
  • Xiaoyun Wang Institute for Advanced Study, BNRist, Tsinghua University, Beijing, China; Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China; School of Cyber Science and Technology, Shandong University, Qingdao, China

DOI:

https://doi.org/10.46586/tosc.v2022.i2.63-91

Keywords:

Preimage, MITM Attack, Streebog, MILP

Abstract

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.

Published

2022-06-10

Issue

Section

Articles

How to Cite

Improved MITM Cryptanalysis on Streebog. (2022). IACR Transactions on Symmetric Cryptology, 2022(2), 63-91. https://doi.org/10.46586/tosc.v2022.i2.63-91