When aiming to build a MAC, classic literature discusses the use of Envelopes or key "Sandwich" to build MACs. These were proved to be as secure as HMAC in “Sandwich” Is Indeed Secure: How to Authenticate a Message with Just One Hashing by Yasuda. In these Envelopes, a key (K) is prepended to the padded message (M) and then another key is appended afterward (K). We can describe the MAC construction as $\operatorname{MAC}=H(K\mathbin\|M\mathbin\|K)$.

As Yasuda explains, the key after the message is added in order to avoid length extension attacks on the MAC. It is also important to keep the appended key in its own hash block in order to avoid attacks such as the one described in On the security of two MAC Algorithms by Preneel and Oorschot.

Now, what I haven't found in recent papers is any security analysis on the security (or lack of) of MAC algorithms such as the ones described by Yasuda in his paper as "prefix". In other words, I'm trying to find how secure MAC=H(K||M) nowadays is and which are the tradeoffs of using such algorithms beyond the danger posed by length extension attacks.

More explicitly, I'm currently trying to find out if a "prefix" MAC building algorithm that would use SHA2 as its hashing algorithm would be susceptible to key recovery attacks. Let's suppose that this algorithm makes use of SHA2-256 and generates a MAC over 2 blocks containing a key, data, and padding. The blocks would look like this:

Block1 (Secret key 32 bytes || 32 bytes of message data that can be influenced by an attacker))

Block2 (64 bytes of message data & padding).

As far as I can see attacks such as the one discovered by Preneel & Oorschot will only work for keys whose value lies between two hashing blocks, so I'm trying to find other methods of key recovery attack that would be relevant for "prefix" MAC building algorithms. I'm assuming that any number of MACs and message data can be gathered by an attacker but considering that the key can only be recovered through cryptoanalysis.

  • $\begingroup$ The reason you're not finding papers about key recovery attacks on such prefix constructions is likely the fact that any such attack would trivially imply a preimage attack on the hash function. This generic fact wouldn't make a good topic for a paper. And if you found a concrete example of such an attack on a prefix-MAC, you'd write a paper about a preimage attack on the hash instead. $\endgroup$ Nov 12, 2019 at 21:03

1 Answer 1


None of these constructions will lead to key recovery unless the underlying hash function is spectacularly broken in the sense of preimage resistance, which pretty much none of them are (archived).

But key recovery is not usually what's directly relevant to your application. If you're using one of these constructions as a MAC, for example, what's relevant to your application is forgery—and while key recovery is one path to forgery, it's not the only path to forgery. In MAC applications, length extension is fatal: it is trivial to forge MACs under $m \mapsto \operatorname{SHA256}(k \mathbin\| m)$.

These days, it's all an academic concern, because:

  • the world has settled on using HMAC to get a PRF out of SHA-256 so it's ubiquitous and ready at hand essentially everywhere,
  • there are much cheaper MACs like GHASH and Poly1305 built into authenticated ciphers like AES-GCM and crypto_secretbox_xsalsa20, and
  • SHA-3 and BLAKE2 natively provide keyed variants anyway with PRF security so you don't need to construct your own—and making the prefix construction secure was an explicit design criterion for the SHA-3 competition if you really still want to use it.
  • $\begingroup$ I will provide some additiona context. In the case of my application, length extension is not an issue, as a fixed message length is expected and checked for. If a longer message with a valid MAC is received it would be easily spotted. Regarding it only being an academic concern, I mostly concur with you. With the availability of HMAC there's little reason to use SHA2 based MACs, yet I find some of those in my vicinity. These implementations are based on the ATEC family of criptochips. Since I'm deeply concerned about the security of using SHA2 based MACs, I've raised this question. $\endgroup$
    – Alpha1983
    Nov 14, 2019 at 8:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.