International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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
Lei Hu
Xiaoyun Wang
Download:
DOI: 10.46586/tosc.v2022.i2.63-91
URL: https://tosc.iacr.org/index.php/ToSC/article/view/9714
Search ePrint
Search Google
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.
BibTeX
@article{tosc-2022-32080,
  title={Improved MITM Cryptanalysis on Streebog},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2022, Issue 2},
  pages={63-91},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/9714},
  doi={10.46586/tosc.v2022.i2.63-91},
  author={Jialiang Hua and Xiaoyang Dong and Siwei Sun and Zhiyu Zhang and Lei Hu and Xiaoyun Wang},
  year=2022
}