Message Authentication Code (MAC)

In cryptography, a message authentication code (MAC), sometimes known as a tag, 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. 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:

• A key generation algorithm selects a key from the key space uniformly at random.

• A signing algorithm efficiently returns a tag given the key and the message.

• A verifying algorithm efficiently verifies the authenticity of the message given the key and the tag. That is, return accepted when the message and tag are not tampered with or forged, and otherwise return rejected.

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

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.

Message integrity codes

The term message integrity code (MIC) is frequently substituted for the term MAC, especially in communications, to distinguish it from the use of MAC meaning MAC address (for media access control address). However, some authors use MIC to refer to a message digest, which is different from a MAC – a message digest does not use secret keys. This lack of security means that any message digest intended for use gauging message integrity should be encrypted or otherwise be protected against tampering. Message digest algorithms are created such that a given message will always produce the same message digest assuming the same algorithm is used to generate both. Conversely, MAC algorithms are designed to produce matching MACs only if the same message, secret key and initialization vector are input to the same algorithm. Message digests do not use secret keys and, when taken on their own, are therefore a much less reliable gauge of message integrity than MACs. Because MACs use secret keys, they do not necessarily need to be encrypted to provide the same level of assurance.

An example of MAC use

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 detect replay 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 a one-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.

One-time MAC

Universal hashing and in particular pairwise independent hash functions provide a secure message authentication code as long as the key is used at most once. This can be seen as the one-time pad for authentication.

The simplest such pairwise independent hash function is defined by the random key key = (a,b), and the MAC tag for a message m is computed as tag = (am + b) mod p, where p is prime.

More generally, k-independent hashing functions provide a secure message authentication code as long as the key is used less than k times for k-ways independent hashing functions.

Approaches to authenticated encryption

Encrypt-then-MAC (EtM)

The plaintext is first encrypted, then a MAC is produced based on the resulting ciphertext. The ciphertext and its MAC are sent together. Used in, e.g., IPsec.[10] The standard method according to ISO/IEC 19772:2009.[5] This is the only method which can reach the highest definition of security in AE, but this can only be achieved when the MAC used is "strongly unforgeable".[11] In November 2014, TLS and DTLS extension for EtM has been published as RFC 7366. Various EtM ciphersuites exist for SSHv2 as well (e.g. [e-mail]).

Encrypt-and-MAC (E&M)

A MAC is produced based on the plaintext, and the plaintext is encrypted without the MAC. The plaintext's MAC and the ciphertext are sent together. Used in, e.g., SSH. Even though the E&M approach has not been proved to be strongly unforgeable in itself,it is possible to apply some minor modifications to SSH to make it strongly unforgeable despite the approach.

MAC-then-Encrypt (MtE)

A MAC is produced based on the plaintext, then the plaintext and MAC are together encrypted to produce a ciphertext based on both. The ciphertext (containing an encrypted MAC) is sent. Used in, e.g., SSL/TLS. Even though the MtE approach has not been proven to be strongly unforgeable in itself,the SSL/TLS implementation has been proven to be strongly unforgeable by Krawczyk who showed that SSL/TLS was in fact secure because of the encoding used alongside the MtE mechanism.Despite the theoretical security, deeper analysis of SSL/TLS modeled the protection as MAC-then-pad-then-encrypt, i.e. the plaintext is first padded to the block size of the encryption function. Padding errors often result in the detectable errors on the recipient's side, which in turn lead to padding oracle attacks, such as Lucky Thirteen.