What is Message Authentication Codes?

What is Message Authentication Codes? – A message authentication code, or MAC, is a construction that detects tampering with messages. Encryption prevents Eve from reading the messages but does not prevent her from manipulating the messages. This is where the MAC comes in. Like encryption, MACs use a secret key, K, known to both Alice and Bob but not to Eve. Alice sends not just the message m, but also a MAC value computed by a MAC function. Bob checks that the MAC value of the message received equals the MAC value received. If they do not match, he discards the message as unauthenticated. Eve cannot manipulate the message because without K she cannot find the correct MAC value to send with the manipulated message.

What is Message Authentication Codes

What a MAC Does

A MAC is a function that takes two arguments, a fixed-size key K and an arbitrarily sized message m, and produces a fixed-size MAC value. We’ll write the MAC function as mac(K, m). To authenticate a message, Alice sends not only the message m but also the MAC code mac(K, m), also called the tag. Suppose Bob, also with key K, receives a message m  and a tag T. Bob uses the MAC verification algorithm to verify that T is a valid MAC under key K for message m.

We start with a look at the MAC function in isolation. Be warned that using a MAC function properly is more complicated than just applying it to the message.

What is Message Authentication Codes

The Ideal MAC and MAC Security

There are various ways to define the security of a MAC. We describe here our preferred definition. This definition is based on the notion of an ideal MAC function, which is very similar to the notion of an ideal block cipher. The primary difference is that block ciphers are permutations, whereas MACs are not. This is our preferred definition because it encompasses a broad range of attacks, including weak key attacks, related-key attacks, and more.

The ideal MAC is a random mapping. Let n be the number of bits in the
result of a MAC. Our definition of an ideal MAC is:

Remember that, in this definition, the MAC takes two inputs, a key and a message. In practice, the key K is not known to the attacker or, more precisely, it is not fully known. There could be a weakness in the rest of the system that provides partial information about K to the attacker.

Cryptography is a broad field. There are more formal definitions that the oreticians use. When possible, we prefer the definition above because it is broader and more aligned with the full range of attacks one might consider. Our attack model includes some forms of attacks not captured by the conventional, formal definitions, such as related-key attacks and attacks that assume that the attacker has partial knowledge about the key. That is why we prefer our style of security definitions, which are robust even if the function is abused or used in an unusual environment.

The more restrictive standard definition is one in which an attacker selects n different messages of her choosing, and is given the MAC value for each of these messages. The attacker then has to come up with n + 1 messages, each with a valid MAC value.

What is Message Authentication Codes

CBC-MAC and CMAC

CBC-MAC is a classic method of turning a block cipher into a MAC. The key K is used as the block cipher key. The idea behind CBC-MAC is to encrypt the message m using CBC mode and then throw away all but the last block of ciphertext. For a message P 1 , . . . , P k , the MAC is computed as:

H 0 := IV
H i := E K (P i ⊕ H i−1 )
MAC := H k

Sometimes the output of the CBC-MAC function is taken to be only part (e.g., half) of the last block. The most common definition of CBC-MAC requires the IV to be fixed at 0.

In general, one should never use the same key for both encryption and authentication. It is especially dangerous to use CBC encryption and CBC-MAC authentication with the same key. The MAC ends up being equal to the last ciphertext block. What’s more, depending on when and how CBC encryption and CBC-MAC are applied, using the same key for both can lead to privacy compromises for CBC encryption and authenticity compromises for CBC-MAC.

Using CBC-MAC is a bit tricky, but it is generally considered secure when used correctly and when the underlying cipher is secure. Studying the strengths and weaknesses of CBC-MAC can be very educational. There are a number of different collision attacks on CBC-MAC that effectively limit the security to half the length of the block size [20]. Here is a simple collision attack: let M be a CBC-MAC function. If we know that M(a) = M(b) then we also know that M(a  c) = M(b  c). This is due to the structure of CBC-MAC. Let’s illustrate this with a simple case: c consists of a single block. We have

