Foundations of Coding: Compression, Encryption, Error Correction (2015)

Chapter 3. Cryptology

3.3 Key Exchange

In order to be able to exchange confidential informations, two entities using symmetric cryptography need to have a common secret. This common secret can be the symmetric key they will be using or something that will enable them to build such a key. Now, the question is how can they share a common secret? With perfect secrecy for instance they should meet in person and find a way to exchange this common secret in shelter. This might not always be very practical. An alternative is to use cryptographic tools to perform this key exchange. In this section, we present the classical Diffie–Hellman scheme for key exchange and the nonetheless classical Man-in-the-middle attack that can break it. Then we present the Kerberos system that uses a third party to authentify both entities when they do not even know each other beforehand. We will see that these systems have limitations that will be overcome via the use of asymmetric cryptography.

3.3.1 Diffie–Hellman Protocol and Man-in-the-Middle Attacks

Using a one-way function like modular exponentiation makes key sharing possible.

Thus, let us suppose that Alice and Bob wish to share a secret key K. They first agree on a prime integer p and on a generator g of . Then, one can define the following two-stage protocol that enables them to construct K in secret:

1.

a. Alone, Alice chooses a secret number and computes

She sends A to Bob.

b. Symmetrically, Bob chooses a secret number and computes

He sends B to Alice.

2.

a. Alone, Alice computes .

b. Symmetrically, Bob computes at his end.

Finally, Alice and Bob share the same secret key without ever having disclosed it to each other directly.

Exercise 3.13

One supposes that Oscar sees A and B. Explain why Oscar cannot easily deduce K.

Solution on page 309.

Exercise 3.14

Alice and Bob agree on the following parameters: and . Alice chooses the secret number . At his end, Bob chooses the number . What is the secret key resulting from the Diffie–Hellman key exchange protocol?

Solution on page 309.

The most classic attack on interchange protocols consists in Oscar cutting the communication line between Alice and Bob before they start the key sharing (transmission of A and B). This is the so-called Man-in-the- middle attack. The general idea is that Oscar passes himself off as Bob as far as Alice is concerned and as Alice as far as Bob is concerned.

In this way, Oscar can read all communications between Alice and Bob with the key that they think they have constructed in secret. In practice, Oscar produces and . He intercepts A and B and then produces and . Then, he sends to Alice and to Bob. The progress of the attack is given Table 3.9.

Table 3.9 Man-in-the-Middle Attack on the Diffie–Hellman Protocol

Next, Oscar has to decode the messages sent by Alice or Bob on-the-fly and then re-encode them with the other key in the manner given in Table 3.10.

Table 3.10 Sending of a Message Intercepted by the Man-in-the-Middle

Thus, Alice and Bob think that they are sending each other secret messages, whereas Oscar is intercepting them and decrypting them in the middle! So not only is Oscar able to obtain all the exchanges between Alice and Bob but he is also able to modify these exchanges. Indeed, nothing prevents him, being in the middle, from replacing the message sent by Alice with whatever information he wants. In the sequel, we describe various secret key and public key protocols developed to prevent such an attack.

3.3.2 Kerberos: a Secret Key Provider

To agree on the enciphering and deciphering functions E and D, the safest solution is for Alice and Bob to meet physically. The Diffie–Hellman protocol allows one to do away with this physical meeting, but its weakness is that an active intruder placed between Alice and Bob may intercept all communications.

One solution for avoiding excessively numerous exchanges while protecting oneself against the “ Man-in-the-middle ” attack is to introduce a third party. Developed by the Massachusetts Institute of Technology, Kerberos is a secure authentication system with a trusted third party (or Trusted Authority (TA)), which is designed for TCP/IP networks. However, it is not a system for authorizing access to resources, although there are extensions considering this issue. The MIT distribution of Kerberos is free. This system shares with each entity U of the network a secret key (a password in the case of a user), and knowing this key stands stead of a proof of identity.

The authentication is negotiated by means of a trusted third party : the Key Distribution Center (KDC) Kerberos incorporates a number of features:

· the authentication is secure;

· there is no sending of passwords over the network;

· the authentication is unique: the user only enters his/her password once (for a given period of time, one day for instance) to connect several times with the remote services (this principle is called “ Single Sign On ”);

· the authentication is managed in a centralized way; and

· this standard is compatible with several operating systems (notably unix, linux, , and ).

Kerberos identifies the users of the system (a physical person, a Server, or a service) via a triplet name, role, domain (where domain identifies the administration domain associated with at least one Kerberos server)—more precisely, in the form of aname/role@domain string. Hence, one physical person is identified by the string login/staff@DOMAIN. For a service, it is better to refer to the server that provides the service: it would be identified by the string service/hostname@DOMAIN.

3.3.2.1 General Description of the Kerberos Protocol

Kerberos is based on the use of tickets that are used to convince an entity of the identity of another entity. It also creates session keys that are given to two participants and are used to encrypt data between these two participants, following the steps shown in Figure 3.15. There are two types of accreditations:

· the tickets that are used to securely give the future recipient (Bob or the Ticket Granting Service (TGS)) the identity of the sender (Alice) to whom the ticket has been supplied. It also contains information items that the recipient can use to make sure that the sender using the ticket is indeed the party to whom the ticket was issued.

· the authenticators, which are additional accreditations presented with the ticket.

Figure 3.15 Kerberos authentication steps

A ticket takes the following form:

Thus, it contains the name of the service s that Alice wishes to use (TGS, or Bob) as well as a list of information items enciphered with the service's secret key (that only the service will be able to decrypt); more precisely:

· the identity of Alice,

· the date of the request, t

· the date of expiration of the ticket,

