Improved MITM Cryptanalysis on Streebog
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.
Automatic Classical and Quantum Rebound Attacks on AES-like Hashing by Exploiting Related-key Differentials 📺
Collision attacks on AES-like hashing (hash functions constructed by plugging AES-like ciphers or permutations into the famous PGV modes or their variants) can be reduced to the problem of finding a pair of inputs respecting a differential of the underlying AES-like primitive whose input and output differences are the same. The rebound attack due to Mendel et al. is a powerful tool for achieving this goal, whose quantum version was first considered by Hosoyamada and Sasaki at EUROCRYPT 2020. In this work, we automate the process of searching for the configurations of rebound attacks by taking related-key differentials of the underlying block cipher into account with the MILP-based approach. In the quantum setting, our model guide the search towards characteristics that minimize the resources (e.g., QRAM) and complexities of the resulting rebound attacks. We apply our method to Saturnin-hash, Skinny, and Whirlpool and improved results are obtained.