Message Authentication Code

A Message Authentication Code ( MAC ; German message authentication code ) is used to obtain certainty about the origin of data or messages and their integrity check. MAC algorithms require two input parameters, firstly the data to be protected and secondly a secret key , and calculate a checksum from both , the message authentication code.

functionality

How a MAC works

The integrity of a message to be transmitted can be checked using MACs as follows: First, the sender and recipient agree on a secret key. The sender calculates a MAC for this key and its message and then sends the message and the MAC to the recipient. This calculates the MAC for the received message with the key and compares the calculated MAC with the received one. The recipient interprets the agreement of both values ​​as a successful integrity test: the message was sent by a party who knows the secret key and it was not changed during transmission.

MACs do not protect against replay attacks . To do this, the message itself must contain data that ensure that repetitions can be detected (e.g. time stamp, sequence number or through the use of one-time MACs).

Determination of the MAC

MACs are either based on block ciphers or hash functions or are specially developed MACs. A common method for MAC calculation, the HMAC , is based on cryptographic hash functions and is used, for example, in SSL and IPsec . A common method based on block ciphers is the Cipher-Based Message Authentication Code (CMAC) specified in NIST Special Publication 800-38B, which is used in conjunction with AES or Triple DES . An older method for calculating a MAC based on DES and CBC is standardized as ANSI X9.9, but has since been revoked due to security deficiencies. A special MAC is the Message Authentication Algorithm (MAA), which was developed in 1983 as a standard for banks.

Differentiation of hash functions and digital signatures

Cryptographic hash functions can be used to calculate MACs, but MACs go beyond the use of simple hash values: If a message were only transmitted with its hash value as a MAC, this would not be secure because the hash function is publicly known. An attacker could modify the message and calculate and transmit a new hash value for the new message. However, if the sender and recipient share a secret, this can flow into the hash calculation, so that an attacker is unable to calculate the appropriate hash value after modifying a message.

Even if the manipulation security of MACs suggests a relationship with digital signatures , there are differences between the two methods. MACs differ from digital signatures in that checking the MAC requires knowledge of the same secret key that was used to calculate it. Therefore anyone who can check a MAC can also calculate it; accordingly, he is unable to prove to third parties who the message came from. In contrast, digital signatures are created using a key known only to the sender and verified using a public key. This ensures that the signer is in possession of the private key and that there is a high degree of probability that it is the specified author of the message.

Information-theoretically secure procedures

This section is not adequately provided with supporting documents ( e.g. individual evidence ). Information without sufficient evidence could be removed soon. Please help Wikipedia by researching the information and including good evidence.

See talk page, section “Receipts are missing” . - JensLechtenboerger 4:53 p.m. , 9 November 2011 (CET)

example

A plain text bit ( A or B ) should be transmitted in an authenticated manner using a 1-bit MAC. The key is two bits long.

key	(A, 0) *	(A, 1) *	(B, 0) *	(B, 1) *
00	A.		B.
01	A.			B.
10		A.	B.
11		A.		B.

* (Text, MAC)

The message AABB under the (previously agreed) secret key 11000110 is then transmitted as (A, 1) (A, 0) (B, 1) (B, 0).

Security analysis

Suppose an attacker intercepts the first transmitted pair from the above example and tries to send a B instead of the A. So that the change is not noticed and he is not noticed, he needs the appropriate MAC. He knows from the overview that the corresponding key section is 10 or 11 . With this knowledge, however, it is not possible for him to decide between (B, 0) and (B, 1). He is faced with exactly the same decision even without knowing the key section, i.e. the question MAC = 0 or MAC = 1. So, on average, he guesses correctly in every second case.

This fact can be used to generally define information-theoretical security.

${\displaystyle W(x\mid S)=W(x)}$(for notation see conditional probability )

In words: regardless of the a priori knowledge of the plain text x , an attacker does not receive any additional information by seeing the ciphertext S (here: plain text and MAC) or parts thereof. This gives absolute security according to Shannon .

In all considerations, it is of course assumed that the system described functions correctly and is also used that way. If the attacker z. If, for example, the secret key (or parts) is in hand, systems that are secure in terms of information theory must also be broken.

properties

The following properties relate to the general case. In particular, there are derived, more efficient processes of the same quality.

The error probability (in the example: 0.5) is determined from the length of the MAC used per message bit (in the example: 1) ${\displaystyle \varepsilon }$ ${\displaystyle \sigma }$ ${\displaystyle \varepsilon =2^{-\sigma }}$

Since there must always be a suitable MAC that can be guessed at random, even extending the MAC cannot guarantee a probability of zero. Due to the asymptotic relationship, however, the probability quickly approaches negligible dimensions.

The necessary key length (using the example: 2) is determined by . So if you want to transmit a message of length , key bits (in the example: 8) are required. ${\displaystyle 2\sigma }$ ${\displaystyle l}$ ${\displaystyle l2\sigma }$

Analogous to the one-time pad , the question arises as to how many keys are necessary to ensure the desired and just described security. In general, this value is also specified. The above example with the specified dimensions (including the size of MAC and key) is therefore optimal. ${\displaystyle \epsilon ^{-2}}$

literature

• Charlie Kaufman, Radia Perlman, Mike Speciner: Network Security: Private Communication in a Public World. Prentice Hall PTR, Upper Saddle River, New Jersey 2002, ISBN 0-13-046019-2 .
• Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone: Handbook of Applied Cryptography. CRC Press, 2001, ISBN 0-8493-8523-7 . (on-line)
• William Stallings: Cryptography and Network Security: Principles and Practice. 5th edition. (International Edition), Prentice Hall, 2011, ISBN 978-0-13-705632-3 .

Individual evidence

1. ↑ dict.cc: message authentication code <MAC> | Message authentication code
2. ↑ ^{a b} Menezes et al: Handbook of Applied Cryptography. P. 323.
3. ↑ Menezes et al: Handbook of Applied Cryptography. P. 364.
4. ^ Stallings: Cryptography and Network Security: Principles and Practice. P. 400.
5. ^ Stallings: Cryptography and Network Security: Principles and Practice. P. 404.
6. ↑ X9 Committee: Withdrawal of ANSI X9.9, Financial Institution Message Authentication (PDF; 157 kB) Archived from the original on February 5, 2007. Retrieved on November 9, 2011.
7. ^ Kaufman et al.: Network Security: Private Communication in a Public World. P.56.
8. ↑ ^{a b c} Kaufman et al.: Network Security: Private Communication in a Public World. P. 51.