4
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ Welcome to Cryptography.SE Is this homework question? What is the origin of this question? $\endgroup$
    – kelalaka
    Oct 10 at 7:49
  • 1
    $\begingroup$ 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). $\endgroup$
    – Maarten Bodewes
    Oct 10 at 11:01
  • $\begingroup$ @kelalaka I was going through some CTF writeups and found the hash length extension attack. Now I'm just wondering about this construction. $\endgroup$
    – Johny Dow
    Oct 10 at 17:58
  • 1
    $\begingroup$ It is overkill for secure hash functions like SHA3 and Blake2. $\endgroup$
    – kelalaka
    Oct 10 at 18:45
6
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – cisnjxqu
    Oct 10 at 11:38
  • $\begingroup$ @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. $\endgroup$
    – fgrieu
    Oct 10 at 14:25
  • 1
    $\begingroup$ @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. $\endgroup$
    – fgrieu
    Oct 10 at 15:12
  • 1
    $\begingroup$ @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.. $\endgroup$
    – Johny Dow
    Oct 10 at 18:05
  • 1
    $\begingroup$ @Johny Dow : I was wrong, we can't recover the key. See modified first two paragraphs of the answer. $\endgroup$
    – fgrieu
    Oct 10 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.