Streebog compression function as PRF in secret-key settings

Security of the many keyed hash-based cryptographic constructions (such as HMAC) depends on the fact that the underlying compression function $\mathsf{g}(H,M)$ is a pseudorandom function (PRF). This paper presents key-recovery algorithms for 7 rounds (of 12) of Streebog compression function. Two cases were considered, as a secret key can be used: the previous state $H$ or the message block $M$. The proposed methods implicitly show that Streebog compression function has a large security margin as PRF in the above-mentioned secret-key settings.