About «$k$-bit security» of MACs based on hash function Streebog

Various message authentication codes (MACs), including HMAC-Streebog and Streebog-K, are based on the keyless hash function Streebog. Under the assumption that the compression function of Streebog is resistant to the related key attacks, the security proofs of these algorithms (in the single key setting) were recently presented at CTCrypt 2022.
Generic related key attacks have the great impact on the security bounds. Guessing any one of the $q$ related keys can be $q$ times faster than guessing a single secret key. However, if different related keys are used to process different inputs, then the adversary should choose a specific key when guessing, not any one. This simple observation fortunately holds for MACs based on Streebog.
We carefully detail the resources of the adversary in the related key settings, revisit the proof, and obtain new security bounds. Let $n$ be the bit length of the hash function state. If the amount of processed data is less than about $2^{n-k}$ blocks, then for HMAC-Streebog-512 and Streebog-K, the only effective method of forgery (or distinguishing) is guessing the $k$-bit secret key or the tag if it is shorter than the key. So, we can speak about «$k$-bit security» without specifying the amount of material, if the key length is no longer than half of a state. The bound for HMAC-Streebog-256 is worse and equal to $2^{\frac{n}{2}-k}$ blocks.
We describe several attacks that show the tightness of the obtained security bounds. Hence, the latter cannot be significantly improved further.