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.

Given a Merkle-Damgård hash function $H$, I know that an attacker can forge a message protected by a MAC computed as $H(\textrm{secret_key}||\textrm{message})$.

Why can't he perform the same extension attack on a MAC construction $H(\textrm{message}||\textrm{secret_key})$?

share|improve this question
4  
You can perform a length extension, but then the message doesn't end with the secret key anymore and is thus not a valid authentication tag. –  CodesInChaos Jun 14 '13 at 13:17
    
Thanks CodesInChaos, this cleared it to me. –  Peter Jun 14 '13 at 13:25
    
Regardless, you should almost certainly be using an HMAC. –  Stephen Touset Jun 14 '13 at 15:37
    
add comment

1 Answer 1

up vote 6 down vote accepted

How does the length extension attack against $H(k||m)$ work?

For Merkle-Damgård hashes, if you know $H(x)$ but not $x$ you can still choose an $e$ and then compute $H(x||p||e)$. With $x=k||m$ you can compute $H((k||m||p)||e)=H(k||(m||p||e))$ which is a valid authentication tag for $m||p||e$.

Why doesn't it work against $H(m||k)$?

With a length extension an attacker chooses the extension. The only non trivial way to make $H(m||k||e)$ a valid tag is if $e$ ends with $k$. Since the attacker doesn't know the secret key they can't put the key at the end of $e$ and thus can't produce a valid tag.

What should I be using?

Either use H(k||m) with a hash that's not vulnerable to length extension attacks, such SHA3. Or use HMAC with an older hashfunction, such as SHA2. $H(m||k)$ is not ideal because it can be attacked by finding collisions of $H$. Collisions are one of the easier attacks crypto-analytically and require a hashfunction twice the width of the target security level. e.g. SHA-256 for a 128 bit security level.

share|improve this answer
    
Great in-depth answer. Thanks! –  Peter Jun 14 '13 at 18:43
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.