M(a  c) = E K (c ⊕ M(a))
M(b  c) = E K (c ⊕ M(b))

and these two must be equal, because M(a) = M(b).

The attack proceeds in two stages. In the first stage, the attacker collects the MAC values of a large number of messages until a collision occurs. This takes 2 64 steps for a 128-bit block cipher because of the birthday paradox. This provides the a and b for which M(a) = M(b). If the attacker can now get the sender to authenticate a  c, he can replace the message with b  c without changing the MAC value. The receiver will check the MAC and accept the bogus message b  c. (Remember, we work in the paranoia model. It is quite acceptable for the attacker to create a message and get it authenticated by the sender. There are many situations in which this is possible.) There are many extensions to this attack that work even with the addition of length fields and padding rules [20].

This is not a generic attack, as it does not work on an ideal MAC function. Finding the collision is not the problem. That can be done for an ideal MAC function in exactly the same way. But once you have two messages a and b, for which M(a) = M(b), you cannot use them to forge a MAC on a new message, whereas you can do that with CBC-MAC.

As another example attack, suppose c is one block long and M(a  c) = M(b  c). Then M(a  d) = M(b  d) for any block d. The actual attack is similar to the one above. First the attacker collects the MAC values of a large number of messages that end in c until a collision occurs. This provides the values of a and b. The attacker then gets the sender to authenticate a  d. Now he can replace the message with b  d without changing the MAC value.

There are some nice theoretical results which argue that, in the particular proof model used, CBC-MAC provides 64 bits of security when the block size is 128 bits [6] and when the MAC is only ever applied to messages that are the same length. Unfortunately, this is short of our desired design strength, though in practice it’s not immediately clear how to achieve our desired design strength with 128-bit block ciphers. CBC-MAC would be fine if we could use a block cipher with a 256-bit block size.

There are other reasons why you have to be careful how you use CBC-MAC. You cannot just CBC-MAC the message itself if you wish to authenticate messages with different lengths, as that leads to simple attacks. For example, suppose a and b are both one block long, and suppose the sender MACs a, b, and a  b. An attacker who intercepts the MAC tags for these messages can now forge the MAC for the message b  (M(b) ⊕ M(a) ⊕ b), which the sender never sent. The forged tag for this message is equal to M(a  b), the tag for a  b. You can figure out why this is true as an exercise, but the problem arises from the fact that the sender MACs messages that are different lengths.

If you wish to use CBC-MAC, you should instead do the following:

  1. Construct a string s from the concatenation of l and m, where l is the length of m encoded in a fixed-length format.
  2. Pad s until the length is a multiple of the block size. (See Section 4.1 for
    details.)
  3. Apply CBC-MAC to the padded string s.
  4. Output the last ciphertext block, or part of that block. Do not output any of
    the intermediate values.

The advantage of CBC-MAC is that it uses the same type of computations as the block cipher encryption modes. In many systems, encryption and MAC are the only two functions that are ever applied to the bulk data, so these are the two speed-critical areas. Having them use the same primitive functions makes efficient implementations easier, especially in hardware.

What is Message Authentication Codes?

Still, we don’t advocate the use of CBC-MAC directly, because it is difficult to use correctly. One alternate that we recommend is CMAC [42]. CMAC is based on CBC-MAC and was recently standardized by NIST. CMAC works almost exactly like CBC-MAC, except it treats the last block differently. Specifically, CMAC xors one of two special values into the last block prior to the last block cipher encryption. These special values are derived from the CMAC key, and the specific one used by CMAC depends on whether the length of the message is a multiple of the block cipher’s block length or not. The xoring of these values into the MAC disrupts the attacks that compromise CBC-MAC when used for messages of multiple lengths.

If You Like this Blog Please Comment Down

For More Hacking Content Click Here

Related posts

Leave a Comment