Cryptography: Theory and Practice:Authentication Codes | Modern Cryptography: Theory and Practice

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

Table of Contents

10.2 Computing Deception Probabilities

In this section, we look at the computation of deception probabilities. We begin with a small example of an authentication code.

Example 10.1

Suppose

and

For each and each , define

It will be useful to study the authentication matrix, which tabulates all the values e_ij(s). For each key and for each , place the authentication tag e_K(s) in row K and column s of a matrix M. The array M is presented in Figure 10.3.

Suppose that the key is chosen at random, i.e., for each . We do not specify the probability distribution since it turns out to be immaterial in this example.

Let’s first consider an impersonation attack. Oscar will pick a source state s, and attempt to guess the “correct” authentication tag. Denote by K₀ the actual key being used (which is unknown to Oscar). Oscar will succeed in deceiving Bob if he guesses the tag . However, for any and , it is easy to verify that there are exactly three (out of nine) authentication rules such that e_K(s) = a. (In other words, each symbol occurs three times in each column of the authentication matrix.) Hence, it follows that Pd₀ = 1/3.

Figure 10.3 An authentication matrix

Substitution is a bit more complicated to analyze. As a specific case, suppose Oscar observes the message (0, 0) in the channel. This does give Oscar some information about the key: he now knows that

Now suppose Oscar replaces the message (0, 0) with the message (1, 1). Then, he will succeed in his deception if and only if K₀ = (1, 0). The probability that K₀ is the key is 1/3, since the key is known to be in the set {(0, 0), (1, 0), (2, 0)}.

A similar analysis can be done for any substitution that Oscar might make. In general, if Oscar observes the message (s, a), and replaces it with any message (s′, a′) where s′ ≠ s, then he deceives Bob with probability 1/3. We can see this as follows. Observation of (s, a) restricts the key to one of three possibilities. Then, for each choice of (s′, a′), there is one key (out of the three possible keys) under which a′ is the authentication tag for s′.

Let’s now discuss how to compute the deception probabilities in general. First, we consider Pd₀. As above, let K₀ denote the key chosen by Alice and Bob. For and , define payoff (s, a) to be the probability that Bob will accept the message (s, a) as being authentic. It is not difficult to see that

That is, payoff (s, a) is computing by selecting the rows of the authentication matrix that have entry a in column s, and summing the probabilities of the corresponding keys.

In order to maximize his chance of success, Oscar will choose (s, a) such that payoff (s, a) is a maximum. Hence,

Note that Pd₀ does not depend on the probability distribution .

Pd₁ is more difficult to compute, and it may depend on the probability distribution . Let’s first consider the following problem: Suppose Oscar observes the message (s, a) in the channel. Oscar will substitute some (s′, a′) for (s, a), where s′ ≠ s. Hence, for , and , we define payoff (s′, a′; s, a) to be the probability that a substitution of (s, a) with (s′, a′) will succeed in deceiving Bob. Then we can compute the following:

The numerator of this fraction is found by selecting the rows of the authentication matrix that have the value a in column s and the value a′ in column s′, and summing the probabilities of the corresponding keys.

Since Oscar wants to maximize his chance of deceiving Bob, he will compute

The quantity p_s_,a denotes the probability that Oscar can deceive Bob with a substitution, given that (s, a) is the message observed in the channel.

Now, how do we compute the deception probability Pd₁? Evidently, we have to compute a weighted average of the quantities P_s_,a with respect to the probabilities of observing messages (s, a) in the channel. That is, we calculate Pd₁ to be

Figure 10.4 An authentication matrix

The probability distribution is as follows:

In Example 10.1,

for all s, a, so Pd₀ = 1/3. Also, it can be checked that

for all s, s′, a, a′, s ≠ s′. Hence, Pd₁ = 1/3 for any probability distribution . (In general, though, Pd₁ will depend on .)

Let’s look at the computation of Pd₀ and Pd₁ for a less “regular” example.

Table of Contents