· and (above all) a session key , which will be used for the authenticator (see below) and for enciphering future communications between Alice and the service s.

Although Alice is not able to decrypt the ticket (it is enciphered with the secret key ), she can nonetheless give it encrypted to s. Thus, in parallel with tickets, Kerberos also uses authenticators taking the following form:

Alice generates an authenticator each time she wants to use a service s (TGS or Bob).

Contrary to the ticket, which Alice can use several times for gaining access to the service, an authenticator is unique and can only be used once. However, as Alice possesses the session key , she will be able to generate one whenever necessary.

3.3.2.2 Details of Kerberos Messages

Figure 3.15 shows the various messages that are exchanged. To sum up:

· Messages 1 and 2 enable Alice to obtain the first ticket, which she then presents to the TGS each time she wants to contact a recipient.

· Messages 3 and 4 let Alice get a service ticket, which she then presents to Bob for a service request.

· Messages 5 and 6 correspond, respectively, to the service request from Alice to Bob and to the response from Bob. As we will see, this step enables Alice and Bob to mutually authenticate themselves and to provide them with a session key that lets them encrypt their future messages. This is the sense in which one should understand the concept of service.

Now let us look at the explicit content of these messages:

1. : this message simply acts as an introduction to Alice. She states her name and the name of the TGS she wants to deal with³.

2. : the authentication server (AS in Figure 3.15) looks for the client in its database. If it finds it, it generates a session key thta should be used between Alice and the TGS. First, this key is enciphered with Alice's secret key ⁴: this is the first part of the message (). Then, it creates a ticket for Alice, so that she is able to authenticate herself with the TGS. As we have seen earlier, this ticket is enciphered with the TGS's secret key . Alice is not able to decrypt it,but she can still present it at each request to the TGS. In this particular case, the ticket is called TGT. One may notice that only the genuine Alice is able to retrieve the session key (she is the only one who possesses the secret key ). Therefore, Alice now has the session key and the TGT ticket .

3. : Now, Alice has to obtain a new ticket for each Bob she wishes to contact. For this, Alice contacts the TGS providing it firstly with the TGT ticket she already possesses and also with an authenticator (in addition to the name of the server she wishes to contact). The authenticator contains formatted, genuine information items from the ticket via the TGS. As these information items are enciphered with the session key , it proves that Alice knows it and thus, authenticates her. (Hence the name “ authenticator” given to ).

4. 4. : Thanks to its secret key , the TGS decrypts the ticket, retrieves the session key , and is then able to decipher the authenticator . It compares the content of the authenticator with the information items contained in the ticket. If everything agrees (Alice is authenticated), it can generate a session key (which will be used between Alice and Bob) enciphered with the session key and a new ticket that Alice will have to present to Bob. After receiving the message and deciphering it, in addition to and (that she will keep until the ticket expires for interacting with the TGS), Alice will have a new session key and a new ticket that she can use with Bob.

5. : Now, Alice is ready to authenticate herself to Bob; this is performed in the same way as between Alice and the TGS⁵ (see message ).

6. : Now, Bob must authenticate himself by proving that he is able to decrypt the ticket , hence that he possesses the session key . He has to send back a piece of information that can be checked by Alice, encrypted with this key. By verifying it, Alice is now sure of the identity of Bob and has a session key that can be used for enciphering the communications between Alice and Bob.

3.3.2.3 Weaknesses of Kerberos

· Attack by repetition: although the datings are supposed to prevent it, the messages might be replayed during the lifetime of the tickets (around 8 h by default).

· Dating services: the authenticators depend on the fact that all the clocks on the network are more or less synchronized. If one is able to mislead a computer as regards to the true time, then the old authenticators can be replayed. Most of the time maintenance protocols are not secure. Hence, this can be a serious vulnerability.

· Password gamble: an intruder has to collect the first halves, , of the messages in order to predict the value of (in general, ). By gambling on the password , the intruder is able to compute , decode, and obtain . He can then check the correctness of his choice by decrypting the authenticator of which he knows the content (at least, he knows ).

· Login name usurping (commonly referred to as “ spoofing”): one may imagine an attack in which all the Kerberos client programs are replaced by a version not only implementing the Kerberos protocol but also recording passwords.

The KDC holds the keys of all users and all servers. While this reduces the total number of secret keys (otherwise every user would have to have one key for each server and vice versa), it also means that if the KDC is successfully attacked, all the keys have to be changed. Public key architectures enable one to get rid of this last problem.

Exercise 3.15 (Needham–Schroeder Protocol Attack)

Alice and Bob want to exchange a session key. Ivan shares one secret key with Alice and one secret key with Bob. The Needham and Schroeder protocol is as follows:

i. Alice sends to Ivan.

ii. Ivan generates a session key K and sends to Alice.

iii. Alice sends to Bob.

iv. Bob sends to Alice.

v. Alice sends to Bob.

1. What is the purpose of ?

2. What is the purpose of and why does Alice have to send it back as ?

3. One security problem with this protocol is that the old session keys keep their value. If Eve is able to eavesdrop on the messages exchanged and was able to obtain an old session key, explain how she can convince Bob that she is Alice.

4. What should be added to messages to prevent this vulnerability? What does the resulting protocol look like?

5. In the resulting system, a user doesn't need to authenticate himself with the KDC each time he wants access to a service. Why? What is the weakness of this method?

6. In this system, Ivan has a list of keys (or password fingerprints) for all his clients. What could happen if this list was stolen? How can one protect oneself from such a danger?

Solution on page 310.

To overcome the problem of key theft, one solution would be to use a public key system for authentication instead. This system is explained in Section 3.4.