# Would a non-envelop, prefix only, SHA2 built MAC be susceptible to key recovery attacks?

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.

• 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. – Luis Casillas Nov 12 '19 at 21:03

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)$$.