Key-recovery security of keyed hash functions based on GOST 34.11-2018 (“Streebog”)

Keyless hash function GOST 34.11-2018 (“Streebog”) is used in many keyed cryptoalgorithms, including HMAC-Streebog and Streebog-K. Using the provable security approach, we obtain the upper bounds on the probability of recovering the secret key for the two algorithms mentioned. We also propose a sandwich-like method of converting “Streebog” to the keyed cryptoalgorithm (conventionally called Streebog-S) without changing the hash function itself. Streebog-S is a secure pseudorandom function and a secure message authentication code. Unlike HMAC-Streebog and Streebog-K, the only key-recovery method for Streebog-S is straightforward guessing. This statement holds under the assumption that the similar is true for the underlying iteratively applied compression function.