Key-Distribution Protocols and Conference Key Agreement

The following types of key-distribution protocols are distinguished:

— protocols for transporting (already generated) keys;

— protocols for the (joint) generation of a shared key (public key distribution);

— schemes for the pre-distribution of keys.

A further distinction is made between key-distribution protocols for individual participants and between groups of participants in an information exchange.

1. Key transport using symmetric encryption

There are protocols in which the parties carry out key transport through direct interaction, that is, two-party protocols or, in other words, protocols of the "point-to-point" type, and protocols with centralized key distribution, in which a third party is provided for, playing the role of a trusted center.

Two-party protocols.

A distinction is made between protocols in which the parties already possess in advance some secret information known to both of them, and protocols that do not require this condition.

Let parties A and B already share some common secret information in advance. Suppose that this — is a secret key k_AB.

Then, to transport the key k the parties can use one-way transmission:

A→B: E_kAB(k,t,B),

where E — is the encryption algorithm, t — is the timestamp, B — is the identifier of user B (for brevity, instead of id(B) we will use just the single symbol B).

If the timestamp is not transmitted, an attacker can replay the same message. If the identifier of the addressee is not specified, an attacker can return the intercepted message to the sender, which in some situations can be dangerous, since user A will not be able to establish that this message was not received from user B.

In the protocol given above, instead of encryption one could use a keyed hash function depending on the shared key:

A→B: k  h_kAB(t,B).

If session authentication is additionally required, the following "challenge-response" type protocol can be used:

1. B→A:r_B,

2. A→B:E_kAB(k,r_B,B),

where r_B — is a random number generated by user B and transmitted to user A at the start of the session. When using a hash function, a similar protocol can look like this:

1. B→A: r_B,

2. A→B: k  h_kAB(r_B,B).

If mutual authentication is required, the last protocol can be modified by giving party A the ability, through generating its own random number r_A and inserting it into the message at step 2 of the protocol, to make sure that it is indeed dealing with user B.

The original protocol can be modified so that the sought-after key k is not generated by one side alone, but is the result of a two-way exchange.

Let users A and B , besides the random numbers r_A and r_B , also generate random numbers k_A and k_B respectively. Then, as a result of executing the protocol

1. B→A:r_B,

2. A→B:E_kAB(k_A,r_A,r_B,B),

3. B→A:E_kAB(k_B,r_B,r_A,A),

each of the parties can compute the shared key using some function f according to the rule k = f(k_A,k_B). In this protocol, neither party can know the value of the key in advance.

Let us now present the "keyless" protocol of A. Shamir, which allows a key to be transported without using any shared secret information.

Suppose there is some commutative encrypting transformation E. This means that for all messages x and keys k₁ and k₂ the following equality holds

Then users A and B can implement the following three-step protocol for transporting the secret key k from A to B:

1. A→B: E_kA(k),

2. B→A: E_kB(E_kA(k)),

3. A→B: D_kA(E_kB(E_kA(k))).

In this protocol, not every commutative transformation E. can be used. For example, it is easy to see that for the transformation E_k (k) = k  the protocol turns out to be clearly insecure. Therefore, in Shamir’s protocol it is recommended to use a transformation of the form E_kA(k) = k^a mod p, in which the constant a is determined by the key k_a.

Three-party protocols.

Let us consider key-distribution protocols between pairs of participants using a third party T, called the center. This role is usually played by some dedicated network node, or server, which all participants trust. The center T stores the keys of all users on the network. Hence the scheme of key relationships is graphically represented as a star.

One of the first protocols of this type consists of performing the following steps:

1. A→T: A,B,r_A,

2. T→A: E_kAT(r_A,B,k,E_kBT(k,A)),

3. A→B: E_kBT(k,A),

4. B→A: E_k(r_B),

5. A→B: E_k(r_B - 1).

As a result of executing the first three steps of the protocol, users A and B obtain from the center T a generated shared key k for organizing their interaction. The fourth and fifth steps are intended for authenticating user A and confirming that the key was received correctly by both parties.

The weakness of this protocol lies in the possibility of replaying to user B the message transmitted at step 3. In this case, user B has no way to establish that the received key k has already been used. Therefore, if this key is compromised, an attacker can authenticate and transmit messages on behalf of A.

This shortcoming is eliminated in the Kerberos protocol. Let us first consider the basic protocol used in the Kerberos authentication and key-distribution protocol. It consists of the following steps:

1. A→T: A,B,r_A,

2. T→A: E_kBT (k, r_A ,L,B), ticket,

3. A→B: ticket, authenticator,

4. B→A: E_k(t,k_B).

