Key Establishment - Understanding Cryptography - page 330

any of the other n 2 parties. This situation is shown for the case of a network with

n = 4 participants in Fig. 13.3.

−

Fig. 13.3 Keys in a network with n = 4users

We can extrapolate several features of this simple scheme for the case of n users:

Each user must store n − 1keys.

n 2

There is a total of n ( n − 1) ≈ keys in the network.

1) / 2 = 2 symmetric key pairs are in the network.

A total of n ( n −

If a new user joins the network, a secure channel must be established with every
other user in order to upload new keys.

The consequences of these observations are not very favorable if the number
of users increases. The first drawback is that the number of keys in the system is
roughly n 2 . Even for moderately sized networks, this number becomes quite large.
All these keys must be generated securely at one location, which is typically some
type of trusted authority. The other drawback, which is often more serious in prac-
tice, is that adding one new user to the system requires updating the keys at all
existing users. Since each update requires a secure channel, this is very burdensome.

Example 13.1. A mid-size company with 750 employees wants to set up secure e-
mail communication with symmetric keys. For this purpose, 750 × 749 / 2 = 280 , 875

symmetric key pairs must be generated, and 750 749 = 561 , 750 keys must be dis-

tributed via secure channels. Moreover, if employee number 751 joins the company,
all 750 other users must receive a key update. This means that 751 secure channels
(to the 750 existing employees and to the new one) must be established.

×

Obviously, this approach does not work for large networks. However, there are
many cases in practice where the number of users is (i) small and (ii) does not
change frequently. An example could be a company with a small number of branches
which all need to communicate with each other securely. Adding a new branch does
not happen too often, and if this happens it can be tolerated that one new key is
uploaded to any of the existing branches.