“Sandwich”-like keyed algorithm based on the “Streebog” hash function

We propose a keyed cryptographic algorithm based on the “Streebog” hash function. We do not make any structural changes to the hash function itself, but only introduce a special type of padding. As a result, the key appears on both sides of the message in so-called “sandwich” manner — hence the name Streebog-S for our construction. “Sandwich” properties make it possible to simplify defenses against side-channel attacks while maintaining their effectiveness. We prove that Streebog-S and other algorithms based on “Streebog”, HMAC-Streebog and Streebog-K, remain secure as pseudorandom functions (PRF) and message authentication codes (MAC) even when almost all internal states are leaked to the adversary. This leakage resistance requires additional properties from the underlying compression function, namely collision- and preimage-resistance.