# Is $H(k || m) \oplus k$ secure?

It is known that $$H(k || m)$$ (when using SHA1) is an insecure MAC function since it is vulnerable to hash length extension.

But what about $$H(k || m) \oplus k$$? A normal hash length extension seems to be impossible now. Even if the same key is used several times, I see no problem as long as the output of $$H$$ is random enough. Am I right?

• Welcome to Cryptography.SE Is this homework question? What is the origin of this question? Oct 10 at 7:49
• Note that for the security properties of SHA-3, just $H(k \| m)$ is considered secure - KMAC isn't much else than that (but it uses SHAKE, not SHA). Oct 10 at 11:01
• @kelalaka I was going through some CTF writeups and found the hash length extension attack. Now I'm just wondering about this construction. Oct 10 at 17:58
• It is overkill for secure hash functions like SHA3 and Blake2. Oct 10 at 18:45

Consider $$H$$ defined as: SHA-512, with it's output XORed with the first 512 bits of the input message (padded with zeroes for short message). With such $$H$$, the proposed MAC is insecure. Yet, as far as we know, this $$H$$ is no worse than SHA-512 from a standard standpoint.

Argument: observe that if $$H(m_1\mathbin\|m_2)=\operatorname{SHA-512}(m_1\mathbin\|m_2)\oplus m_1$$ and $$\operatorname{MAC}_k(m)=H(k\mathbin\|m)\oplus k$$, then for 512-bit key¹ $$k$$ it holds $$\operatorname{MAC}_k(m)=\operatorname{SHA-512}(k\mathbin\|m)$$. Therefore this $$\operatorname{MAC}$$ is susceptible to the length extension attack².

Therefore, it is impossible to prove that $$H(k\mathbin\|m)\oplus k$$ is a secure MAC without some insight into the internal structure of $$H$$.

I'm rather confident the proposed MAC construction is practically secure for hashes of the SHA-2 family, and even for SHA-1. We might want to prove security under the assumption the hash has Merkle-Damgård structure, a compression function built from a block cipher $$E$$ per the Davies-Meyer construction, with appropriate block and key size for $$E$$. I think this would be possible under the ideal cipher model, but not a standard model of security of $$E$$. The problem is that XORing the key with the output of a block cipher can weaken it. That's the case e.g. for AES-128 in decryption mode, where the XOR removes a round's worth of security.

¹ For key of arbitrary size, $$\operatorname{MAC}_k(m)=\operatorname{SHA-512}(k\mathbin\|m)\oplus F_{|k|}(m)$$ where $$F_{|k|}(m)$$ is $$0^{\min(|k|,512)}$$, followed by the first $$\min(\max(512-|k|,0),|m|)$$ bits of $$m$$, followed by $$0^{\max(512-|k|-|m|,0)}$$. This still allows attack.

² Contrary to what I wrote initialy, we can't recover $$k$$ from queries.

• I'm having a hard time proving that $H$ is a collision resistant hash function. Let $H(m_1\|m_2) = \mathrm{SHA}(m_1\|m_2)\oplus m_1$. Given a collision of $H(m_1\|m_2)$ we need to give a collision for $\mathrm{SHA}$. Let $m_a, m_b$ be two colliding inputs of $H$ with $m_a \neq m_b$ and $H(m_a) = H(m_b)\iff\mathrm{SHA}(m_{a_1}\|m_{a_2})\oplus m_{a_1} = \mathrm{SHA}(m_{b_1}\|m_{b_2})\oplus m_{b_1}$. It's easy to derive a collision if $m_{a_1} = m_{b_1}$, but what if they are distinct? Can we bound the probability that they are distinct? Oct 10 at 11:38
• @cisnjxqu: I think we could prove that $H$ defined such that $H(m_1\mathbin\|m_2)=\mathrm{SHA}(m_1\mathbin\|m_2)\oplus m_1$ is collision resistant under a model of $\mathrm{SHA}$ as a random oracle. However that's a poor model, since it does not account for the length-extension property. I think we could more laboriously prove that with a finer model of $\mathrm{SHA}$ where we use the actual Merkle-Damgård construction, and a round function modeled by a random oracle.
– fgrieu
Oct 10 at 14:25
• @cisnjxqu : Yes. Example: define $S(m)$ to be the first bit of $m$, concatenated with an ideal hash of the rest of $m$. $S$ is collision-resistant, yet $H$ defined by $H(m_1\mathbin\|m_2)=S(m_1\mathbin\|m_2)\oplus m_1$ is not, since the first bit of the input of $H$ has no influence on the outcome.
– fgrieu
Oct 10 at 15:12
• @fgrieu Thanks a lot! Can you give me some more tips on how to recover the key using hash length extension? I can't figure it out.. Oct 10 at 18:05
• @Johny Dow : I was wrong, we can't recover the key. See modified first two paragraphs of the answer.
– fgrieu
Oct 10 at 19:14