Question

Consider Message Authentication Codes: a) Identify whether an symmetric/asymmetric cryptosystem is used and explain how it is applied to generate and validate the MAC. b) Describe any additional information is needed by the receiver to validate the MAC. c) Explain whether the receiver can trust a successfully validated MAC and any assumptions about the additional information you identified in (b) for a validated MAC to be trusted.

Answer 1

A message authentication code (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.

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.

Algorithms Used to Generate MACs:

Three algorithms typically comprise a MAC: a key generation algorithm, a signing algorithm and a verifying algorithm. The key generation algorithm chooses a key at random. The signing algorithm sends a tag when given the key and the message. The verifying algorithm is used to verify the authenticity of the message when given the key and tag; it will return a message of accepted if the message and tag are authentic and unaltered, but otherwise, it will return a message of rejected.

However, the message itself should contain some data that ensures that this message can only be sent once. For example, a one-time MAC, timestamp or sequence number could be used to guarantee that the message can only be sent once. Otherwise, the system could be vulnerable to a replay attack, in which an attacker intercepts the message after it has been decoded and retransmits it at a later time, replicating the original results and infiltrating the system.

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.

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 m₁ of the size of two blocks m₁ = (m, t XOR m):
   rawCBC(k, m₁) = 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.

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.

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, k₁, k₂) := P(m, k₁) + k₂  (mod q): returns an authentication code t
• V(m, k₁, k₂, t): returns a value true or false depending on the correctness of the examined authentication code t

where:

• q is a large prime (about 2¹²⁸),
• m is a message that contains L blocks of size of 128 bits,
• k₁, k₂ are two secret keys; each of them has value from the interval [1, q],
• P(m, x) = m[L]⋅x^L + ... + 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.