What Is Hash-Based Message Authentication?

Hussain Safwan
Oct 9, 2020 · 5 min read

So you’re reading this, but how confident are you that this is the same text from the author stated above and hasn’t been compromised to something else on the way (like I was writing on Data Science and the adversary altered it to a text on cryptography)? Well, networks are quite precarious in nature and such an incidence shouldn’t be surprising at all. In network communications, the integrity of the message to be delivered is just as important as secrecy and other privacy requirements are.

By integrity, we mean that a message (like this article is a message from me to my audience) should arrive at the receiver’s end just as it left the sender’s, i.e. without any alterations or at the least the fact that it has been altered should be confirmable. The central concept here is to tag the message with an authenticator so that the receiver has a clue of what the original message might have been. Now, there are quite a few algorithms to produce and attach the authenticator, the one we are particularly interested in this episode is the hMAC algorithm that stands for hash-based message authentication code. To go for hMAC, we need to understand the rudimentary one, the MAC algorithm. This should serve as a nice gateway into the realm of message authentication.

Message Authentication Codes

The MAC is a string of fixed size generated by an algorithm that takes the message and a secret key as input. The string, also known as the tag or the digest, is then concatenated to the message itself, and the compound is passed through the unsafe network. On the receiver’s end, the message is extracted and input into the same algorithm provided the receiver has access to the secret key, the same digest should be reproduced which is then compared to the incoming one — if matched the message is authentic else fraudulent. Some of the characteristics of MAC are,

  1. The same message with the same key produces the same MAC

Cipher MACs

MACs are a way to secure the integrity of the message and obviously can’t provide the secrecy alone. So the use if MAC with an encryption scheme is the best way to provide privacy and authenticity of the communication at the same time. Below is a diagram to illustrate the procedure, press on the image to zoom in,

The procedure is known as cipher tied MAC as the MAC is produced from the cipher. There is another procedure called plaintext tied MAC where the encryption is done after the message-MAC concatenation.

With that said, I guess we’re ready to take the big bite and discuss about hMACs.

Hash-based MACs

This class of MAC tags is produced via algorithms that have an underlying hash function. Any well-known hash function may be used for example SHA, MD, Whirlpool, etc. The mathematical definition of hMAC is,

The algorithm takes in the secret key and the message (plain or encrypted) as input, pretty usual. The size of the key is to be adjusted to the block size of the underlying hash function, denoted by H. Like, for instance, the block size of SHA-256 is 256B. The adjustment is done by hashing the key down to the required size if exceeded. K’ here is the length-adjusted key. The opad and ipad are the outer and inner padding constants. The values are strings of hex 0x36 and 0x5c repeated to match the block size, i.e. for a block size of 4, the value of opad is 0x360x360x360x36. The algorithmic pseudocode would be like,

Since the hash function is anything like SHA or MD, it’s quite arduous to actually work an example out — sorry for that.

Attacks and Robustness

Brute force attack on the MAC algorithm can be carried out on two lines, one is to linearly search the keyspace, which for a k-length key should be 2^k. The other is to search the entire tag space to generate a valid tag for the message m, the effort for which is 2^n. So the overall effort is the minimum of the two, i.e. min(2^k, 2^n).

Similar goes for hMAC. For an algorithm employing n-bit key, it takes 2^n keyspace to be searched, which makes brute force infeasible even for a short lengthed key.

Before I end this episode, I’d like to share a brute-force scenario that I found at the crypto exchange site. Say we’re trynna break an hMAC-MD5 that employs a 128-bit key, which raises the keyspace to 2¹²⁷. Now to brute-force this algorithm we use the current fastest GPU, actually an amalgam of 25 internal GPUs, that breaks 400 billion (4 x 10¹¹) keys per second. Say due to a super boosted budget we manage 1 million of these servers which raises the computation power to a staggering 4 x 10¹⁷ keys/second. Impressive, no?

Well, not exactly, even at this rate it would take 1.35 x 10¹³ years! Fun fact: The sun turns into a red giant in about 5 x 10⁹ years!

ENJOY THE FIREWORKS!

The Startup

Get smarter at building your thing. Join The Startup’s +793K followers.

Sign up for Top 10 Stories

By The Startup

Get smarter at building your thing. Subscribe to receive The Startup's top 10 most read stories — delivered straight into your inbox, once a week. Take a look.

By signing up, you will create a Medium account if you don’t already have one. Review our Privacy Policy for more information about our privacy practices.

Check your inbox
Medium sent you an email at to complete your subscription.

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +793K followers.

Hussain Safwan

Written by

Developer, writer, artist. Total blend. Visit me at https://safwan.netlify.app/

The Startup

Get smarter at building your thing. Follow to join The Startup’s +8 million monthly readers & +793K followers.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store