Message Authentication Code (MAC)

A message authentication code (often called MAC) is a block of a few bytes that is used to authenticate a message. The receiver can check this block and be sure that the message hasn't been modified by the third party.

The abbreviation MAC can also be used for describing algorithms that can create an authentication code and verify its correctness.

Definition MAC defined over (K, M, T) is a pair of algorithms (S, V):
  • S(k, m): returns a message authentication code t which belongs to a set T
  • V(k, m, t): returns a value true or false depending on the correctness of the received authentication code
where:
  • M is a set of all possible messages m,
  • K is a set of all possible keys k,
  • T is a set of all possible authentication codes t

The simplest way to mark the authenticity of the message is to compute its checksum, for example using the CRC algorithm. One can attach the result to the transmitted message.

The primary disadvantage of this method is the lack of protection against intentional modifications in the message content. The intruder can change the message, then calculate a new checksum, and eventually replace the original checksum by the new value. An ordinary CRC algorithm allows only to detect randomly damaged parts of messages (but not intentional changes made by the attacker).

The following paragraphs present several MAC algorithms that provide security against intentional changes of authentication codes.

MAC algorithms based on PRF

It is possible to create secure MAC algorithms using a secure pseudorandom function (PRF).

Definition Having a pseudorandom function F: (K x X) -> Y one can define a pair of secure MAC algorithms (S, V) as:
  • S(k, m) := F(k, m)
  • V(k, m, t): returns a value true if t = F(k, m) or false otherwise
  • One should consider that the set Y should be large enough that a probability of guessing the result of the F function would be negligible.

For example, to encrypt a 16-byte long message one can use the AES encryption algorithm or any other similar symmetric cipher that operates on data blocks of size of 16 bytes.

The following paragraphs present some MAC algorithms that allow to protect longer messages.

CBC MAC

CBC MAC is based on a pseudorandom function (for convenience called F). It works similarly to encryption performed in the CBC mode, with a difference that intermediate values are not returned. Moreover, after encryption of the last data block, one additional encryption of the current result is performed using the second secret key.

The additional encryption is performed to protect the calculated code. The whole process, including the last additional step, is often referred to as ECBC MAC (Encrypted MAC), in contrast to the previous algorithm steps called Raw CBC MAC.

Scheme of ECBC MAC

Without the last algorithm step (that is, without encryption using the second key), an intruder could attack CBC MAC security using a chosen-plaintext attack:

  1. The intruder chooses a message m of size of one block.
  2. The intruder obtains a value of authentication code of the message from the attacked system: t = F(k, m).
  3. At this moment, the attacker can determine a value of authentication code of the message m1 of the size of two blocks m1 = (m, t XOR m):
    rawCBC(k, m1)  = rawCBC(k, (m, t XOR m))  =  F(k, F(k, m) XOR (t XOR m))  =  F(k, t XOR (t XOR m))  =  t

CBC MAC can protect a message of any length, from one to many blocks. To ensure security, while using CBC MAC one should change the secret key every some time. It can be proved that after sending the number of messages that is equal roughly to the square of the number of all possible values of data blocks, the key is no longer safe.

The last data block should be filled up to the full length using previously agreed bits. The additional bits should clearly determine the end of the original message to prevent attackers from using a potential ambiguity. A popular method of aligning the length of the last block is to append an additional bit equal to 1 and then filling the rest of the block up with bits equal to 0. If there is not enough free space in the last block, one should add one more extra block and fill it with the additional padding bits.

For comparison, adding only zeros would cause ambiguity where is the last bit of the broadcast message (because the original message may have zeros as last bits of data). Furthermore, a lot of messages with different contents that only differ in the number of zeros at the end, would have the same authentication codes. This situation would break safety rules of message encoding.

ECBC MAC is used in various applications, for example in banking systems (ANSI X9.9, X9.19 and FIPS 186-3 standards). It is often based on the AES algorithm, that is used as F function.

NMAC

The NMAC algorithm (Nested MAC) is similar to the CBC MAC algorithm described earlier. It uses a slightly different pseudorandom function F. The function F returns numbers that are correct values of secret keys (thus, not the values of data blocks).

As in the case of CBC MAC, after encryption of the last data block, one additional encryption of the result is performed, using the second secret encryption key. Because the previous result of encryption of the last data block consists of the same amount of bits as the secret key, an additional sequence of bits (a fix pad) should be append, to assure that the result has the same size as data blocks. NMAC is usually used in systems, where the length of data blocks is much bigger than the size of secret keys.

Scheme of NMAC

The last additional encryption is performed to protect the calculated code, as in the case of CBC MAC. During encryption the subsequent blocks without the last step of NMAC, the algorithm is commonly referred to as a Cascade.

Without the last step of the algorithm (that is, without encryption using the second key), an intruder would be able to append any number of blocks to the intercepted message with the correctly calculated authentication code. Then, he could calculate a new authentication code and attach it to the modified message. As input to the first new added function F, the attacker would use the original authentication code of the original message.