Here "the ticket" is the name given to the quantity E_kBT(k,A,L), "authenticator" — is the quantity E_k(A,t,k_A), t — is the timestamp; L — is the validity period of the ticket, r_A — is a random number generated by user A and inserted into the transmitted message for mutual authentication, while k_A and k_B — are random numbers generated by users A and B respectively, and used either as the key for encrypting information to the other party, or for generating the shared key k_AB = f(k_A,k_B) using some function f.

In the full Kerberos protocol, the basic protocol described above is used twice. This is because two servers are provided for. The first is the "authentication server", denoted AS, which issues so-called "ticket-granting tickets" (tgt), containing keys intended for long-term use. The second server, TGS, — the "ticket-issuing server", issues ordinary tickets for accessing network resources and communicating with other users.

Fig. 36. The Kerberos protocol

The messages transmitted under this protocol look as follows:

1. A→AS: A,TGS,r_A, ,

2. AS→A: E_kA,AS(k_A,TGS,r_A,L₁,TGS), tgt,

3. A→TGS: tgt, authenticator₁, B, r_A’,

4. TGS→ A: E_kA,TGS(k,r_A’,L₂,B), ticket,

5. A→B: ticket, authenticator₂,

6. B→A: E_k(t₂,k_B),

where

tgt = E_kAS,TGS(k_A,TGS, A, L₁),

authenticator₁ = E_kA,TGS(A,t₁),

ticket = E_kB,TGS(k, A,L₂),

authenticator₂ = E_k (A, t₂, k_A ) .

Thanks to the introduction of the second server, the load on the first server is reduced many times over. The first server must be the most protected, since it stores the master keys of all users. There can be several servers of the second type, and they can correspond to a particular subnet or a particular type of resource.

Let us present one more key-distribution protocol using a server, preferable for the case when the server is located in a more convenient position for the second user. The protocol consists of performing the following actions:

1. A→B: r,A,B,E_kAT(r_A,r,A,B),

2. B →T: r, A,B,E_kAT (r_A,r, A,B),E_kBT(r_B,r, A,B),

3. T→B: E_kAT(r_A,k),E_kBT(r_B,k),

4. B→A: E_kAT(r_A,k).

User A generates two random numbers: the first (r_A) is used, as before, for mutual authentication, and the second (r) — for authenticating the communication session (a timestamp may be used instead of it).

This protocol can be supplemented with one more step to provide mutual authentication of the parties and confirmation of the correctness of the received key:

4^’. B→A: E_kAT (r_A,k),E_k(r,r_B),

5. A→B: E_k(r).

2. Key transport using asymmetric encryption

Let us consider variants of using asymmetric encryption for transporting the secret keys of symmetric cryptosystems.

Protocols without the use of a digital signature.

To transport the key k the following one-step protocol can be used:

A→B: E_kB(k,t,A),

where E — is the public-key encryption algorithm, t — is the timestamp, inserted to prevent the possibility of key reuse.

To carry out mutual authentication and confirm that the key was received correctly, the protocol from [Nee78] can be used:

1. A→B: E_B(k₁,A),

2. B→A: E_A(k₁,k₂),

3. A→B: E_B(k₂).

By decrypting the received messages at the second and third steps, the parties make sure that they are indeed dealing with the correct party and that the other party has correctly decrypted the received key value.

Protocols using a digital signature.

When a digital signature is used, an authenticated key-transport protocol can consist of only a single message and take, for example, one of the following three forms:

A→B: E_B(k,t,S_A(B,k,t))

(encryption of the signed key);

A→B: E_B(k,t,),S_A(B,k,t)

(encryption and signing of the key);

A→B: t,E_B(A,k),S_A(B,t,E_B(A,k))

(signature of the encrypted key).

Public key certificates

As a rule, when public keys are used, what is stored is not the keys themselves but their certificates. A certificate is a set of data

C_A=(A,k_A,t,S_kTA(A,k_A,t)),

consisting of the identifier of user A, its public key k_A and, possibly, some other additional information, for example, the time t the certificate was issued and its period of validity, certified by the digital signature of the trusted center TA or of a trustworthy person. A certificate is intended to eliminate the possibility of substituting the public key while it is being stored or transmitted.

Having received such a certificate and verified the digital signature, one can make sure that the public key indeed belongs to the given user.

The international standard CCITT X.509 defines the following authentication protocol with simultaneous key distribution:

1. A→B:C_a,D_a,S_a(D_a),

2. B→A: C_B,D_B,S_B(D_B),

3. A→B:r_B,B,S_A(r_B,B),

