Message Authentication - Introduction to Cryptography with Maple - page 230

bit of this byte is flipped, bd is changed to b9 and the dollar amount is changed to
$5000. When doing these changes, the adversary does not know whether the number
will be increased or decreased but the example clearly shows that a highly secure
encryption scheme like OTP does not provide authenticity or integrity.

Observe also that, even without any knowledge about the message, a small random
change to the ciphertext in the previous example would produce a plaintext different
from the one originally sent and hence would violate the authenticity and integrity
of the message. Expanding on this idea, we mention another basic reason why all
the encryption schemes seen so far fail to provide authenticity. It is the fact that they
allow spoofing attacks in which an adversary may masquerade as a legitimate user
just by sending an arbitrary ciphertext and exploiting the fact that the ciphertext in
question will give, when decrypted with the secret key, a valid plaintext. The plaintext
may, and very likely will, be meaningless but even so this kind of attack is disturbing
and should be prevented.
The conclusion is that authentication requires different techniques than encryption
and, because of the problems mentioned, it is generally admitted that the best practice
is, inmost situations, to use encryption and authentication together and not encryption
alone.

5.2 Message Authentication Codes

We are going to introduce a class of cryptographic schemes called Message Authenti-
cation Codes (or MACs, for short) that will prevent an adversary from impersonating
a legitimate user and frommodifying a message without the legitimate users noticing
it. MACs are used in the private-key setting and, similarly to symmetric encryption
schemes, require parties to share a secret key.

5.2.1 Defining MACs

Before giving the formal definition, we informally explain the idea of how a MAC
is used. Two users (often called the sender and the receiver) share a secret key k
and want to communicate in an authenticated way. Concretely, the sender wants to
send a message m to the receiver and for this she does the following. She uses a tag
generation algorithm , that we shall denote by Mac , to compute a MAC tag t ,using m
and k as inputs. Then, she sends the pair ,

the receiver verifies that t is a valid tag for m by running a verification algorithm Ve r
that takes as input m , k , and t and shows whether t is a valid tag for m .

( m , t ) to the receiver. After receiving ( m , t )