Message authentication code

In cryptography, a message authentication code (MAC) is a short piece of information used to authenticate a message—in other words, to confirm that the message came from the stated sender (its authenticity) and has not been changed in transit (its integrity).

A MAC algorithm, sometimes called a keyed (cryptographic) hash function (which is somewhat misleading, since a cryptographic hash function is only one of the possible ways to generate a MAC), accepts as input a secret key and an arbitrary-length message to be authenticated, and outputs a MAC (sometimes known as a tag). The MAC value protects both a message's data integrity as well as its authenticity, by allowing verifiers (who also possess the secret key) to detect any changes to the message content.

Informally, a message authentication code consists of three algorithms:

For a secure unforgeable message authentication code, 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 can forge the tag of any message except the given one.

Formally, A Message Authentication Code (MAC) is a triple of efficient algorithms (G, S, V) satisfying:

A MAC is unforgeable if for every efficient adversary A

where A^{S(k, · )} denotes that A has access to the oracle S(k, · ), and Query(A^{S(k, · )}, 1ⁿ) 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 she can easily obtain a valid tag.

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-plaintext 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.

...
Wikipedia