[Hash Techniques] : Message Authentication Code MAC, HMAC and Password Salting

In this blog post, I will talk about the authenticity problem in the digital word, and I will start with the basics. It is easier for people to understand encryption (confidentiality), but it becomes tricky when we talk about integrity and authenticity. While Integrity is making sure the data is not modified since the last time we looked at, authenticity means that the recipient may reasonably be certain that a message was truly created by its purported author. Integrity and Authenticity serve different purposes, but they are related to a certain extend. Let us discuss a simple message exchange between Alice and Bob.

Confidentiality via Encryption

Let us suppose Alice and Bob are exchanging a secret message (m) over an open channel. “Eve” on the other hand is listening to the channel. Using an encryption and a shared secret key, both Alice and Bob can exchange their messages without Eve knowing the content, thus confidentiality is ensured.

MAC1
But there is another problem, Eve can do more than listening to the message if he can have a small control over the channel. In this way, Eve can change the message that Alice sent, so that Bob will receive a different message. The integrity of the message is compromised in this case.
Actually, if Eve has control of the channel, he can do another nasty things. He can learn the message (m), record it and then resend it to Bob, or even delete the message completely so that Bob will not receive anything.

MAC2

Hash functions alone does not equal integrity 

One solution to the integrity problem is that Alice could compute the hash of the message, and send both the message and the hash to Bob. Bob can then read the message, and then recompute the hash of the message and compare it with the hash value received from Alice. The problem here is that Eve could interrupt the message that Alice sent, create a new message and then send the new message and the hash of the new message to Bob. Bob then will do the same computation and he would think that the message was sent by Alice.

Message Authentication Code MAC

Consider that Bob just received a message. Why should Bob believe the message came from Alice? This means that the message is completely useless.  Eve as we talked before, could send a new message to Bob with a hash value to trick him.

To resolve this problem, Authentication is introduced. Like encryption, authentication uses a secret key that Alice and Bob both know. We will call this the authentication key (Ka). When Alice sends the message m, the following occurs:

  1. Alice and Bob share a secret authentication key Ka.
  2. Alice computes a message authentication code, or MAC as a function of both the message m and the authentication key Ka.
  3. Alice then sends both the message m and MAC to Bob.
  4. Bob will receive both message m and the MAC.
  5. Bob re-computes what the MAC value should be using his own copy of the authentication code Ka, and the received message m.
  6. Bob checks if the received MAC value equals his computation of MAC.

In this way, there is now way that Eve could change the message and send his own hash value, because he does not know what it takes to compute an authentic MAC, as he has no knowledge of the shared secret Ka.

MAC3

Now Eve wants to modify the message m to a different message m2. Bob will then compute the MAC value as a function of (m2, Ka), and compare it to the received MAC value. But a good MAC function will not give the same result for two different messages, so Bob will recognize that the message is not correct.
Eve can still do nasty things. For example, Eve can replay or resend the same messages to Bob or even change the order for messages. To sort this issue, a sequence numbering can be applied to each message, so that Bob can verify that order and uniqueness of incoming messages.

MAC modes

So how MAC is computed? MAC is a function of a shared secret Ka, and the input message m.  Both parties should share a secret authentication key before starting to use MAC. MAC can be computed via encryption or hashing as we will see next.

Via Encryption (CBC-MAC)

Encryption can be used to compute MAC value, like when using CBC encryption. In this block cipher encryption mode, the message is encrypted using CBC mode, and then we throw away all but the last block of cipher text.

Via Hashing (HMAC)

It is so trivial to use hash function to compute the MAC. To do this, you perform the following computation:

h(Ka XOR a || h(Ka XOR b || m))

  • XOR = Exclusive OR
  • || = Concatenation
  • h = hashing
  • a,b = padding constants

MAC6

Salting vs MAC

Hashing can be used in many different ways. You can use it with an extra data and computation to get different usages. Here are two examples:

  • Add a shared secret key to the message and you can use Hash as MAC to preserve integrity and authenticity.
  • Add some extra (not secret) data to the message before you hash it, and you make your hash function more resistant to rainbow attacks [salting technique]

So we have talked about MAC in the blog post, so I will be talking about Salting technique here.

Password salting is a way of making password hashing more secure by adding a random string of characters to passwords before their hash is calculated, which makes them harder to reverse.

Important points :

  • In MAC, the shared key is secret while the message is not.
  • In Password Salting, the password is the secret while the additional data (Salt) is not secret
  • No two different passwords should use the same Salt value.

We use salting when storing passwords. Passwords are stored using hash techniques and never using encryption. The reason is that encryption is two direction operation, while hashing is one way operation. The most famous attack against hashing is a technique called rainbow tables, where all words and phrases in the dictionary are hashed, and a look-up is made to compare the stored hash value with the rainbow table content for a match. So if someone has his password as (Password), then most probably the hash value of this password exist in the rainbow table, and thus can be racked.

 Unsalted passwords chosen by humans tend to be vulnerable to dictionary attacks since they have to be both short and meaningful enough to be memorized. Since salts do not have to be memorized by humans they can make the size of the rainbow table required for a successful attack prohibitively large without placing a burden on the users.

Final Thoughts

MAC can be said to provide authenticity and integrity to some extend. TLS is a practical example of where MAC is being used in real life.

Salting is used when storing password hash values to make it more resistant to attacks using rainbow tables. You should always use different salt for each password hash.

You should never use the same key for authentication and encryption unless you know what you are doing. For example, do not use the same key for encryption and for the MAC shared key.

In PKI world, digital signature is the equivalent of MAC. But instead of having the same shared secret between Alice and Bob, in digital signature, Alice computes the MAC using her private key, while Bob re-computes the MAC using Alice’s public key. While MAC is similar to digital signature, MAC is faster, but on the other hand, does not provide non-repudiation as digital signatures do.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s