Basics of Message Authentication Code (MAC)

One of the most attractive and complex area of cryptography is that of message authentication and the related area of digital signatures. 

1. Message Authentication Requirements (MAC) :

Now why we need MAC? 😴. While communicating across a network, the following attacks are identifies so that we generally uses MAC.

1.1 Disclosure : Release of message contents to any person outside the network. 

1.2 Traffic analysis : Discovery of the pattern of traffic between parties. In connection oriented system the frequency and duration of the connections can be determined. In case of connectionless the number and length of message between parties could be determined. 

1.3 Masquerade : Insertion of message into the network from a fraudulent source. 

1.4 Content Modification : It means any kind of change in the message such as inserting something, deleting something, transposition, and modifying message. 

1.5 Sequence Modification : Any modification to a sequence of message between parties, including again insertion, deletion, modification.

1.6 Timing Modification : Delay or replay of message. 

1.7 Source Repudiation : Means denial of transmission by source. 

1.8 Destination Repudiation : Denial of receipt if message by destination .

Note 1 : Since 1.1, 1.2 provides confidentiality. 1.3, 1.4, 1.5, 1.6 provides authentication. 1.7 provides digital signature. 1.8 provides combination of digital signature and a protocol designed to counter this attack.

2. Message Authentication Functions :

This section works with the types of functions that may be used to produce an authenticator. These may be grouped into three classes. 

2.1 Hash Function : A function that maps a message of any length into a fixed-length hash value, which serves as the authenticator. 

2.2 Message Encryption : Message encryption by itself can provide a measure of authentication. The analysis differs for symmetric and public key encryption schemes. 

2.2.1 Symmetric Encryption : 

Please see the Figure 1 for better clarity regarding this topic. 😊

If M is recoverable, B knows that none of the bits of M have been altered because an opponent that does not know K would not know to alter bits in the ciphertext to produce the desired changes in the plaintext. So we may say that symmetric encryption provides authentication as well as confidentiality. 

Now this statement needs to be justified. Consider exactly what is happening at B. Given a decryption function 'D' and a secret key 'k', the destination will accept any input 'X' and produce output 'Y', Y = D(K,X). if X is the ciphertext of a legimate message M produce by the corresponding encryption  function, then 'Y' is some plaintext message 'M'. Otherwise, Y will likely to be meaningless sequence of bits. There may need to be some automated means of determining at B whether 'Y' is legimate plaintext and therefore must have come from A. 

Suppose the Message M can be any arbitrary bit pattern. In that case, there is no way to determine automatically at the destination, whether an incoming message is the ciphertext of a legimate message. This conclusion is incontrovertible if M can be any bit pattern, then regardless of the value of X the value Y = D(K,X) is some bit pattern and therefore must be accepted as authentic plaintext. 

Fig. 1: Basic Uses of Message Encryption 

If a plaintext is, say binary object file or digitized X-Rays determination of properly formed and therefore authentic plaintext may be difficult. Thus, an opponent could achieve a certain level of disruption simply by issuing message with random content purporting to come from a legimate user. 

To overcome this above problem , we calculate frame check sequence (FCS) or checksum. If the calculated FCS is equal to the incoming FCS, then the message is considered as authentic. 

Now the order in which the FCS and encryption function are performed is critical. The sequence illustrated in below figure (as shown in Fig. 2) as internal error control, which is contrast with external error control. 

Fig. 2: Internal and External Error Control

The FCS is outer code, an opponent can construct message with valid error control codes. Although the opponent cannot know what the decryption plaintext will be, he or she can still hope to create confusion and disrupt option. 

For error control code, considered the structure of message transmitted using the TCP/IP protocol architecture (as shown in Fig. 3).  

Fig. 3 : TCP Segment

Now suppose each pair of hosts used a unique secret key. So that all exchanges between a pairs of hosts used the same key, regardless of application. Then we could simply encrypt all of the datagram except the IP header. Again, if an opponent substituted some arbitrary bit pattern for the encrypted TCP segment. The resulting plaintext would includes not only checksum but also other useful information such as sequence number. because successive TCP segments on a given connection are numbered sequentially, encryption assures that an opponent does not delay, mis order or delete any segments.  

2.2.2 Public Key Encryption : It provides confidentiality but not authentication (Please see Figure 1 for better understanding means how authentication and confidentiality is achieved)☺.

2.3 Message Authentication Code :  An Alternative authentication technique involves the use of a secret key to generate a small fixed size block of data, known as a cryptographic checksum or MAC, that is appended to the message. 

This technique assumes that two communicating parties say A and B share a common secret key K. When A has a message to sent to B, it calculates the MAC as a function of the message and the key. 

MAC = C(K,M)

Here, M = Input Message ; C = MAC function ; K = shared secret key ; MAC = Message Authentication Code. 

The message plus MAC are transmitted to the intended recipient. The recipient performs the same calculation on the received message, using the same secret key, to generate a new MAC. The received MAC is compared to the calculated MAC. 

if we assume that only the receiver and the sender know the identity of the secret key, and if the received MAC matches the calculated MAC, then : 

1. The receiver is assured that the message has not been altered. If an attacker alters the message but does not alter the MAC, then the receiver's calculation of the MAC will differ from the received MAC because the attacker is assumed not to know the secret key, the attacker can not alter the MAC to correspond to the alterations in the message. 

2. The receiver is assured that the message is from the alleged sender because no one else knows the secret key, no one else could prepare a message with a proper MAC.

3. If the message includes a sequence number, then the receiver can be assured of the proper sequence because an attacker can not successfully alter the sequence number. 

Fig. 4: Basic Use of Message Authentication Code (MAC)

Note 2. A MAC function is similar to encryption. One difference is that the MAC algorithm need not be reversible as it must be for decryption. Mac function is many to one function.

3. Security of MAC : 

The security of MAC depends on two attacks 

3.1 Brute Force Attack : It is quite difficult for this. We have some knowledge of known message tag pairs.

Suppose given one or more text MAC pairs [xi, MAC(K,xi)], it is computationally infeasible to compute any text MAC pair [x, MAC(K,x)] for any new input x = xi.

3.2 Cryptanalysis : An ideal MAC algorithm will require a cryptanalytic effort greater than or equal to the brute force attack. 

There is much more variety in the structure of MAC than in hash function. So, it is difficult to generalize about the cryptanalysis of MAC's. Furthermore, for less work has been done on developing such attacks. 

**************************************************************************************************************