where C_A and C_B — are the certificates of the parties, S_A and S_B — are the digital signatures of the parties,

D_A = (t_A ,r_A,B, data₁, E_B (k₁)),

D_B = (t_B, r_B, A,r_A, data₂,E_A (k₂))

- are the sets of transmitted and signed data. Additional information for authenticating the source is placed in the data fields. The third step of the protocol is required by party B to confirm that it is indeed interacting with party A.

3. Public key distribution

Public key distribution allows two users to work out a shared secret key through dynamic interaction based on exchanging public messages, without any shared secret information distributed in advance. An important advantage of public distribution is also that none of the users can determine the value of the key in advance, since the key depends on the messages transmitted during the exchange.

The first public-key distribution algorithm was proposed by W. Diffie and M. Hellman. To carry it out, the parties must agree on the values of a large prime number p and a generating element α of the multiplicative group . To generate the shared key k they must generate random numbers x, 1≤ x ≤ p - 2, and y, 1 ≤ y ≤ p - 1, respectively. They must then exchange messages in accordance with the protocol:

1. A→B: α ^x mod p,

2. B→A: α ^y mod p.

The desired shared key is now computed by the formula:

k = (α ^y)^x = (α ^x)^y mod p.

A drawback of this protocol is the possibility of a "man-in-the-middle" attack, which consists of the following. Suppose that an attacker has the ability to substitute messages transmitted by the users.

Let us consider two protocols that eliminate this drawback. The first protocol, called STS (station-to-station), assumes that the users apply a digital signature, with which the messages transmitted under the Diffie—Hellman protocol are signed:

1. A →B: α ^x mod p,

2. B→A: α ^y mod p, E_k(S_B(α ^y, α ^x)),

3. A→B: E_k(S_A(α ^x, α ^y)).

Here S_A and S_B — are the digital signatures of users A and B respectively, k — is the desired shared key. They make it possible to guarantee the authenticity of receiving the message precisely from the user from whom this message was received. Encryption of the signature values of the users is introduced in order to provide mutual confirmation of the correctness of computing the value of the key.

One more approach likewise assumes that the subscribers hold public keys, but instead of a digital signature it proposes using a modified key-agreement procedure. Let us consider the MTI protocol (Matsumoto-Takashima-Imai).

Suppose that users A and B have secret keys a, 1 ≤ a ≤ p - 2, and b, 1≤ b ≤ p - 2 , respectively, and publish their public keys z_A = α^a mod p and z_B = α^b mod p. To derive the shared secret key k they must generate random numbers x, 1≤ x ≤ p - 2, and y, 1≤ y ≤ p - 2, respectively, and then exchange the following messages:

1. A→B: α^x mod p,

2. B→A: α^y mod p.

The resulting shared key is computed using the formula:

Now any tampering with the messages will cause the parties to obtain different key values, which in turn will make it impossible to read any of the transmitted information.

4. Key Pre-distribution

Most cryptographic systems require the pre-distribution of secret keys. For pre-distribution, parties can exchange keys at a personal meeting, entrust key delivery to a specially designated trusted courier, or use some dedicated secure channel for transmission. Depending on the purpose of the cryptographic system, it is sometimes convenient to distribute not the keys themselves but certain auxiliary key materials, on the basis of which each participant or group of participants can independently compute the required key using some procedure established in advance.

Key pre-distribution schemes in a communication network

If the number of subscribers in a secure communication network is small, the number of keys to be distributed is also small. For larger networks, however, key distribution becomes a very serious problem. It lies in the fact that for a network with n subscribers, it is necessary to generate in advance and subsequently store n(n-1)/2 keys. Moreover, each network subscriber must be given keys for communicating with the remaining n - 1 subscribers, which the subscriber must keep permanently. For example, for a network with 100 subscribers, nearly 5000 keys must be generated and stored, and each subscriber must keep 99 keys.

To reduce the amount of stored key information, various key pre-distribution schemes in a communication network are used. Their essence is that what is actually distributed at first is not the keys themselves, but certain auxiliary key materials of a smaller size. Based on these materials, each network subscriber can independently compute, using some algorithm, the key required for communication. This approach makes it possible to reduce the volume of both the stored and the distributed secret information.

As an example, let us consider the Blom scheme for distributing keys among n subscribers, in which the key-computation procedure consists of evaluating a certain symmetric polynomial over a finite field.

Let us choose a field F, having a finite but sufficiently large number of elements, and fix n distinct elements r₁, ..., r_nF, that are nonzero. Let us assign each element r_i

to subscriber i of the network, i = . These elements are not secret and can be kept on a publicly accessible network server. Let us now choose a polynomial over the field F of degree 2t, 1 ≤ t < n, of the form

