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 to verify its integrity. MAC algorithms require two input parameters, firstly, the data to be protected and, secondly, a secret key and calculate a checksum of both, the Message Authentication Code.

Operation

The integrity of a message to be transmitted can be set via MACs as check follows: First, the sender and receiver agree on a secret key. The sender calculates for this key and its message a MAC and then sends the message and the MAC to the receiver. This calculates the MAC to the received message with the key and compares the computed MAC with the received. The agreement between the two values ​​, the receiver interprets as successful Integrity Test: This message was sent from a party that knows the secret key, and it was not modified during transmission.

MACs do not protect against replay attacks. For this, the message itself contain data that ensure that repetitions can be detected (eg timestamp, sequence number, or by the use of one-time MACs).

Determination of MAC

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

Definition of hash functions and digital signatures

Cryptographic hash functions can be used for calculation of MACs, but MACs go beyond the use of simple hash out: When a message would be transmitted only by its hash value as the MAC, this would not be safe because the hash function is publicly known. An attacker could modify the message and compute a new hash value for the new message, and transfer this. However, if the sender and receiver share a secret, it may be included in the hash calculation, so that an attacker is not able after modification of a message to calculate the matching hash value.

Even if the tamper resistance of MACs suggesting a relationship with digital signatures, there are differences between the two methods. MACs differ from digital signatures is that the verification of the MACs knowledge of the same secret key requires that was used to calculate it. Therefore, anyone who can verify a MAC can also calculate this; he is therefore able to prove to a third party from whom the message originates. In contrast, digital signatures can be created using a key known only to the sender and verified using a public key. This ensures that the signers in the possession of the private key, and it is so with high probability is the default author of the message.

Information Theoretically safe method

Example

A plaintext bit (A or B) is to be transmitted authenticated by a 1 -bit MAC. The key is two bits long.

* (Text, MAC)

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

Safety analysis

Suppose an attacker captures the first transmitted pair from the above example and tries to send a B instead of A. Thus, the change is not noticed and he does not really stand, it requires the matching MAC. He is known from the overview that the corresponding key portion 10 or 11 is. With this knowledge, it is not possible for him to choose between (B, 0) and ( B, 1 ). Exactly the same choice he is even without knowing the key portion, that is the question MAC = MAC = 0 or 1 So he advises on average correct in every second case.

About this issue, you can define general information-theoretical security.

W ( x | S) = W ( x ) ( for the notation see Conditional Probability ) In words: Regardless of the a priori knowledge about the plaintext x an attacker gains by seeing the ciphertext S ( here: plaintext and MAC) or portions thereof no information added. Thus, absolute security is given to Shannon.

For all reflections is of course that the described system works correctly and is also so used. If the attacker, for example, the secret key ( or parts ) in the hand, as well as information-theoretically secure systems are to break.

Properties

The following properties apply to the general case. In particular, there are more efficient methods derived the same quality.

The probability of error (example: 0.5 ) is determined by the length of the MAC used per message bit (example: 1)

There must always be a matching and thus randomly guessed MAC, no probability can be guaranteed equal to zero by the extension of the MAC. By the asymptotic context, the probability approaches but quickly negligible dimensions.

The required key length (example: 2) is determined by. So, if you want a message length transferred, key bits are (example: 8 ) is necessary.

Analogous to the one- time pad here is also the question of how many keys are needed to ensure the desired security and just described. Generally, this value is specified. For the above example with the specified dimensions ( inter alia size of MAC and key ) is optimal.