Message Authentication Codes

Feb 2, 2019

6 minute read

Security

If I send you a message, how can you be sure that the message is from me and the that message’s contents haven’t been altered? Phrased another way, how can you be sure that the message is authentic?

A message that is authentic guarantees:

Data Integrity: The message is unaltered. Someone didn’t tamper with the message as it was on its way to you.
Sender Authenticity: The message is from someone you trust.

A Message Authentication Code (or MAC) is one way to provide message authenticity. Whenever we exchange messages, we’ll include a MAC, which we can use to verify the integrity of the message and the sender authenticity.

Data Integrity
Sender Authenticity
Non-Repudiation: Shared Secrets vs Signatures
Use Cases
API Request Signing

Data Integrity

The MAC we send should validate the data integrity of the message. In other words, is the message you received the same as the message I sent?

We can use a common cryptographic hash function to verify our message’s integrity. There are tons of hashing functions to choose from: MD5, SHA1, SHA256, SHA512 to name a few. Let’s agree to use SHA1.

Imagine I want to send you the message:

Let's meet for coffee at 2pm.

Everytime I send you a message, the last line I’m going to send will identify the Message Authentication Code (MAC) by the hashing function I used (SHA1), and the digest (the hash of the message):

Let's meet for coffee at 2pm.
MAC-[HASH FN]: [DIGEST]

When I run the message Let's meet for coffee at 2pm. through SHA1, I get the digest 9eebb8b2c3c0057ce7ebe34a167ebebe8660072f. So the entire message including the MAC will look like:

Let's meet for coffee at 2pm.
MAC-SHA1: 9eebb8b2c3c0057ce7ebe34a167ebebe8660072f

Now let’s say you receive the message. You notice the last line identifies a MAC using SHA1. This tells you that if you run the message through a SHA1 hash on your end that you should also get the same digest 9eebb8b2c3c0057ce7ebe34a167ebebe8660072f.

If you can verify that the MAC-SHA1 digest I sent you matches the SHA1 Digest that you created from the message, then we’ve solved first challenge of data integrity. You know that the contents of the message you received are exactly the same as the message that I sent you.

But there’s still a problem, we haven’t solved for verifying the sender’s authenticity. An attacker could intercept our message, recognize that we’re using SHA1 as our hashing function and craft a replacement message with an updated digest:

Let's meet for coffee at 5pm.
MAC-SHA1: f976d3c26f727e549670928278253d6219ef5ee2

When you receive this message, you test it via MAC-SHA1 and the hash checks out, even though it’s been altered by an attacker enroute to you.

Sender Authenticity

We need a MAC that will also ensure sender authenticity: that the messages we receive are from trusted sources.

To ensure sender authenticity, let’s agree on a shared secret key: cappuccino. Let’s also agree that before we hash the message, we prefix our shared secret key to the beginning of the message.

cappuccinoLet's meet for coffee at 2pm.
MAC-SHA1: 2c20d03e235a44711ac9af4b6139bccd511e49d3

When you receive the message, you reconstruct the shared secret + message, run it through SHA1 and verify the authenticity of the message.

What about the attacker? He intercepts our message again, updates his message and MAC, but this time he doesn’t know about our secret key.

Let's meet for coffee at 5pm.
MAC-SHA1: 822192480c2654a79f2846646261533ef9fea4f7

cappuccinoLet's meet for coffee at 5pm.
MAC-SHA1: e2046eb664f55b44ba50b4f46f2290b3e0c87a15

Notice the hashes don’t match! This proves that some part of the authenticity of this message has been tampered with and the message shouldn’t be trusted.

Non-Repudiation: Shared Secrets vs Signatures

Let’s extend the ownership of our shared secret to include everyone in our organziation and that everyone in our organization uses the same shared secret to generate MACs for message exchange.

Since everyone in the organization uses the same shared secret, you now can only verify that the message came from someone within the organziation, and not a particular individual.

When shared keys are overly shared, message authors are able to repudiate (or deny) that they wrote any given message. In other words, the MAC scheme we’ve chosen no longer provides non-repudiation (the ability for an author to deny ownership of a message).

If you need guarantees for non-repudiation (you need to be able to prove who wrote a given message), you should look into digital signatures using public-key cryptography.

Use Cases

The example above is simple and contrived. Passing simple messages back and forth between individuals is better served using public-key encryption rather than a MAC.

In the real world, MACs are usually used between software applications to sign data being passed back and forth between them.

API Request Signing

Flickr API

Back in the 2000s, many public APIs used the same approach as we did above to authenticate API calls from client applications. The most well known at the time was the Flickr API.

If you wanted to use Flickr’s data within your app, you would first need to register your App. Flickr would then generate an API key and a shared secret for you to use. Everytime you called the Flickr API, you would include your API key and sign your request using the shared secret. Request signing went like this:

Sort your argument list into alphabetical order based on the parameter name. e.g. foo=1, bar=2, baz=3 sorts to bar=2, baz=3, foo=1
Concatenate the shared secret and argument name-value pairs. e.g. SECRETbar2baz3foo1
calculate the md5() hash of this string. a626bf097044e8b6f7b9214f049f3cc7
append md5 digest to the argument list with the name api_sig, e.g. api_sig=a626bf097044e8b6f7b9214f049f3cc7

Notice how the shared secret was prefixed onto the sorted parameters. This is exactly the same as how we verified our MAC-SHA1 signatures above.

While simple, the method we’ve used (and Flickr used to use) is vulnerable to length extension attacks and shouldn’t be used. More details on the Flickr vulnerability can be found in the whitepaper: Flickr’s API Signature Forgery Vulnerability - Thai Duong and Juliano Rizzo.

Length Extension Attacks work against the Merkle–Damgårdhashing family of hash functions. This includes MD5, SHA1, SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256 and others.

There are more secure ways to create MACs using a schema similar to the one we’ve created.

Brian Wigginton

Data Integrity

Sender Authenticity

Non-Repudiation: Shared Secrets vs Signatures

Use Cases

API Request Signing

Flickr API

AWS S3 Request Signatures using HMAC

Resources

Core Concepts

RFCs

Attacks

Birthday Attacks

Length Extensions Attacks