Sebery J.Cryptography.An introduction to computer security.1989

8.2 Model of Authentication Systems	311
On the other hand, B may rst calculate the largest value in each column and
select the one with the smallest value. This choice guarantees that no matter

what A selects, B will never lose more than

min max gxy:		(8.2)
y	x
When the matrix of the game G is such that
max min gxy		= min max gxy = v;
x	y	y x

then the game has the point of equilibrium and the value v is the value of the game. A player who apply a pure strategy always decides on the single move (row/column).

Players may choose moves in more complex ways using so-called mixed strategies. This time players attach probabilities (or weights) to each their moves and select the current move probabilistically. Assume that the strategy of A is de-

termined by the probability distribution = f x1 ; : : : ; xn1 g and the strategy

of Y { by = f y1 ; : : : ; yn2 g, where xi = P (xi) and yj = P (yj). It is easy to get an expression for the expected gain/loss

payo =	2X X		x ygxy	(8.3)
	x	y2Y

when the players A and B apply their strategies and , respectively. Denote

v1 = max min payo

and

v2 = min max payo :

The fundamental theorem of rectangular games says that if v1 = v2, then there are two mixed optimal strategies and such that

v = payo = v1 = v2:

The value v is called the value of the game and the two strategies ( , ) are the saddle point of the game.

8.2.2 Impersonation Game

An authentication system can be looked at as a game between two players. Therst player consists of two communicants Alice and Bob. The second player is Oscar. Alice and Bob can select encoding rules to minimize Bob's chances for

312 8 AUTHENTICATION

EnM		m1	m2	m3	m4
e1		1	0	1	0
e2		0	1	1	0
e3		1	0	0	1
e4		0	1	0	1

Table 8.2. Incidence matrix

deception. On the other hand, Oscar can choose cryptograms according to a strategy which maximizes his chances for a successful deception of Bob. The communicants' strategy for the selection of encoding rules is determined by the probability distribution = f e j e 2 Eg where e is the probability that Alice and Bob choose the encoding rule e (the row of the authentication matrix).

Obviously, Pe2E e = 1. Oscar's strategy is described by the probability distribution = f m j m 2 Mg where m is the probability that Oscar selects cryptogram m (where Pm2M m = 1).

After both the communicants and opponent have made their choices about the encoding rule e and the fraudulent cryptogram m = (s; t), Oscar wins only if the tag t0 in the row e and the column s of the authentication matrix B is equal to t. While considering the game model of authentication, it is convenient to de ne the so-called incidence matrix: An incidence matrix is a binary matrix A = [aem] (aem 2 f0;1g) with E rows and M columns (e 2 E and m 2 M). The entry aem = 1 only if the cryptogram m is valid under the encoding rule e. Otherwise, the entry is zero.

For example, the incidence matrix of the authentication system illustrated in Table 8.1 is given in Table 8.2. Clearly, knowing the authentication matrix it is easy to construct the corresponding incidence matrix and vice versa.

Consider the impersonation attack where Oscar knows the A-code, i.e. the incidence matrix. After the communicants (Alice and Bob) agree on their strategy , it is possible to compute the conditional probability of Oscar's success provided he has chosen the fraudulent cryptogram m so

payo (m) =		X	eaem:	(8.4)
		e2E
The probability of Oscar's success never exceeds the values
p0 = max	X	mpayo (m):
m2M

f e1 ; e2 ; e3 ; e4 g equal to:

8.2 Model of Authentication Systems

313

Therefore, the optimal strategy for Alice and Bob should minimize p0 that is

p	= min(max	X	mpayo (m))
0
		m2M

= min(max	X X	e maem):
	m2M e2E

Similarly, Oscar can compute the conditional probability of his success provided the communicants have selected the encoding rule e 2 E which is

payo (e) =				maem:
			m2M
			X
The probability never drops below the value
p = min		X	epayo (e):
o	e2E

The optimal strategy for Oscar should maximize po so

p	= max(min		X	epayo (e))
0
			e2E

= max(min	X X	e maem):
	m2M e2E

Note that A = [aem] is the incidence matrix of the game. According to the

fundamental theorem of rectangular games if there is the saddle point of the game then p0 = p0 = p0 = p0 .

An A-code is perfect under the impersonation if the value p0 of the impersonation game is independent of Oscar's strategy .

Theorem 33. (Simmons [472, 473]) An A-code is perfect under the impersonation if and only if there is a communicants' strategy such that

p0 = payo (m) = MS = T1

Consider the A-code given by Table 8.1. Assume that the strategy = = f1=2; 1=4; 1=8;1=8g. The conditional probabilities are

payo (m1) = 1=2 + 1=8 = 5=8 payo (m2) = 1=4 + 1=8 = 3=8 payo (m3) = 1=2 + 1=4 = 3=4 payo (m4) = 1=8 + 1=8 = 1=4

314 8 AUTHENTICATION

The probability of success for Oscar is at most 5=8. If the communicants use another strategy, say = f1=4; 1=4; 1=4; 1=4g, then all conditional probabilities payo (mi) = 1=2 for i = 1; 2; 3; 4. Note that the strategy is optimal as the payo does not depend on the Oscar's strategy.

8.2.3 Substitution Game

In the substitution attack, Oscar knows the A-code and a single valid cryptogram m. He tries to deceive Bob by sending him a fraudulent cryptogram m0. The probability of Oscar's success called payo is:

	payo (m; m0) = P (m0		valid m received)
	=	P (m0	valid, jm received)	(8.5)
		P (m received)

For simplicity, denote that P (m) = P(m received). This probability can be computed as follows:

P (m) =	X	P(m; e)
	e2E
Some pairs (m; e) never					happen. This can be			conveniently		expressed using
the entries of the incidence matrix so P (m) =								P	e2E aemP (m; e). Note that
			j			j				j
P (m; e) = P(e)P(m				e) = eP (m			e). The probability P (m				e) is equal to

the probability PS(s) that the message source has generated a message s such

j	P
that m = (s; e(s)). Therefore P(m) =		e2E aem ePS(m; e). The probability

P (m e) = PS(m; e) as the pair (m; e) uniquely determines the message s. The probability P (m0 valid; m received ) can be transformed in similar way

and:

P (m0 valid, m received ) = X P(m0 valid; m received ; e) =

e2E

= X eP (m0 valid; m received j e)

e2E

= X eaemaem0PS (m; e)

e2E

Finally, we get

payo (m; m0) = Pe2E eaemaem0 PS(m j e) (8.6)

P (m)

8.2 Model of Authentication Systems

315

After interception of cryptogram m, Oscar can choose a fraudulent cryp-

togram m0 from (M 1) possibilities. His choice can be described in the form
of an assignment z : M ! M. The assignment can be represented as
intercepted cryptogram		fraudulent cryptogram
m1	!	m0	(m0 = m1)
.		1	1.	6
.			.
.			.
mM	!	m0 (m0		= mM )
		M	M	6
or, brie y, z(m) = m0. There are (M	1)M possible assignments. Let the set
Z = fzi j i = 1; : : : ; (M 1)M g contain all assignments Oscar may ever apply.
Obviously, he will have some preferences for some assignments. His strategy
(preferences) is determined by the probability distribution
= f z j z 2 Zg				(8.7)

where z is the probability that Oscar chooses z as his substitution assignment

(note that			z2Z z = 1). The probability of Oscar's success when he uses the
assignment z					is
		P2 Z
p1 (z) =				P (m) payo (m; m0)					(8.8)
		m2M
where m0		X
	= z(m). The probability of Oscar's success when he applies the strat-
egy is:
p1 =			zp1 (z) = z					P (m) payo (m; m0)	(8.9)
	z2Z					z2Z	m2M
	X					X	X

Substituting payo by equation (8.6), we obtain:

p =

X X X

a

em

a0

0P

S

(m; e) =

X X

e

X

a

a

em

0 P (m; e)

1

z e

em

z

em

S

z2Z m2M e2E

z2Z e2E

m2M

P

Note that g(e; z) =

m2M aemaem0PS (m; e) are entries of the game matrix G

with E rows and (M

1)M columns, where m0 = z(m) and A = [aem] is the

incidence matrix of the A-code. Thus the optimal strategy for Oscar would besuch that

p1 = max(min		X X	e zg(e; z)):	(8.10)
		e2E z2Z
On the other hand the optimal Alice and Bob's strategy would be and
p1 = min(max		X X	e zg(e; z)):	(8.11)
		e2E z2Z

316 8 AUTHENTICATION

If p1 = p1 , then the fundamental theorem of rectangular games assures the existence of two optimal strategies for the players (the saddle point). The value of the game for these two strategies is p1 = p1 = p1 . The value p1 expresses also the probability of substitution by Oscar.

An authentication code is perfect for the substitution attack if the value of the substitution game for the optimal communicants' strategy does not depend on Oscar's strategy. The next theorem characterizes perfect A-codes.

Theorem 34. (Massey [320]) An A-code is perfect under substitution if and

only if there is a communicants' strategy				such that payo (m; m0) is con-
			2 M2. The
stant for every pair (m; m0)				value of the substitution game is
p	1	= payo (m; m0).

As we deal with authentication without secrecy, the requirement that m 6= m0 translates to s 6= s0 where m = (s; t) and m0 = (s0; t0). It is not diÆcult to observe that if the payo function is constant for every pair s 6= s0, all tags are equally probable and p1 = T 1.

8.2.4 Spoo ng Game

The substitution game can be generalized to a spoo ng game. In the spoo ng game, the communicants, Alice and Bob, play against the opponent Oscar. Oscar knows the A-code applied and sees r di erent valid cryptograms sent over the channel. He chooses a fraudulent cryptogram m0 (the cryptogram has to be di erent from all cryptograms observed) and tries to deceive Bob so he will accept m0 as the valid cryptogram. The spoo ng game can be analyzed in similar way to the analysis of the substitution game. If the spoo ng game has a saddle point, then the value of the game denoted by pr is determined by the following theorem.

Theorem 35. If the spoo ng game is de ned by an A-code, then

1
pr T	:	(8.12)

The equality holds if and only if for any sequence of r observed cryptograms (mr 2 Mr) and any fraudulent cryptogram m0 (m0 is di erent from the observed cryptograms)

payo (mr; m0) =	1	:	(8.13)
	T

8.3 Information Theoretic Bounds

317

An A-code is r-fold secure against spoo ng if the game values for impersonation, substitution, and all spoo ng games are

pi = T1

where i = 0; 1; : : : ; r. Recall that game values are equivalent to the probability of deception or Oscar's success.

8.3 Information Theoretic Bounds

Bounds for probabilities pi (i = 0;1; : : : ; r) can be derived using entropies. Let H(E) = Pe2E P (e) log2 P (e) is the entropy of the random variable with the probability distribution fP (e) j e 2 Eg over the set E. Similarly, H(M) and H(S) are entropies of cryptograms and messages, respectively.

Simmons [472] proved that the impersonation probability

p0	2 (H(E) H(EjM)):	(8.14)
This bound was re ned by Johansson and Sgarro in [262] and
p0	2 inf(H(E) H(EjM))	(8.15)

where inf stands for in mum that is the greatest lower bound. The in mum is taken over all source statistics that do not change the set of pairs (m; e) for

which P (m; e) 6= 0.

In 1974 Gilbert, MacWilliams, and Sloane [201] considered a general class of A-codes without secrecy and proved that the probability of substitution

p1 E 1=2:

(8.16)

Now we are going to generalize the bound (8.16) for the case of spoo ng of order r. To simplify our considerations we assume that

1.	The message source generates source states with the uniform probability,
	i.e. P(s) = 1=S for s 2 S.
2.	Oscar selects the fraudulent cryptogram m0 that maximizes the probability
	P (m0 is valid j mr). The average probability pr of Oscar's success is:
	pr =	X	P (mr) max P (m0 is valid	j	mr)
		mr2Mr	m0

H(E) H(E; Mr j Sr):

318 8 AUTHENTICATION

First, we observe that

H(M0jMr)
pr 2		(8.17)
where H(M0	j Mr) is the conditional entropy of that the fraudulent cryptogram
is valid provided r cryptograms have been seen. This follows from the de nition

of the conditional entropy and properties of the logarithm:
H(M0	j	Mr) =		X		X	P (m0 is valid; mr) log2	P(m0 is valid	j	mr)
				r	2M	r 0
				m		m 2M

X

X

P (m0 is valid; mr) log

2

max P(m0

is valid

j

mr)

r

2M

r

0

m0

m

m 2M

log2

P (m0

is valid; mr ) max P(m0

is valid

j

mr)

mr2Mr m02M

m0

=

log2 prX X

This sequence produces the requested inequality (8.17).

Second, we will show that:

H(M0 j Mr)

H(E)

r + 1

Note that H(E) H(E j

Sr). As the pair, message and encoding rule, assigns

the unique cryptogram so H(E j Sr) = H(E; Mr j Sr) so

Using the properties of the entropy, we obtain:

H(E; Mr j Sr) = H(Mr j Sr) + H(E j Mr; Sr)

The knowledge of r cryptograms is suÆcient to determine the corresponding r messages so H(E j Mr; Sr) = H(E j Mr) and H(E j Mr) H(E) H(Mr j Sr). Clearly,

H(M0 j Mr) H(E j Mr)

as the uncertainty of encoding rules must be equal or bigger than the uncertainty associated with the decision about the fraudulent cryptogram. In other words, if the encoding rule is known so is the valid cryptogram. This means that:

H(M0 j Mr) H(E j Mr) H(E) H(Mr j Sr)	(8.18)
The messages are independently and uniformly selected from the set S so
H(Mr j Sr) = rH(M j S):	(8.19)

There are two possible cases:

8.4 Constructions of A-codes

319

H(E)
1. H(M j S) r+1 , then according to (8.18) and (8.19) we get:
H(M0 j Mr)	H(E)				(8.20)
		r + 1
H(E)		, then H(M0	j Mr) = H(M0 j Mr; S) H(M j S)
2. H(M j S) r+1
H(E) . Note that H(M0 Mr; S)				H(M S) holds as the knowledge of r
r+1		j		j
cryptograms never increases the entropy of M0. This gives the nal bound
for pr and
H(E)
pr 2 r+1 :					(8.21)

If the inequality (8.21) becomes equality, then

{E = 2H(E) and all encoding rules are equally probable.

{Probabilities of deception p0 = p1 = : : : = pr = T1 .

More details about entropy bounds for spoo ng can be found in [166, 434, 445].

8.4 Constructions of A-codes

Gilbert, MacWilliams, and Sloane [201] demonstrated that A-codes can be constructed using combinatorial designs. Projective spaces are combinatorial objects which may be used to construct A-codes. Also orthogonal arrays and error correcting codes provide tools for the design of A-codes.

8.4.1 A-codes in Projective Spaces

An n-dimensional projective space P G(n; q) over Galois eld GF (q) is a collection of points, lines, planes, and subspaces P G(i; q) (i < n) such that

1. The number of all points in the space P G(n; q) is (n) = qn+1 1		= qn +
qn 1	q 1
	+ : : : + q + 1.

2.Each subset of (n r) linearly independent equations constitutes a projective subspace P G(r; q). The number of all di erent subspaces of dimension r contained in P G(n; q) is

	(r; n) =	(n) (n	1) (n r)	:
		(r) (r 1)	(2) (1) (0)

The implementation of hS; M; Ei A-code using the projective space P G(N; q) applies the following assignments:

320 8 AUTHENTICATION

M		s1			s2			s3			s4
EnS	m1		m2	m3		m4	m5		m6	m7		m8
e1	1		0	1		0	1		0	1		0
e2	0		1	1		0	1		0	0		1
e3	1		0	0		1	1		0	0		1
e4	0		1	0		1	1		0	1		0
e5	1		0	1		0	0		1	0		1
e6	0		1	1		0	0		1	1		0
e7	1		0	0		1	0		1	1		0
e8	0		1	0		1	0		1	0		1

Table 8.3. The incidence matrix of an A-code designed in P G(3; 2)

{Messages s 2 S are projective subspaces P G(N 2; q) of P G(N; q). Note that the message spaces are chosen so the intersection of any two arbitrary message

spaces is a projective space P G(N 3; q) and in general the intersection of every ` message spaces creates a projective space P G(N (` + 1); q).

{Encoding rules e 2 E are points.

{Cryptograms m 2 M are projective spaces P G(N 1; q) spanned over the corresponding message space containing the point corresponding to the en-

coding rule.

The properties of the implementation are:

{The number of encoding rules E = qN .

{The number of tags is T = q,

{N di erent pairs (message, cryptogram) uniquely determine the encoding rule applied and break the A-code.

{Probabilities of deception are p0 = p1 = : : : = pr = q 1 for r = 1; 2; : : : ; N 1.

The projective space P G(3; 2) can be used to construct a simple A-code with four messages, eight cryptograms, and two tags whose incidence matrix is given in Table 8.3. If Oscar sees the cryptogram m4, he knows that the encoding rule e 2 fe3; e4; e7; e8g. If he wants to send a fraudulent cryptogram for s4, he has to choose either m7 or m8. Both cryptograms are equally probable. If Oscar observes the second cryptogram m5, he knows that the encoding rule is in the set e 2 fe3; e4g. This observation does not help him in deciding what is the cryptogram for s4. He still has two equally probable candidates. Any