Message integrity means that the origins of the message (sender) and the content of the message were not modified. In other words, we are ensuring that the message has not found its ways in the hands of a hacker. In cryptography, message authentication codes (also known as MACs) are used for message integrity to verify the message being transmitted.

Let’s take a simple example. If we are sending a message to our friend, John, there needs to be a means in which he can verify that the message received was in fact, from us, and the validity of the data content. The message authentication code can be denoted with the symbol, I, and is defined as,

Where S is the signing algorithm and V is the verification algorithm

To check the validity of the message a signing algorithm, S,  generates a tag, t. This algorithm is probabilistic. This can be represented as,

As can be seen above, the signing algorithm, S, accepts two inputs; a key and a message and outputs a tag, t. Anyone familiar with cryptography will know that the key is used to encrypt the message. Without this key, it is impossible to verify message integrity. This key must remain secret to any adversary (or potential hackers). It is important to note that the secrecy of the message is not being verified here. We are only concerned with whether or not the message has been tampered with.

The verification algorithm  is a deterministic algorithm and can be defined as follows,

Where k is the encryption key, m is the message and t is the tag generated from the signing algorithm. The output of the algorithm is r and is the outcome. That is, whether the verification was accepted or rejected.

Apart from having a signing algorithm and verification algorithm, the MAC has a correctness property which states that,

This means that for every key and every message in the space, if we verify the signature algorithm with the same key and message as the other inputs of the verification algorithm, we should get ‘accept’ in return.

A MAC is considered to be secure if an attacker cannot generate a new message/tag pair defined as,

Another requirement of secure MACs is that the signing algorithm cannot be predicted by the adversary. This is known as being existentially unforgeable by the adversary. The adversary should not be able to generate new tags for signed messages. (Boneh & Shoup, 2017)

There are various different variants of MACs, which we will not go into detail here. Some examples of different MACs include,

• CBC MAC (Cipher Block Chaining MAC)
• ECBC MAC (Encrypted CBC MAC)
• NMAC (Nested MAC)
• CMAC
• PMAC (Parallel MAC)
• One-time MAC
• Carter-Wegman MAC
• HMAC

(Kowalczyk)

 

Each of these offer their own set of advantages and disadvantages and we will be revisiting each of these at a later date. This article is a brief overview in order to give a basic understanding of message authentication codes in cryptography.

 

References

Boneh, D., & Shoup, V. (2017). A Graduate Course in Applied Cryptography.

Kowalczyk, C. (n.d.). Message authentication code (MAC). Retrieved from Crypto-IT: view-source:http://www.crypto-it.net/eng/theory/mac.html

 

Featured image source: https://dirkstrauss.com/wp-content/uploads/2018/03/cryptography_magnifyingglass_code_l.jpeg