Score:4

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

fr flag

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?

kelalaka avatar
in flag
Welcome to Cryptography.SE Is this homework question? What is the origin of this question?
Maarten Bodewes avatar
in flag
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).
Johny Dow avatar
fr flag
@kelalaka I was going through some CTF writeups and found the hash length extension attack. Now I'm just wondering about this construction.
kelalaka avatar
in flag
It is overkill for secure hash functions like SHA3 and Blake2.
Score:6
ng flag

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.

cisnjxqu avatar
us flag
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?
fgrieu avatar
ng flag
@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.
cisnjxqu avatar
us flag
That might be possible, yes. I suppose my question is whether there is a collision resistant hash function (here $\mathrm{SHA}$) such that $H$ is _not_ collision resistant.
fgrieu avatar
ng flag
@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.
Johny Dow avatar
fr flag
@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..
fgrieu avatar
ng flag
@Johny Dow : I was wrong, we can't recover the key. See modified first two paragraphs of the answer.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.