A message authentication code (MAC) is an authentication tag (also called a checksum) derived by application of an authentication scheme, together with a secret key, to a message. MACs are computed and verified with the same key so they can only be verified by the intended receiver, unlike digital signatures. MACs can be categorized as (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 that is 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 use a key or keys in conjunction with a hash function (see Question 94) to produce a checksum that is appended to the message. An example is the keyed-MD5 (see Question 99) method of message authentication [KR95b].
Lai, Rueppel, and Woolven [LRW92] proposed a MAC based on stream ciphers (see Question 86). 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 (see Question 89); the checksum is the final state of the two LFSRs.
MACs can also be derived from block ciphers (see Question 54). The DES-CBC MAC is a widely used US and international standard [NIS85]. The basic idea is to encrypt the message blocks using DES CBC (see Question 82) and output the final block in the ciphertext as the checksum. Bellare et al. give an analysis of the security of this MAC [BKR94].