Chapter 6. Cryptographic Protocols: Surprising Vistas for Communication

6.1 More than Etiquette

A protocol usually refers to customs and regulations dealing with diplomatic formality, precedence and etiquette. Typically, a protocol determines a map for seating the participants, or the order of speeches. It has happened that an inter­national conference has spent most of the time while arguing about the seating protocol.

A cryptographic protocol constitutes an algorithm for communications between different parties, adversaries or not. The algorithm applies cryptographic trans­formations and is usually based on public-key cryptography. However, the goal of the protocol is usually something beyond the simple secrecy of message transmis­sion. The communicating parties might want to share parts of their secrets to achieve a common goal, or to join their forces in order to disclose a secret not known to any of the parties separately. Two parties distant from one another might want to generate together a random sequence. One party might also want to convince another that he/she is in the possession of some information, without disclosing anything of the information itself. Protocols realizing such goals have considerably changed our ideas about what is impossible when several parties, adversaries or not, are communicating with each other.

Protocols are designed with a specific goal in mind. Both the security properties of the underlying cryptosystem and those of the protocol itself have to be taken into consideration in the evaluation of the protocol. Intuitively, a protocol is at most as secure as the underlying cryptosystem but the security of a protocol can be much lower.

For instance, consider the following very general task. A private conversation should be established between two individual users of an information system or a communication network. No assumptions are made concerning whether or not the two individual users ever communicated before. The basic idea behind public- key cryptography can be used to solve this problem. The resulting protocol is very simple and consists of the following two steps. First, all users publish their encryption key. Secondly, messages intended for a user A are encrypted by ,4's encryption key. In this case the underlying cryptosystem might be secure but the protocol as such still does not prevent the possibility of impersonating: Some user C might pretend to be the user B when sending messages to A. To prevent the occurrence of such situations, some convention of signing messages has to be added to the protocol.

When separating security properties of the underlying cryptosystem from those of the protocol, the possible adversaries should be kept in mind. In most commun­ication protocols, an adversary belongs to one of the following three types.

(1) Communicating parties who try to cheat. We will meet later two types of cheaters, passive and active.

(2) Passive eavesdroppers. They are otherwise harmless but may obtain in­formation not intended for them.

(3) Active eavesdroppers. Besides obtaining secret information, they may mess up the whole protocol.

In the simple protocol above, the user C who tries to impersonate B can be classified to belong to the type (3). For an example of an adversary of the type (1), consider the protocol in Example 2.3 for playing poker by telephone. Assume, further, that encryptions and decryptions are carried out by modular exponen­tiations and taking discrete logarithms, respectively. (In Example 2.3 the encryp­tion and decryption methods were left unspecified.) More specifically, assume that the players A and B have agreed on a large safe prime p and on the representation of the cards as numbers from the interval [2, p — 1]. Each player chooses privately encryption and decryption exponents satisfying

^eA^dA = ^e_Bd_B = ¹ (modp - 1),

after which encryption and decryption are carried out modulo p. However, the property of being a quadratic residue (mod p) is preserved in this encryption. If the dealer notices that the numerical representation of each ace is a quadratic residue, only nonresidues are dealt to the opponent and residues to the dealer. The dealer now knows that the opponent has no aces. It is also clear that all hands are not equally likely. Even in the case of a modulus n such that quadratic residuosity (mod n) is intractable, the dealer can trace the progress of a perfect square (mod n) through the execution of the protocol.

Usually it is very difficult to establish mathematical theorems about the security of a protocol as such or with respect to the security of the underlying cryptosystem. One should examine methods by which the security properties of protocols can be defined and established, as well as by which the impossibility of a protocol meeting certain requirements can be proved. The same issues are met also in the analysis of ordinary algorithms. However, cryptographic protocols are different from ordinary algorithms in that each participant has some computational power (that might vary from participant to participant) and is able to make inferences. This means that a participant may combine a priori knowledge and the knowledge acquired so far with the information contained in the messages just received. The new message to be sent depends on this combined knowledge.

