Cryptography: Theory and Practice:Authentication Codes

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

10.1 Introduction

We have spent a considerable amount of time studying cryptosystems, which are used to obtain secrecy. An authentication code provides a method of ensuring the integrity of a message, i.e., that the message has not been tampered with and that it originated with the presumed transmitter. Our goal is to achieve this authentication capability even in the presence of an active opponent, Oscar, who can observe messages in the channel and introduce messages of his own choosing into the channel. This goal is accomplished in the “private-key” setting whereby Alice and Bob share a secret key, K, before any message is transmitted.

In this chapter, we study codes that provide authentication but no secrecy. In such a code, a key is used to compute an authentication tag which will enable Bob to check the authenticity of the message he receives. Another application of an authentication code is verify that data in a large file has not been tampered with. An authentication tag would be stored with the data; the key used to generate and verify the authenticator would be stored separately, in a “secure” area.

We should also point out that, in many respects, an authentication code is similar to a signature scheme or to a message authentication code (MAC). The main differences are as follows: The security of an authentication code is unconditional, whereas signature schemes and MACs are studied from the point of view of computational security. Also, when an authentication code (or a MAC) is used, a message can be verified only by the intended receiver. In comparison, anyone can verify a signature using a public verification algorithm.

We now give a formal definition of the terminology we use in the study of authentication codes.

DEFINITION 10.1 An authentication code is a four-tuple , where the following conditions are satisfied:

1. is a finite set of possible source states

Figure 10.1 Impersonation by Oscar

2. is a finite set of possible authentication tags

3. , the keyspace, is a finite set of possible keys.

4. For each , there is an authentication rule .

The message set is defined to be .

REMARK Note that a source state is analogous to a plaintext. A message consists of a plaintext with an appended authentication tag; it could be more precisely referred to as a signed message. Also, an authentication rule need not be an injective function.

In order to transmit a (signed) message, Alice and Bob follow the following protocol. First, they jointly choose a random key . This is done in secret, as in a private-key cryptosystem. At a later time, suppose that Alice wants to communicate a source state to Bob over an insecure channel. Alice computes a = e_K(s) and sends the message (s, a) to Bob. When Bob receives (s, a), he computes a′ = e_K(s). If a′ = a, then he accepts the message as authentic; otherwise, he rejects it.

We will study two different types of attacks that Oscar might carry out. In both of these attacks, Oscar is an “intruder-in-the-middle.” These attacks described are as follows:

Impersonation: Oscar introduces a message (s, a) into the channel, hoping to have it accepted as authentic by Bob. This is depicted in Figure 10.1.
Substitution: Oscar observes a message (s, a) in the channel, and then changes it to (s′, a′), where s′ ≠ s, again hoping to have it accepted as authentic by Bob. Hence, he is hoping to mislead Bob as to the source state. This is depicted in Figure 10.2.

Associated with each of these attacks is a deception probability, which represents the probability that Oscar will successfully deceive Bob, if he (Oscar) follows an optimal strategy. These probabilities are denoted by Pd₀ (impersonation) and Pd₁ (substitution). In order to compute Pd₀ and Pd₁, we need to specify probability distributions on and . These will be denoted by and , respectively. We assume that the authentication code and these two probability distributions are known to Oscar. The only information that Alice and Bob possess that is not known to Oscar is the value of the key, K. This is analogous to the way that we studied the unconditional security of private-key cryptosystems.

Figure 10.2 Substitution by Oscar

Table of Contents

Chapter 10Authentication Codes

10.1 Introduction

Chapter 10
Authentication Codes