To ensure NMAC security, one should change the secret key from time to time. It can be proved that after sending the number of messages equal roughly to the square of the number of all possible values of secret keys, the key is no longer safe.

The NMAC algorithm uses the same methods for adding padding bits to the end of the last incomplete message block, as the CBC MAC algorithm.

CMAC

The CMAC algorithm is similar to the previously described CBC MAC algorithm. Is uses the same pseudorandom function F, which returns numbers that are elements of the set of all possible values of data blocks.

Instead of the last additional encryption that uses a second key, CMAC uses two additional keys that are added to input bits to the last block of F function. Depending on whether the last message block is completely filled up with data bits, or it must be filled up with a previously determined sequence of padding characters, the corresponding encryption key should be used.

Scheme of CMAC

Adding the additional key in the last encryption step protects against appending new blocks of modified messages by a potential intruder. It is not necessary to use an additional encryption by the F function, unlike in other MAC algorithms. Thanks to this solution, there is no need to add an additional block to make room for padding (it is enough to choose the correct additional key).

CMAC is considered to be secure. It provides a safe way for message authentication. It is certified for example by the American institute NIST.

PMAC

The PMAC algorithm (Parallel MAC) can be performed using many threads at time, unlike other MAC algorithms described above (that require sequential processing of data blocks).

PMAC uses two secret encryption keys. The first secret key is used in P functions. All P functions receive also the subsequent numbers of the additional counter. Output bits of P functions are added XOR to data blocks. The result is encrypted by a pseudorandom function F, that uses the second secret key. The P function should be uncomplicated and it should work much faster than F functions.

Output bits from all F functions and output bits from the last data block (which is not encrypted by the F function) are added XOR together, then the result is encrypted using the F function algorithm, with the second secret encryption key.

Scheme of PMAC

As usual, it can be proved that PMAC is secure, if the secret key is changed from time to time. A new key should be created after sending the number of messages that is equal roughly to the square of the number of all possible values of data blocks.

PMAC allows to update authentication codes easily and quickly, in a case when one of the message block was replaced by a new one. For example, if a block m[x] is replaced by m'[x], then the following calculations should be performed:
    tag'  =  F(k2, (F-1(k2, tag) XOR F(k2, m[x] XOR P(k1, x)) XOR F(k2, m'[x] XOR P(k1, x)))

One-time MAC

Similar to one-time encryption, one can define a one-time MAC algorithm, which provides security against potential attacks and it is generally faster than other message authentication algorithms based on PFR functions.

Definition One-time MAC is a pair of algorithms (S, V):
  • S(m, k1, k2) := P(m, k1) + k2  (mod q): returns an authentication code t
  • V(m, k1, k2, t): returns a value true or false depending on the correctness of the examined authentication code t
where:
  • q is a large prime (about 2128),
  • m is a message that contains L blocks of size of 128 bits,
  • k1, k2 are two secret keys; each of them has value from the interval [1, q],
  • P(m, x) = m[L]⋅xL + ... + m[1]⋅x is a polynomial of degree L

It can be proved that two messages secured by using the same keys are indistinguishable for potential observers.

Carter-Wegman MAC

The construction of Carter-Wegman MAC is based on the idea of ​one-time MAC. It is extended by a pseudorandom function to allow using one secret key many times for subsequent messages.

Definition Having a secure one-time MAC (S, V) defined over sets (M, KJ, T) and a secure pseudorandom function F: KF x {0,1}n->{0,1}n, one can define a pair of algorithms Carter-Wegman MAC:
  • SC-W(m, kF, kJ) := (r, F(kF, r) XOR S(m, kJ)): returns an authentication code that is a pair (r, tC-W)
  • VC-W(m, kJ, F(kF, r) XOR tC-W): returns true or false depending on the correctness of the examined authentication code (r, tC-W)
where:
  • kJ, kF are two secret keys of sets KJ and KF,
  • T is a set of all possible values of authentication codes of the one-time MAC algorithm (of length of n bits),
  • r is a random number of length of n bits,
  • (r, tC-W) is a value of an authentication code of the Carter-Wegman algorithm (of length of 2n bits)

HMAC

HMAC is a popular system of checking message integrity, which is quite similar to NMAC.

The HMAC algorithm uses one-way hash functions to produce unique mac values.

Scheme of HMAC

The input parameters ipad and opad are used to modify the secret key. They may have various values assigned. It is recommended to choose the values that would make both inputs to the hash functions look as dissimilar as possible (that is, that modify the secret key in two different ways).

Using a secure hash function (that means the function which doesn't produce the same outputs for different input data) guarantees the security of the HMAC algorithm.

Nowadays, the HMAC algorithm is used in many systems, including some popular Internet protocols (SSL, IPsec, SSH).

Date: 2020-03-09