I was reading HMAC on wikipedia and I was confused about a few points.
- Where do I use HMAC?
- Why is the key part of the hash?
- Even if someone successfully used a "length-extension attack", how would that be useful to the attacker?
A message authentication code (MAC) is produced from a message and a secret key by a MAC algorithm. An important property of a MAC is that it is impossible¹ to produce the MAC of a message and a secret key without knowing the secret key. A MAC of the same message produced by a different key looks unrelated. Even knowing the MAC of other messages does not help in computing the MAC of a new message.
An HMAC is a MAC which is based on a hash function. The basic idea is to concatenate the key and the message, and hash them together. Since it is impossible, given a cryptographic hash, to find out what it is the hash of, knowing the hash (or even a collection of such hashes) does not make it possible to find the key. The basic idea doesn't quite work out, in part because of length extension attacks, so the actual HMAC construction is a little more complicated. For more information, browse the hmac tag on Cryptography Stack Exchange, especially Why is H(k||x) not a secure MAC construction?, Is H(k||length||x) a secure MAC construction? and HMAC vs MAC functions. There are other ways to define a MAC, for example MAC algorithms based on block ciphers such as CMAC.
A MAC authenticates a message. If Alice sees a message and a MAC and knows the associated secret key, she can verify that the MAC was produced by a principal that knows the key by doing the MAC computation herself. Therefore, if a message comes with a correct MAC attached, it means this message was seen by a holder of the secret key at some point. A MAC is a signature based on a secret key, providing similar assurances to a signature scheme based on public-key cryptography such as RSA-based schemes where the signature must have been produced by a principal in possession of the private key.
For example, suppose Alice keeps her secret key to herself and only ever uses it to compute MACs of messages that she stores on a cloud server or other unreliable storage media. If she later reads back a message and sees a correct MAC attached to it, she knows that this is one of the messages that she stored in the past.
An HMAC by itself does not provide message integrity. It can be one of the components in a protocol that provides integrity. For example, suppose that Alice stores successive versions of multiple files on an unreliable media, together with their MACs. (Again we assume that only Alice knows the secret key.) If she reads back a file with a correct MAC, she knows that what she read back is some previous version of some file she stored. An attacker in control of the storage media could still return older versions of the file, or a different file. One possible way to provide storage integrity in this scenario would be to include the file name and a version number as part of the data whose MAC is computed; Alice would need to remember the latest version number of each file so as to verify that she is not given stale data. Another way to ensure integrity would be for Alice to remember the MAC of each file (but then a hash would do just as well in this particular scenario).
¹ “Impossible” as in requiring far more computing power than realistically possible.
HMAC is a computed "signature" often sent along with some data. The HMAC is used to verify (authenticate) that the data has not been altered or replaced. Here is a metaphor:
You are going to mail a package to Sarah which contains a photograph. You expect her to open the package and view the photograph. At some point in the near future you expect her to send you back the package with that photograph in it. It's vital that she put the same photograph back in the package. You need to be absolutely sure she doesn't send you back an altered photograph even a little bit, or replace it with a different one. You've got hundreds of these packages going out daily with different photos; you'd never remember the photo in such detail that you could tell if she changed a small bit of it (like if she airbrushed a small zit off her face).
Here's what you can do: Before you send her the package, place another copy of the photograph inside a small locked box. Keep the key. Place the small locked box inside the package along with the original photograph you are mailing her. Assume she knows she is not to remove the locked box from the package. When you receive the package back from her, open it, place the photo on the table. Open the locked box, remove the copy, compare the two. If they are the same, then she has not altered the photograph (it is "authentic"). If the locked box is not in the package or your key will not open it, then assume she has done something nefarious and throw the whole package in the trash. The beauty here is that you don't need to "remember" anything about what you originally sent her; everything you need to ensure legitimacy of the photo comes back inside the package.
In the example above, the small locked box represents an HMAC. Your key is the HMAC's key. The photograph is the data you are applying the HMAC to.
The above is a round trip metaphor where only you have a key. In a different situation, let's say you often send packages to Tommy. You're worried that the nosey mail carriers might be opening your packages and replacing the photographs or changing them. You do the same thing with the locked box, except in this case, you let Tommy have a copy of the key, so that when he receives a package, he can open the locked box included and compare the photos himself. If upon receipt he finds the photos differ, his key doesn't open the box, or the box missing, he knows something is fishy.
The above metaphors describe why HMACs are needed but not so much how they work. Let's change the metaphor again to get closer to how they work:
Let's keep the mental imagery of the package with the photograph: you want to mail it, then receive it back again like before, ensuring the photo was not altered or replaced by the receiver, or during the round trip.
Before you close the package and mail it, you make a copy of the photograph. No locked box this time, instead you brush over the copy with a concoction of liquid chemicals. Only you know the recipe (key) for this mixture, and anytime you brush over a copy, you use the exact same brush strokes. The mixture will swirl and blur the copy of the photograph into something resembling modern art; let's call it an HMAC. You're not exactly sure what it will look like after it dries, but you know that if you brush any two identical photos with the same recipe and the same brush strokes, the resulting HMACs will look the same. So you place the dried HMAC into the package along with the original photograph and send it off to Sarah.
When you get the package back from Sarah, it contains what you hope is the un-altered original photograph along with what you expect is the HMAC you created and included with it. Take the photograph out of the package, copy it, and create another HMAC with that copy (apply your mixture/brush strokes). Compare the HMAC you just created with the HMAC that came back in the package. If they are identical, then you can be sure Sarah and the mail carriers did not alter the photograph.
If Sarah had altered the photo, then the HMACs will not be identical. If Sarah had altered the HMAC, then the HMACs will not be identical. If Sarah had altered the photo, and tried to create a new HMAC, then the HMACs will not be identical (she doesn't know your recipe).
Thus you know if the photo (data) is authentic or not, which is exactly what HMACs are used for.
1 . You use HMAC whenever you want integrity of the data maintained (and authenticity)
2 . The key is part of the HMAC, since it is a shared secret known between 2 parties only and only they can create the HMAC and no one else. (Ensures authenticity)
3 . Length extension attacks are not possible on HMAC. MAC's on the other hand simply appends key to the message, which is susceptible to it. HMAC was introduced to overcome this attack on MAC's.
Answer edited to answer comment below :- "I still don't understand why the key is in the message? Do I not know the public key of the party? If I know the public key then why is the key in the message rather me using the already known key? If I don't know the key then why would i trust that party?"
Let me try to give the shortest possible answer "HMAC provides digital signatures by using preshared secret (a.k.a secret key or symmetric key)". Essentially, if you do not have PKI in place or don't want to deal with complexities of public/private keys, root of trust and certificate chains, you can still have reliable digital signature using preshared secrets. The downside is the same as with symmetric key cryptography in general - you now need to worry about key distribution and protection of your secret keys.