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

Question

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.

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.