The Basics of Crypto 7: Keyed Hashing Functions

Keyed hashing functions are essentially normally hashing functions with a system of validation. They are used commonly in modern communications systems as methods for confirming the integrity and authenticity of messages exchanged between multiple parties, the most common form of this being the hashed-based message authentication codes (HMAC).

Keyed hashes are used predominantly in two cryptographic systems: message authentication codes (MACs) and pseudo random functions (PRFs). MACs are used in message authentication and integrity whilst PRFs are very similar to PRNGs with some slight differences.

Message Authentication Codes (MAC)

MACs maintain the integrity and authenticity of messages by generating a token referred to as the authentication tag of the message. Similarly to how you can decrypt a cipher text if you have it's key and confirm it has not been modified you can confirm that a message has not been modified if you know a MACs token.

When using secure communications systems such as SSH or TLS they will often combine a cipher and a MAC to protect the confidentiality, integrity and authenticity of the communications. These protocols generate a MAC for each network packet transmitted ensuring each packet is not tampered with or corrupted during transit.

Also something to be aware of is that MACs provide no protection against replay attacks. If someone was to eavesdrop on communications between user A and user B and then later replay the messages from user A to user B the MAC would still show as valid. Many protocols include a message number so the receiver knows if the messages are being replayed back later however MACs do not do this.

A basic diagram detailing how a MAC works in message transmission can be seen below:

Pseudorandom Functions (PRF)

PRFs take a message and a key and output random looking data. However they will output the same data consistently with the same inputs. PRFs are commonly used to confirm a user knows something. Say for example Alice wanted to convince Bob that she knew the value of a secret key, if Bob sent Alice a random value Alice could then use the PRF with the value and the key to produce some output and return that to Bob, Bob could then confirm that Alice knew the key.

Hash-Based MAC (HMAC)

A hash based MAC is a MAC based on a hashing function. A HMAC can function as either a secure MAC or a secure PRF as long as the underlying hashing function is collision resistant. A HMAC generally consists of five parts, the message, inner padding string, outer padding string, key and the hashing function. It works by XORing the outer padding string with the key and passing it to the hashing function, then XORing the key with the inner padding string and passing it to the hashing function, then taking the output of the first operation and passing it with the message to the hashing function, then taking the output of the second and third operations and passing them to the hashing function to generate the final HMAC. Since that stream of words is relatively difficult to follow I have included a picture below (the red crosses represent points where the hashing function is utilised:

In general you will see HMACs (or MACs for that matter) specified alongside the appropriate hashing mechanism e.g. HMAC-SHA-256 this is because the hashing mechanism being used is the SHA-256 mechanism.