In cryptography, a message authentication code (MAC), sometimes known as an authentication tag, is a short piece of information used for authenticating and integrity-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.
Terminology The term message integrity code (MIC) is frequently substituted for the term MAC, especially in communications to distinguish it from the use of the latter as Media Access Control (as in MAC address). However, some authors use MIC to refer to a message digest, which aims only to uniquely but opaquely identify a single message. As such, it is recommended to avoid the term message integrity code (MIC), and instead use checksum, error detection code, hash, keyed hash, message authentication code, or protected checksum.
Definitions Informally, a message authentication code system consists of three algorithms:
A key generation algorithm selects a key from the key space uniformly at random. A MAC generation algorithm efficiently returns a tag given the key and the message. A verifying algorithm efficiently verifies the authenticity of the message given the same key and the tag. That is, return accepted when the message and tag are not tampered with or forged, and otherwise return rejected. A secure message authentication code must resist attempts by an adversary to forge tags, for arbitrary, selected, or all messages, including under conditions of known- or chosen-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. Formally, a message authentication code (MAC) system is a triple of efficient algorithms (G, S, V) satisfying:
G (key-generator) gives the key k on input 1n, where n is the security parameter. S (signing) outputs a tag t on the key k and the input string x. V (verifying) outputs accepted or rejected on inputs: the key k, the string x and the tag t. S and V must satisfy the following:
Pr [ k ← G(1n), V( k, x, S(k, x) ) = accepted ] = 1. A MAC is unforgeable if for every efficient adversary A
Pr [ k ← G(1n), (x, t) ← AS(k, · )(1n), x ∉ Query(AS(k, · ), 1n), V(k, x, t) = accepted] < negl(n), where AS(k, · ) denotes that A has access to the oracle S(k, · ), and Query(AS(k, · ), 1n) denotes the set of the queries on S made by A, which knows n. Clearly we require that any adversary cannot directly query the string x on S, since otherwise a valid tag can be easily obtained by that adversary.
Security While MAC functions are similar to cryptographic hash functions, they possess different security requirements. To be considered secure, a MAC function must resist existential forgery under chosen-message attacks. This means that even if an attacker has access to an oracle 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 from digital 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 with symmetric encryption. For the same reason, MACs do not provide the property of non-repudiation offered by signatures specifically in the case of a network-wide shared 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. 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 a hardware security module that only permits MAC verification. This is commonly done in the finance industry.
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 to collision resistance or preimage security in hash functions. For MACs, these concepts are known as commitment and context-discovery security.
Implementation MAC algorithms can be constructed from other cryptographic primitives, like cryptographic hash functions (as in the case of HMAC) or from block cipher algorithms (OMAC, CCM, GCM, and PMAC). However many of the fastest MAC algorithms, like UMAC-VMAC and Poly1305-AES, are constructed based on universal hashing. Intrinsically keyed hash algorithms such as SipHash are also by definition MACs; they can be even faster than universal-hashing based MACs. 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, in Transport Layer Security (TLS) versions before 1.2, the input data is split in halves that are each processed with a different hashing primitive (SHA-1 and SHA-2) then XORed together to output the MAC.
… excerpt ends here. Continue reading the full article.
