Incryptography, amessage authentication code (MAC), sometimes known as anauthentication tag, is a short piece of information used forauthenticating andintegrity-checking a message. In other words, it is used to confirm that the message came from the stated sender (its authenticity) and has not been changed (its integrity). The MAC value allows verifiers (who also possess a secret key) to detect any changes to the message content.
The termmessage integrity code (MIC) is frequently substituted for the termMAC, especially in communications[1] to distinguish it from the use of the latter asMedia Access Control address (MAC address). However, some authors[2] use MIC to refer to amessage digest, which aims only to uniquely but opaquely identify a single message. However, it is recommended to avoid the termmessage integrity code (MIC), and instead usechecksum,error detection code,hash,keyed hash,message authentication code, orprotected checksum.[3]
Informally, a message authentication code system consists of three algorithms:
A secure message authentication code must resist attempts by an adversary toforge tags, for arbitrary, selected, or all messages, including under conditions ofknown- orchosen-message. It should be computationally infeasible to compute a valid tag of the given message without knowledge of the key, even if for the worst case, we assume the adversary knows the tag of any message but the one in question.[4]
Formally, amessage authentication code (MAC) system is a triple of efficient[5] algorithms (G,S,V) satisfying:
S andV must satisfy the following:
A MAC isunforgeable if for every efficient adversaryA
whereAS(k, · ) denotes thatA has access to the oracleS(k, · ), and Query(AS(k, · ), 1n) denotes the set of the queries onS made byA, which knowsn. Clearly we require that any adversary cannot directly query the stringx onS, since otherwise a valid tag can be easily obtained by that adversary.[7]
While MAC functions are similar tocryptographic hash functions, they possess different security requirements. To be considered secure, a MAC function must resistexistential forgery underchosen-message attacks. This means that even if an attacker has access to anoracle which possesses the secret key and generates MACs for messages of the attacker's choosing, the attacker cannot guess the MAC for other messages (which were not used to query the oracle) without performing infeasible amounts of computation.
MACs differ fromdigital signatures as MAC values are both generated and verified using the same secret key. This implies that the sender and receiver of a message must agree on the same key before initiating communications, as is the case withsymmetric encryption. For the same reason, MACs do not provide the property ofnon-repudiation offered by signatures specifically in the case of a network-wideshared secret key: any user who can verify a MAC is also capable of generating MACs for other messages. In contrast, a digital signature is generated using the private key of a key pair, which is public-key cryptography.[5] Since this private key is only accessible to its holder, a digital signature proves that a document was signed by none other than that holder. Thus, digital signatures do offer non-repudiation. However, non-repudiation can be provided by systems that securely bind key usage information to the MAC key; the same key is in the possession of two people, but one has a copy of the key that can be used for MAC generation while the other has a copy of the key in ahardware security module that only permits MAC verification. This is commonly done in the finance industry.[citation needed]
While the primary goal of a MAC is to prevent forgery by adversaries without knowledge of the secret key, this is insufficient in certain scenarios. When an adversary is able to control the MAC key, stronger guarantees are needed, akin tocollision resistance orpreimage security in hash functions. For MACs, these concepts are known ascommitment andcontext-discovery security.[8]
MAC algorithms can be constructed from other cryptographic primitives, likecryptographic hash functions (as in the case ofHMAC) or fromblock cipher algorithms (OMAC,CCM,GCM, andPMAC). However many of the fastest MAC algorithms, likeUMAC-VMAC andPoly1305-AES, are constructed based onuniversal hashing.[9]
Intrinsically keyed hash algorithms such asSipHash are also by definition MACs; they can be even faster than universal-hashing based MACs.[10]
Additionally, the MAC algorithm can deliberately combine two or more cryptographic primitives, so as to maintain protection even if one of them is later found to be vulnerable. For instance, inTransport Layer Security (TLS) versions before 1.2, theinput data is split in halves that are each processed with a different hashing primitive (SHA-1 andSHA-2) thenXORed together to output the MAC.
Universal hashing and in particularpairwise independent hash functions provide a secure message authentication code as long as the key is used at most once. This can be seen as theone-time pad for authentication.[11]
The simplest such pairwise independent hash function is defined by the random key,key = (a,b), and the MAC tag for a messagem is computed astag = (am +b) modp, wherep is prime.
More generally,k-independent hashing functions provide a secure message authentication code as long as the key is used less thank times fork-ways independent hashing functions.
Message authentication codes and data origin authentication have been also discussed in the framework ofquantum cryptography. By contrast to other cryptographic tasks, such as key distribution, for a rather broad class of quantum MACs it has been shown that quantum resources do not offer any advantage over unconditionally secure one-time classical MACs.[12]
Various standards exist that define MAC algorithms. These include:
ISO/IEC 9797-1 and -2 define generic models and algorithms that can be used with any block cipher or hash function, and a variety of different parameters. These models and parameters allow more specific algorithms to be defined by nominating the parameters. For example, the FIPS PUB 113 algorithm is functionally equivalent to ISO/IEC 9797-1 MAC algorithm 1 with padding method 1 and a block cipher algorithm of DES.
[21] In this example, the sender of a message runs it through a MAC algorithm to produce a MAC data tag. The message and the MAC tag are then sent to the receiver. The receiver in turn runs the message portion of the transmission through the same MAC algorithm using the same key, producing a second MAC data tag. The receiver then compares the first MAC tag received in the transmission to the second generated MAC tag. If they are identical, the receiver can safely assume that the message was not altered or tampered with during transmission (data integrity).
However, to allow the receiver to be able to detectreplay attacks, the message itself must contain data that assures that this same message can only be sent once (e.g. time stamp,sequence number or use of aone-time MAC). Otherwise an attacker could – without even understanding its content – record this message and play it back at a later time, producing the same result as the original sender.