where a_ij = a_ji, i ≠ j, i,j = . Its coefficients are secret and must be kept only at the key distribution center. Each subscriber A receives as key

material the set , consisting of the coefficients of the polynomial

For communication between subscribers A and B it is now possible to use the shared key k_AB:

k_AB = k_BA = f(r_A,r_B) = g_B(r_A) = g_A (r_B),

computed using the formula:

in matrix form:

where the matrix is made up of the coefficients of the polynomial f(x, y) and is symmetric.

When this scheme is used, each subscriber must store t+1 secret values instead of n - 1, while the total number of secret coefficients of the polynomial f equals t(t+1)/2.

For a given number t the Blom scheme gives the minimum possible amount of key material that must be stored by a subscriber.

The key pre-distribution scheme KDP (key distribution patterns) is based on the set-intersection scheme.

Let there be n, n > 2, subscribers (users) and a set of secret keys K, |K| = q. Let us assume that all keys are numbered 1,2,..., q. Let us choose some family {S₁,...,S_n} of subsets of the set {1,2,..., q}. Subscriber i is beforehand given, over a secure channel, the set of secret keys with numbers from the subset S_i, . Thus the family {S₁,...,S_n} represents a table of key numbers for each user. Although this table is not secret, it must be protected from modification and forgery.

If subscriber i wants to communicate with subscriber j, then to derive the shared key it uses the set of keys whose numbers are contained in the intersection S_i S_j. If each key is represented by some bit string, then to form the shared connection key one can, for example, take their sum, or the value of some hash function of the string made up of the keys whose numbers belong to the intersection of the sets S_i S_j.

A key distribution scheme of type KDP, or a KDP(n,q)-scheme, is any family {S₁,...,S_n} of subsets of the set K, satisfying the following condition:

if for some i,j, r {1 ≤ i < j ≤ n} the inclusion S_i S_j S_rholds, then either i = r, or j= r.

This condition means that the shared key of two subscribers must not be known to any other subscriber.

A family of subsets is called a Sperner family, if none of them is contained in another.

The family {S₁,...,S_n} of subsets of the set K, |K| = q, forms a KDP(n,q)-scheme if and only if the set { S_i S_j | 1 ≤ i < j ≤ n } forms a Sperner family.

If the subsets {S₁,...,S_m} of the set K, |K| = q, form a Sperner family, then

Equality is achieved only if the set {S₁,...,S_m} coincides with the set of all w-element subsets of the set K, where w = q/2 for even q and w = (q+1)/2 or (q- 1)/2 for odd q.

For any KDP(n,q)-scheme, each subscriber must have at least log₂n keys. If n  4, then q  2 log₂n.

5. Secret-Sharing Schemes

A secret-sharing scheme is a key pre-distribution scheme for authorized groups of users, in which the key is fixed in advance and is the same for every authorized group. In this case each user receives their own share or "portion of the secret". The scheme includes two protocols: a protocol for forming the shares (splitting the secret) and distributing them among the users, and a protocol for reconstructing the secret by a group of users. The scheme must allow the key to be reconstructed only by those groups of users who are authorized to do so, and no other group should be able to reconstruct the key or obtain any information about it.

The main purpose of a secret-sharing scheme is to protect the key against loss. Usually, several copies of the key are made to guard against loss. As the number of copies of the key increases, the probability of its compromise increases. If the number of copies is small, the risk of losing the key is high. It is therefore better to "split" the key among several people so that the key can be reconstructed under various circumstances by several authorized groups with a membership agreed upon in advance. This eliminates the risk of irrecoverably losing the key.

Another advantage of secret-sharing schemes is that they distribute responsibility for a decision, which is automatically introduced when the composition of the authorized groups is defined. Such collective responsibility is needed in many applications, including making important decisions related to the use of weapons systems, signing corporate checks, or access to a bank vault.

In the simplest case, where there is only a single group, consisting of t users, authorized to form the key, a secret-sharing scheme can be built as follows. Suppose, for example, that the key is a binary vector s of length t. Let us randomly choose t vectors s₁, ...,s_t such that their sum coincides with the vector s, and distribute them among the users. Now, once gathered together, they can easily reconstruct the value of the key s, whereas no group consisting of fewer users can do so. Indeed, in this case the absence of even one share leads to complete uncertainty about the value of the secret, since for every possible value of the sought secret there is a possible value of the missing share.

Note that if, in the previous example, we had simply split the vector into t parts, then such a scheme could not be a secret-sharing scheme, since knowledge of any share would give partial information about the secret s.

