Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

If H(m) is a secure hash function, can't we implement a MAC using H(k||m)?

However, it seems the more widely used MACs, such as NMAC and HMAC (both originally defined in Keying hash functions for message authentication) use a much more complicated scheme. Why is this concatenation scheme insecure?

share|improve this question
add comment

2 Answers

up vote 16 down vote accepted

The word "secure hash function" usually means (for a function $H$)

  • Preimage resistance: Given a value $h$, it is hard to find a message $x$ so that $h = H(x)$.
  • Second preimage resistance: Given a message $x$, it is hard to find a message $x' \neq x$ such that $H(x) = H(x')$.
  • Collision resistance: It is hard to find two messages $x$, $x'$ such that $H(x) = H(x')$.

For a secure MAC function $M$, we want:

  • Unforgability: Without knowing the key $k$, it is hard to find a message $x$ and authentication tag $m$ such that $m = M(k, x)$, even if given some other such valid message-tag pairs (which are not allowed as answers).

Unfortunately, defining $M(k,x) = H(k || x)$ for a secure hash function does not guarantee that the MAC function is unforgeable.

In fact, with the hash constructions used in practice (i.e. the Merkle-Damgard construction without a finalizing round, used in MD5, SHA-1 and the SHA-2 family), it is quite easy, given a valid pair $(x,m)$, to create an $(x', m')$ which is still valid:

To create a hash with Merkle-Damgard, the message is padded to some block size, and then each block in sequence is feeded to a compression function, which updates an internal state. The final state is then output as the hash.

So, $H(k||x)$ is the state of the hash machine after inputting $k||x||pad_x$. If we set our hash machine to this state, and then input arbitrary other data $y$, followed by another pad $pad_y$, we reach the state $m' = H(k||x||pad_x||y) = M(k, x||pad_x||y)$.
Forgery is done, with $x' = x || pad_x || y$.

This also works with the full-width variants of SHA-2, i.e. SHA-256 and SHA-512. For the truncated variants of SHA-2 (SHA-384, SHA-224, SHA-512/224 and SHA-512/256) this attack doesn't work, as the output is not the full hash state. (Though for a length extension attack only the truncated bits would have to be guessed, so the security is a bit less than expected from the output size.)

The HMAC construction is not suspectible to this attack, as the secret key $k$ is applied both before and after the main message, which makes the internal state non-reconstructible.

HMAC does not guarantee unforgability for general secure hash functions, either, but it has a security proof for the Merkle-Damgard construction, if the internal compression function is collision-resistant.

SHA-3 (Keccak) is based on a different model: we have a quite big state into which both key and message are mixed, and which is then further mixed to output the hash. The state itself is never output fully. Because of this, length extension needs state recovery, and the capacity (the hidden part of the state) should be big enough that this is not feasible (as well as guessing the key).

The paper On the security of the keyed sponge construction by the Keccak team analyzes the security of this construction.

share|improve this answer
    
Thanks to the anonymous editor who corrected my $H(x) \neq H(x')$ to $H(x) = H(x')$. –  Paŭlo Ebermann May 14 '13 at 19:58
    
I guess SHA-2 constructions - also Merkle–Damgård - are equally susceptible to this attack - maybe this could be added to the answer. I personally don't know how SHA-3 behaves in this regard, I'll look it up and see if I can put the knowledge on this site... –  owlstead Sep 18 '13 at 16:20
    
@owlstead I added the information about SHA-2 and SHA-3 to the answer. –  Paŭlo Ebermann Mar 4 at 20:56
    
Thanks I knew by now how Keccak behaves of course, but I forgot to add the information myself. –  owlstead Mar 18 at 15:16
add comment

The reason $H(k|m)$ (where $|$ is concatenation) is not the standard comes from the message extension attack. If I, as an attacker, have $H(k|m)$ and $m$, I can compute $H(k|m|p|m')$ (where $p$ is the padding that $H$ would have applied to $k|m$ in computing the digest, and $m'$ is an arbitrary message) without knowing $k$. I would then send $H(k|m|p|m')$ and $m|p|m'$ to the user. The message authentication check would succeed. Clearly this is an issue.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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