Can the HMAC of a pre-hash be considered equivalent to an HMAC of the message?

Question

Assume:

• size of m = 1kB
• HMAC hashing function = SHA256
• H hashing function = SHA256

It seems reasonable to think that there would be no difference in authenticating a message if either HMAC(k, m) or HMAC(k, H(m)) are used as this other post indicates. Am I missing something or are there other potential security risks in doing this?

Pre-hashing is preferred due to the reduction in HMAC validation time on large messages as only the 32byte pre-hash would need to be run through HMAC validation (vs. the entire 1kB message).

Answer 1

TLDR: Such pre-hashing is weaker, and slower on a standard computer.

Most serious security problem: in order to break the MAC with pre-hasing, it is enough to find two different messages with the same SHA-256 hash, and that's an offline attack (it requires a single query to a MAC oracle/device knowing the key). Such breaking of SHA-256's collision resistance could become possible¹ due to some combination of cryptanalytical and technological progress, like that happened for SHA-1. Absent cryptanalytical breakthrough and discounting quantum computers useful for cryptanalysis, that costs $\approx2^{129}$ compression functions (using distributed Pollard's rho with distinguished points). Contrast with the best known attacks against HMAC, which require a much less realistic $\approx2^{128}$ online queries (performing $\approx2^{129}$ compression functions), or a whopping $>2^{256}$ offline compression functions (for 256-bit key).

For just that reason, HMAC-MD5 remains practically secure when MD5 collision is totally broken (collision with chosen prefix is easy), and HMAC-SHA-1 remains practically secure when SHA-1 collision is very broken (collision is easy, collision with chosen prefix is feasible).

Another explanation of these facts: we have argument that HMAC is secure for weaker properties of the hash's compression functions than required for argument of collision-resistance of the hash: Mihir Bellare, New Proofs for NMAC and HMAC: Security Without Collision-Resistance, originally in proceedings of Crypto 2006, republished in Journal of Cryptology, 2015.

---

Pre-hashing is preferred due to the reduction in HMAC validation time on large messages as only the 32byte pre-hash would need to be run through HMAC validation (vs. the entire 1kB message).

No, the opposite, pre-hashing is slower on a standard computer. For a 1024-byte $m$ an $k$ at most 512-bit, $\operatorname{HMAC-SHA-256}(k,M)$ first hashes 512+8192 bits (18 blocks after padding), then 512+256 bits (2 blocks). Whereas $\operatorname{HMAC-SHA-256}(k,\operatorname{SHA-256}(M))$ first hashes 8192 bytes (17 blocks), then 512+256 bytes (2 blocks), then 512+256 bytes (2 blocks). That 2 blocks more, and one more each of hash initialization and finalization. Optimizations for repeated use of the key apply equally to both variants.

The one situation when pre-hashing would result in a speedup is when HMAC itself is implemented in a relatively slow secure device (like a Smart Card or HSM) in order to keep the key protected. In that case, pre-hashing is reasonable, and using SHA-256 for that is not unreasonable. But if performance matters, SHA-512/256 or SHA-384 is probably as better choice for the pre-hash: these hashes are faster on modern CPUs, the secure device won't make more SHA-256 compression functions, and (for SHA-384 pre-hasing, which arguably is more secure than either SHA-256 or SHA-512/256) performance overhead of transmitting 128 extra bytes to the security device is low.

---

¹ I'm not saying that's likely in next two decades; rather, the contrary.

Answer 2

Both are secure, as long as you accurately expect to never see a collision in the un-keyed hash. (SHA-256)

In general, if $\operatorname{H}(M_1) = \operatorname{H}(M_2)$ is true and $M_1 \ne M_2$ then it may or may not be the case that $\operatorname{HMAC}(K, M_1) = \operatorname{HMAC}(K, M_2)$. The ouputs (asume they're $n$-bit tags) should be different, though, with only a one in $2^n$ chance of them being equal for a random $K$.

If $M_1$ and $M_2$ where replaced with $\operatorname{H}(M_1)$ and $\operatorname{H}(M_2)$, then the MAC tags would instead always be equal in such a scenario.

This change makes no practical difference to security unless you either take the colliding $M_1$ and $M_2$ for granted or there exists some practical algorithm to search for such a pair of messages on the fly. (No difference, assuming that the authentication key is unknown to the attacker, that is.)

A collision attack on SHA-256 shouldn't be something to worry about, though. So both normal HMAC-SHA-256 and $\text{HMAC}_{\text{SHA-256}}(K, \text{SHA-256}(m))$ should be okay.

Implementation errors due to added complexity might be a problem, though. As would protocol design oversights made by confusing the role of each hash-based algorithm.