Chapter 7Message AuthenticationIn most people’s minds, privacy is the goal most strongly associated to cryptography. But messageauthentication is arguably even more important. Indeed you m ay or may not care if some particularmessage you send out stays private, but you almost certainly do want to be sure of the originatorof each message that you act on. Message authentication is what buys you that guarantee.Message authentication allows one party—the sender—to send a message to another party—the receiver—in such a way that if the message is modified en route, then the receiver will almostcertainly detect this. Message authentication is also called data-origin authentication. Messageauthentication is said to protect the integrity of a message, ensuring that each message that it isreceived and deemed acceptable is arriving in the same condition that it was sent out—with nobits inserted, missing, or modified.Here we’ll be looking at the shared-key setting for message authentication (remember thatmessage authentication in the public-key setting is the problem addressed by digital signatures). Inthis case the sender and the receiver share a secret key, K, which they’ll use to authenticate theirtransmissions. We’ll define the message authentication goal and we’ll describe some different waysto achieve it. As usual, we’ll be careful to pin down the problem we’re working to solve.7.1 The settingIt is often crucial for an agent who receives a message to be sure who s ent it. If a hacker cancall into h is bank’s central computer and p roduce deposit transactions that appears to be comingfrom a branch office, easy wealth is just around the corner. If an unp rivileged user can interactover the network with his company’s mainframe in su ch a way that the machine thinks that thepackets it is receiving are coming from the system administrator, then all the machine’s access-control mechanisms are for naught. In such cases the risk is that an adversary A, the forger, willcreate messages that look like they come from some other party, S, the (legitimate) sender. Theattacker will send a message M to R, the receiver (or ve rifier ), under S’s identity. The receiverR w ill be tricked into believing th at M originates with S. Because of this wrong belief, R mayinappropriately act on M.The r ightful sender S could be one of many different kinds of entities, like a person, a corpora-tion, a network address, or a particular p rocess running on a particular machine. As the receiver R,you might know that it is S that supposedly sent you the m essage M for a variety of reasons. For2 MESSAGE AUTHENTICATIONMCSenderAKKC’E DReceiverM’ orFigure 7.1: An authenticated-encryption scheme. Here we are authenticating messages with wh atis, syntactically, just an encryption scheme. The sender transmits a transformed version C of Mand the receiver is able to r ecover M′= M or else obtain indication of failure. Adversary A controlsthe communication channel and may even influen ce messages sent by the sender.example, the message M might be tagged by an identifier which somehow names S. Or it mightbe that the manner in which M arrives is a route dedicated to servicing traffic from S.Here we’re going to be looking at the case when S and R already share some secret key, K.How S and R came to get this s hared secret key is a separate question, one that we deal with later.There are several high-level approaches for authenticating transmissions.1. The most general approach works like this. To authenticate a message M using the key K,the sender will apply some encryption algorithm E to K, giving rise to a ciphertext C. Whenwe speak of encrypting M in this context, we are using the word in the broadest possiblesense, as any sort of keyed transf ormation on the message that obeys are earlier defi nition forthe syntax of an encryption scheme; in particular, we are not suggesting that C conceals M.The sender S will transmit C to the receiver R. Maybe the receiver will receive C, or maybeit will not. The prob lem is that an adversary A may control the channel on which messagesare being sent. Let C′be the message that the receiver actually gets. The receiver R, onreceipt of C′, will apply some d ecryp tion algorithm D to K and C′. We want that thisshould yield one of two things: (1) a message M′that is the original message M; or (2) anindication ⊥ that C′be regarded as inauthentic. Viewed in this way, message authenticationis accomplished by an encryption scheme. We are no longer interested in the privacy ofthe encryption scheme but, functionally, it is still an encryption scheme. See Fig. 7.1. Wesometimes use the term authenticated encryption to indicate th at we are using an en cryptionscheme to achieve authenticity.2. Since our authenticity goal is not abou t privacy, most often the ciphertext C that the sendertransmits is simply the original message M together with a tag T ; that is, C = hM, T i.When the ciphertext is of this form, we call the mechanism a message-authentication scheme.A message-authentication scheme will be specified by a tag-generation algorithm TG anda tag-verification algorithm VF. The f ormer may be probabilistic or stateful; the latter isneither. Th e tag-generation algorithm TG produces a tag T$← TGK(M) f rom a key K andthe message. The tag-verification algorithm VF ← VFK(M′, T′) produces a bit from a keyK, a message M′, and a tag T′. The intent is that th e bit 1 tells the receiver to accept M′,while the bit 0 tells the receiver to reject M′. See Fig. 7.5Bellare and Rogaway 3MMTSenderM’AKKM’T’TG VF 0 or 1ReceiverFigure 7.2: A message authentication scheme. This is a special case of the more general frameworkfrom the prior diagram. The authenticated message C is now understo od to be the original messageM together with a tag T . Separate algorithms generate the tag and verify the pair.MMTSenderM’AKKM’T’MAC MAC0 or 1Receiver=T *Figure 7.3: A message authentication code. This is a special case of a message authenticationscheme. The authenticated message C is now understood to be the original message M togetherwith a tag T that is computed as a deterministic and stateless function of M and K. The receiververifi es the authenticity of messages using the same MACing algorithm.3. The