Requirements: Message Authentication Codes
A MAC, also known as a cryptographic checksum, is generated by a function C of the form
𝑇 = 𝑀𝐴𝐶(𝐾, 𝑀)
M is a variable-length message,
K is a secret key shared only by sender and receiver, and
MAC (K, M) is the fixed-length authenticator also called a tag.
- The tag is appended to the message at the source at a time when the message is assumed or known to be correct. The receiver authenticates that message by re-computing the tag.
- When an entire message is encrypted for confidentiality, using either symmetric or asymmetric encryption, the security of the scheme generally depends on the bit length of the key.
- Barring some weakness in the algorithm, the opponent must resort to a brute-force attack using all possible keys.
- On average, such an attack will require 2k-1 attempts for a k-bit key. In particular, for a ciphertext-only attack, the opponent, given ciphertext C, performs 𝑖 = 𝐷(𝐾𝑖, 𝐶) for all possible key values until a 𝑖 is produced that matches the form of acceptable plaintext.
- Then the MAC(Requirements: Message Authentication Codes) function should satisfy the following requirements.
- If an opponent observes M and 𝑀𝐴𝐶(𝐾, 𝑀), it should be computationally infeasible for the opponent to construct a message M’ such that 𝑀𝐴𝐶(𝐾, 𝑀) = 𝑀𝐴𝐶(𝐾, 𝑀′).
- 𝑀𝐴𝐶(𝐾, 𝑀) should be uniformly distributed in the sense that for randomly chosen messages, M and M’, the probability that 𝑀𝐴𝐶(𝐾, 𝑀) = 𝑀𝐴𝐶(𝐾, 𝑀′) is 2-n, where n is the number of bits in the tag.
Let M’ be equal to some known transformation on M. That is, 𝑀′ = 𝑓(𝑀). For example, f may involve inserting one or more specific bits. In that case, Pr[𝑀𝐴𝐶(𝐾, 𝑀) = 𝑀𝐴𝐶(𝐾, 𝑀′)] = 2−𝑛