The following modification of a popular game illustrates these issues. The participants, arbitrarily many, form a chain. The first and last member know their positions. Moreover, each member knows the next member in the chain. During the first phase of the protocol the first member sends the number 2 to the second, and any other member adds 1 to the number received and sends the resulting number further, with the exception of the last member who does not send anything further. After this phase every member knows his/her ordinal number i. The second phase of the protocol consists of a transmission of a message w consisting of a string of letters over the English alphabet. The message w is originally in the possession of member 1. After receiving a message w', the member i applies CAESAR(i) to the first letter of w\ transfers the resulting letter to the end of the word, and sends the new word to the next member. Again, the last member does not send anything. If there are altogether seven members, then the plaintext w = SAUNA is transformed as follows:

SAUNA - AUNAT - UNATC ->• NATCX -> ATCXR TCXRF - CXRFZ

After receiving the word CXRFZ, the seventh member is immediately able to decrypt, and so are all members. Clearly, this protocol is very vulnerable against adversaries of all of the three types (l)-(3).

A protocol for sending encrypted messages, where the receiver acknowledges the receipt, can be described as follows. The encryption keys E_A,E_B,.. . have been publicized, whereas each of the decryption keys D_A,D_B,... is known to the appropriate user only. According to the protocol, the sending of a message w from A to B is carried out in two steps.

Step 1: A sends the triple (A, E_g(w), B) to B.

Step 2: B decrypts using D_B and acknowledges by sending the triple (B, E_A(w), A) to A.

An active eavesdropper C may now intercept the triple in Step 1 and forward to B the triple (C, E_B(w), B). Without noticing the trick, B sends in Step 2 the triple (B, £_c(w), C) to C, after which C is able to decrypt! Even the following version, where also signatures are provided, does not essentially alter the situation.

Step 1: A sends the pair (E_B(E_B(w)A), B) to B.

Step 2: B uses D_B to find A and w and acknowledges by sending the pair (E_A(E_A(_W)B), -4) to A.

Here the functions E and D are assumed to operate on numbers. The names A,B,... are sequences of digits, and E_B(w)A is the sequence of digits obtained by catenating E_B(w) and A.

An active eavesdropper C may now intercept the pair (E_A(E_A(w)B), A) in Step 2. Thus, C knows E_A(w'), where w' = E_A(w)B. C now sends A the pair (E_a(E_a(w')C), A) and A, thinking that this is Step 1 of the protocol, acknowledges by sending the pair (E_c(E_c(w')A), C) to C. C now finds out w' and hence also E_A(w) by using D_c, after which C sends the pair (E_A(E_A(w)C), A) to A. After A has acknowledged by sending the pair (E_c(E_c(w)A), C) to C, C is able to compute w. Of course, A may learn about the interception and be more cautious by keeping a detailed record of messages sent and received.

We discuss finally in this section a signature scheme based on the identities i of users in a network. The identity i can be based, for instance, on the user's name and network address. The identity should identify the user and be available to the other users. It serves the purpose of a public encryption key.

The scheme assumes also the existence of a trusted agency, whose sole purpose is to give each user a secret number x, based on the user's identity i. This happens when the user joins the network.

More specifically, let n, e and d be as in RSA, and / be a one-way function of two variables. The items n, e and / are made public, but d and the factorization of n are known only to the agency. The secret number given by the agency to the user with the identity i is

x = (i^d, mod n).

The user's signature for a message w is any pair (s, t) such that (*) s^e = i-t^fi'-^w)(modn).

Given a triple (w, s, t), this condition can be verified by the other users because /, n, e and / are public information.

On the other hand, a user can generate a signature (s, t) for a message w by choosing a random number r and computing

t = (r^e, mod n) and s = (xr^/(1, mod n).

Since x^e = i (mod n), the verification condition (*) follows. The function / is used to a cryptographic hashing of t and w.

Date: 2015-02-16; view: 672