A message authentication code (MAC) is an authentication tag (also called a checksum) derived by applying an authentication scheme, together with a secret key, to a message. Unlike digital signatures, MACs are computed and verified with the same key, so that they can only be verified by the intended recipient. There are four types of MACs: (1) unconditionally secure, (2) hash function-based, (3) stream cipher-based, or (4) block cipher-based.
- Simmons and Stinson [Sti95] proposed an unconditionally secure MAC based on encryption with a one-time pad. The ciphertext of the message authenticates itself, as nobody else has access to the one-time pad. However, there has to be some redundancy in the message. An unconditionally secure MAC can also be obtained by use of a one-time secret key.
- Hash function-based MACs (often called HMACs) use a key or keys in conjunction with a hash function (see Question 2.1.6) to produce a checksum that is appended to the message. An example is the keyed-MD5 (see Question 3.6.6) method of message authentication [KR95b].
- Lai, Rueppel, and Woolven [LRW92] proposed a MAC based on stream ciphers (see Question 2.1.5). In their algorithm, a provably secure stream cipher is used to split a message into two substreams and each substream is fed into a LFSR; the checksum is the final state of the two LFSRs.
- MACs can also be derived from block ciphers (see Question 2.1.4). The DES-CBC MAC is a widely used U.S. and international standard [NIS85]. The basic idea is to encrypt the message blocks using DES CBC and output the final block in the ciphertext as the checksum. Bellare et al. give an analysis of the security of this MAC [BKR94].