Another example of a secret-sharing scheme is given by Shamir's threshold scheme. Let 1 < t ≤ n. A secret-sharing scheme among n users is called (n,t)-threshold if any group of t users can reconstruct the secret, whereas no group of fewer users can obtain any information about the secret.

To construct an (n,t)-threshold scheme, A. Shamir proposed using a polynomial of degree t – 1 over a finite field with a sufficiently large number of elements. A polynomial of degree t - 1 can be uniquely reconstructed from its values at tdistinct points, but a smaller number of points cannot be used for interpolation.

Let us choose a field F and fix n distinct non-secret elements r₁,...,r_nF, that are nonzero. Each element r_i, is assigned to i-th network subscriber, . Let us also choose trandom elements a₀,...,a_i-1of the field F and form from them a polynomial f(x) over the field F of degree t - 1, 1< t ≤ n ,

Let us set s = f(0) = a₀. Let us now compute the values

s₁ = f(r₁),…, s_n = f(r_n)

and distribute the resulting sets among the participants as shares

To reconstruct the secret S one can use the Lagrange interpolation formula. Suppose there are t pairs (x_i, y_i), where y_i = f(x_i). Then the Lagrange formula has the form

Since s = f(0), from the Lagrange formula we obtain the equalities

where the coefficients cdo not depend on the coefficients of the polynomial f(x) and can be computed in advance.

Using the formula obtained, any group of t users can easily reconstruct the secret. At the same time, it can be shown that no group of fewer users can obtain any information about the secret (prove this yourself).

Shamir's scheme is convenient in that it makes it easy to increase the number of users. To do this, nothing needs to be changed except the set {r₁,..., r_n}, to which new elements should be added r_n+1,..., r_{n+ w}. Compromising a single share turns an (n,t)-threshold scheme into an (n -1, t -1)-threshold scheme.

6. Methods for Establishing Conference Keys

Another type of key distribution among groups of users is provided by key-distribution protocols for conference communication. Despite their outward resemblance to secret-sharing protocols, they have several fundamental differences. Whereas secret-sharing protocols perform a pre-distribution of one and the same key value (secret) over secret channels among privileged groups of users, conference-communication protocols perform a dynamic distribution of keys over open communication channels among privileged groups of users. In this case the keys must be different for each group.

A trivial example of key distribution for conference communication is given by the use of centralized key distribution by means of one of the three-party key-transport protocols used for symmetric cipher systems. To implement such an approach, one of the users in the group must be singled out and given the functions of a key-generation and distribution center. Naturally, this increases the trust and security requirements placed on the designated user, which introduces a serious asymmetry among the participants of the conference communication.

Another approach is based on using the idea of public key distribution.

Let us give examples of protocols in which all group participants have equal authority and perform symmetric functions.

The simplest example of such a protocol for a group of three participants can be obtained by slightly modifying the Diffie-Hellman public key-distribution protocol. The protocol participants agree in advance on the values of a large prime number p and a generating element α of the multiplicative group Z^*_p = {1,2,..., p - 1} . To derive the shared key k users A, B and C must respectively generate random numbers x, y and z, 1 ≤ x,y,z ≤ p - 2 . They must then exchange messages according to the following protocol:

1. A→B: X = α^x mod p,

2. B→C: Y = α^y mod p,

3. C→A: Z = α^z mod p,

4. A→B: Z'=Z^x mod p,

5. B→C: X'=X^y mod p,

6. C→A: Y'=Y^z mod p.

The resulting shared key k = α^xyz mod p is now computed by users A, B and C using the formulas:

k = (Y')^x mod p,

k = (Z')^y mod p,

k = (X')^z mod p

respectively.

The protocol for forming a shared key for conference communication of a group of t users U₀,...,U_t-1. As in the previous protocol, each user U_i; must generate a secret random number r_i, 1 ≤ r_t ≤ p - 2 , and compute the public exponent . Let us set

Then the shared key k has the form

The protocol consists of the following steps:

1. each user U, broadcasts z_i to the other t - 1 users;

2. each user U, computes the value

and broadcasts it to the other t - 1 users;

3. each user U_i, computes the value of the shared key k using the formula

k =

The protocol requires the transmission of 2t(t - 1) messages, and each user must send messages to all the others. The protocol can be modified for the case of message exchange according to a bidirectional-ring scheme.

The protocol considered here does not solve the authentication problem, since it does not include any procedures for mutual authentication of the parties.

See also

• [[b12304]]
• [[b12303]]

See also

• The Key-Sharing Protocol
• Perfect Forward Secrecy (PFS)