Authentication Protocols

Before illustrating authentication protocols that are commonly used in the real world today, the word “protocol” needs to be defined. Protocols are the rules that must be followed by participants or entities in some particular interactions. Thus, network protocols are the rules followed in networked communication systems. Security protocols are the communication rules followed in security applications. Cryptographic protocols are the rules that apply cryptographic techniques so that participants or entities can communicate securely. Authentication protocols fall into the security and cryptographic protocol categories and can be defined as a set of rules that must be followed for entities to prove or confirm their identity. That is, Alice must prove to Bob that she is really Alice, or Bob must prove to Alice that he is really Bob.

Authentication, in many cases, only requires that Alice proves her identity to Bob without Bob proving his identity to Alice. This is called one-way authentication . Sometimes, though, it is necessary for both Alice and Bob to prove their identity to one another. In other words, Alice proves that she is Alice, and Bob, in turn, proves that he is Bob. This is known as two-way authentication or, more formally, mutual authentication . In some situations, the use of symmetric cryptography, asymmetric cryptography, or cryptographic hash functions might be required, as will be seen in the following sections.

Before going into the details of well-known authentication protocols that have been designed, it is necessary to explain the concept of one of the most commonly used components in authentication protocols. The component is known as a nonce or a cryptographic nonce . In cryptography, the term “nonce” stands for “number used once.” It is an arbitrary number that is usually created randomly and can only be used once in a cryptographic protocol or cryptographic communication.

In authentication protocols, nonces are used to ensure that protocol messages cannot be reused in replay attacks. A replay attack is when an attacker eavesdrops a protocol message and retransmits it. A replay can be explained with a simple example shown in Figure 7-1, which shows that Eve sniffs a message that Alice is sending to Bob. Eve then resends the exact same message to Bob, who might think that it is Alice who has sent it.

One way that this problem can be solved is to apply a nonce to a message. In the example, if a nonce is added to the message that Alice sends to Bob and then Eve replays the same message, Bob will be able to notice that Eve’s message is a replay. This is because Bob will notice that the nonce in Eve’s message is exactly the same as the one in Alice’s message.

In reality, apart from using nonces to prevent replay attacks, they can serve other purposes, too. One purpose is that they can serve as a challenge-and-response mechanism. A challenge-and-response mechanism is basically a protocol where one entity presents a question (called a “challenge”), while the other provides an answer (called a “response”). The most simple challenge-and-response mechanism is actually when a server asks a client for a password. This is a challenge. The client then replies with their password. This is a response.

However, when a nonce is used in the challenge and response, it is a little different. In an authentication protocol where a server would like to prove whether or not a client possesses the same symmetric key, a nonce can be used as follows:

where Nonce_S is the nonce value belonging to the server,

K_SC is the symmetric key shared between the server and the client, and

{M}_K is when the message M is encrypted with a symmetric key K.

From the preceding example, the server sends a nonce value to the client who then encrypts it with a symmetric key and transmits the ciphertext to the server. This way the server can easily prove whether or not the client is possessing the same symmetric key by just decrypting the ciphertext. If the resultant plaintext is the same as the nonce value he has sent earlier, the server will know that the client is holding the same symmetric key.

This is just an example of how a nonce or cryptographic nonce can be used in authentication protocols. How nonces are used and applied in authentication protocols is actually up to the protocol designer’s imagination. However, it is important to know that nonces serve two main purposes. The first is to prevent replay attacks. The second is to be used in challenge-and-response mechanisms.

Let us now take a look at some authentication protocols that are deemed interesting and thought provoking. Some are actually very commonly used in the real world, while some are considered classic albeit not the most secure.

Andrew Secure RPC Protocol

RPC stands for Remote Procedure Call which is a method used for causing a function to be executed at another place or on another machine. RPC can either be done by calling a function at a different address space on the same machine or on another machine on a network and even over the Internet. In order to make this procedure more secure, Andrew Secure RPC was proposed as a protocol that allowed two entities, usually a client A and a server B, who already shared a secret key K_AB to carry out authentication and establish a new session key . The Andrew Secure RPC consists of four messages that constitute two main parts. The first three messages make up the handshake, while the fourth message is the session key establishment. The protocol messages are as follows:

From the above protocol, N_A is the nonce generated by the client A. The nonces N_B and are generated by the server B. The notation {M}_K means the message M is encrypted with the symmetric key K.

Unfortunately, the original Andrew Secure RPC has been found to be insecure. The first problem is that the second message could be substituted for the fourth message making the client believe that the component N_A + 1 is actually the new session key. Looking at another angle, the fourth message could easily be a replay of the second message. Another problem is concerning the freshness of the new session key because there is no guarantee that the key is really fresh or newly generated. There are also other issues including the lack of message integrity detection mechanism and mutual authentication.

Various researchers have made an attempt to improve the protocol with the following being the latest and most secure version:

The notations are as described earlier with the addition of MAC_K which means a cryptographic hash function MAC being computed with the secret key K.

The most recent version of the Andrew Secure RPC protocol accomplishes all the objectives in mutual authentication and secure key establishment. It is also secure against replay attacks and message modification attacks.

Needham–Schroeder Protocol

The Needham–Schroeder authentication protocol is probably one of, if not, the best-known security protocols. This authentication protocol is considered important to the field of authentication protocols because it has influenced the design of a significant number of authentication protocols existing today. The Needham–Schroeder authentication is different from the Andrew Secure RPC because it requires the use of a trusted third party (TTP) to complete the authentication and session key establishment.

The aim of the Needham–Schroeder protocol is for two entities A and B to be provided with a new session key K_AB. The protocol requires a trusted authentication server S, which shares common secret keys with all potential participants, A and B in this case. The server S also has the ability to generate a secure session key for any two entities wanting to have a secret key shared between them. The Needham–Schroeder protocol consists of the following five messages:

where N_i is the nonce value belonging to an entity i,

K_ij is the symmetric key shared between the entities i and j, and

{M}_K is when a message M is encrypted with a symmetric key K.

It can be seen that at the end of the protocol session, the principals A and B will end up with a new shared secret K, which will be used for secure communications between them. It can also be observed that the protocol is intended for both A and B to practically authenticate one another in the fourth and fifth messages by asking one another to encrypt a message using the session key K.

However, several flaws have been found in this protocol, most notably a potential replay attack and a lack of message origin identification. A couple of researchers have pointed out that it was possible to replay the third message since there is no component suggesting that the message, specifically the key K, is freshly generated. The second vulnerability is in the fifth message. As mentioned, there is no way for B to know whether or not the message is really from A, which could lead to a message spoofing attack. As a result, an improvement has been made to obtain what is known as an enhanced Needham–Schroeder protocol, which works as follows:

It is evident from the enhanced protocol that the replay attack can be solved by the principal B generating their own nonce N_B1, which is also present in the fifth message. This way B knows that the component N_B1 is new or fresh. Hence, if there is a replay, B should be able to detect it and ignore the message altogether. The enhanced version of the Needham–Schroeder protocol is now believed to be secure, provided that the cryptographic implementation is properly and securely done.

Even though the original Needham–Schroeder authentication protocol has several vulnerabilities, it is still a big influence on many existing authentication and session key establishment protocols today. At the very least, the Needham–Schroeder protocol was the first to implement a three-party protocol that consisted of authentication and key establishment with the help of a trusted third party. Many protocols today, such as Kerberos that will be discussed later in the chapter, have applied the idea as their foundation and built upon it to make them more secure.

Needham–Schroeder Public Key Protocol

Needham and Schroeder not only designed an authentication protocol that applied symmetric cryptography, they also designed one of, if not, the first authentication protocols that used asymmetric cryptography. The Needham–Schroeder Public Key protocol, again, is considered as the beginning of an idea of using public key cryptosystems in authentication protocols.

The Needham–Schroeder authentication protocol has an objective of having two entities, A and B, authenticate one another. Hence, mutual authentication is aimed to be accomplished after a protocol run. The protocol works as follows:

where N_i is the nonce value belonging to an entity i,

+K_i is the public key of the entity i, and

is when the message M is being encrypted with a public key +K_i.

The protocol begins with the entity A sending their identity A along with the newly generated nonce N_A, all of which are encrypted with the public key of the entity B. When B receives the message, they decrypt it using their private key, which is only known by the entity themselves. B then sends the component N_A back to A together with the freshly generated nonce N_B. All are encrypted with the public key of entity A. Finally, A receives the message and decrypts it with their private key. The entity A then checks whether the received N_A matches with the one they had sent earlier. If so, A sends the nonce N_B which is encrypted with B’s public key back to the entity B. Having received the message, B decrypts the message to ensure that the received component is actually the nonce that they had sent earlier.

At the end of this protocol run, A is certain that the other entity is B if and only if the nonce N_A matches with the one in the first message. This is because B is the only one holding the private key that can be used to decrypt the message. Similarly, B is sure that the other entity is A if and only if the nonce N_B in the third message matches with the one in the second message. Again, only A possesses the private key that can decrypt the second message.

Needham and Schroeder have, thereof, shown that it is also possible to use asymmetric cryptography as a part of a protocol that can mutually authenticate the two participating principals.

Although the public key protocol shows some promises of the way to integrate asymmetric cryptography into a mutual authentication mechanism, there is one interesting flaw that was discovered almost 20 years after its birth and should be mentioned here. The protocol is prone to an attack called a man-in-the-middle attack or MitM attack. This type of attack practically means that an attacker C comes into the middle of the conversation between A and B with an objective of impersonating the entity A so that B believes that they are conversing with A. The man-in-the-middle attack is illustrated in Figure 7-2.

The problem actually occurs because there are no components specifying the identity of the message originator in the messages two and three of the Needham–Schroeder Public Key protocol. Therefore, one way to reduce the risk is by adding the identity components B and A in the second and third messages of the protocol, respectively. The resultant protocol thus becomes

Based on the preceding classic authentication protocols, it has been possible for researchers and protocol designers to deduce protocols that would be applicable to real-world usage. The following sections take a look at a couple of authentication protocols whose aims are to confirm the identities of protocol principals as well as to establish a new session key so that a more secure communication channel can be created. The two authentication protocols are known as secure socket layer and Kerberos , which work based on the use of asymmetric cryptography and symmetric cryptography, respectively. Although the technologies behind them are different, they do have similar objectives, as mentioned. The description of how each scheme functions is presented in the subsequent sections.

Secure Socket Layer (SSL)

The first real-world authentication protocol to be discussed is known as secure socket layer or SSL . This protocol is used as or is a basis of other protocols used for securing most Internet transactions. SSL originally dealt mainly with web browsing. However, nowadays, it has become a major part of many transactions on the Internet, which include those of mobile applications. If we map this with the computer network’s OSI model, we will see that SSL is responsible for securing the HTTP in the application layer and the TCP protocol in the transport layer. Hence, SSL’s subsequent version is called Transport Layer Security or TLS . Although the name has been changed from SSL to TLS, the aim of authenticating data transfer or transactions between entities still remains. The only major difference in the context of security is that TLS works with newer cryptographic algorithms including AES and key-based cryptographic hash functions.

Secure socket layer is an element used for safeguarding transactions between users and websites or between users’ device and the server of the application they are using. One of the protocol’s main purposes is to prevent transaction messages or packets from being eavesdropped. SSL is a protocol used to establish a secure channel between two points on the Internet, so that data can be encapsulated and hidden from attackers. However, prior to the action of securing communication channel taking place, one process that must be done is, of course, authentication which is an integral part of the protocol and will be explained later in the section.

In the case of websites, web addresses usually begin with HTTP, which stands for hypertext transfer protocol. Unfortunately, communication using this protocol is not secure and is prone to eavesdropping. This is, therefore, not recommended for transmitting such data as personal information, personal bank records, or credit card number. A solution to this problem is to use HTTPS or secure HTTP. By typing HTTPS instead of just HTTP at the beginning of a web address, SSL is effectively implemented.

SSL is better explained with an example. Suppose a user wants to buy a book from an online bookshop. Before providing their credit card information, the user must be sure that they are really dealing with a legitimate bookshop. That means the bookshop must prove to the user that it really is legitimate. After the user is satisfied that they are dealing with a trusted bookshop, private information can then be provided. In most cases, the user would want to have confidentiality and integrity. The user wants confidentiality because their credit card information needs to be kept secret. Integrity of data is also required because the exchanged information must be correct. For example, if the user orders one book, the number of books should remain one throughout the transactions. SSL is, therefore, a suitable solution.

SSL begins with a handshake phase. This handshake protocol is used to initiate an SSL session between a client and a server. During the handshake, various components, such as keys, digital certificates, and algorithms, are exchanged and negotiated so that a secure communication channel can be established. Entity authentication is also carried out here, in this phase. An overview of the SSL handshake protocol is shown as follows:

where S is the “pre-master secret,”

K is the session key and is computed from H(S, N_Client, N_Server),

+K_Server is the server’s public key,

Certificate_Server is the digital certificate belonging to the server,

H() is a cryptographic hash function,

msg is representing all previous messages,

CLNT is the ID of the client, and

SRVR is the ID of the server.

At the end of the process described earlier, the client should have authenticated the server. The question is: where is the actual authentication process? Some may think that the certificate sent to the client by the server is where the authentication takes place. However, sending the certificate, even if it is valid, does not prove that the sender is really the server. In fact, the client is certain that the other party is the server because the pre-master secret component S is encrypted with the server’s public key, and the only entity that can decrypt it is the server. The client knows that the server has decrypted S successfully because during the information exchange phase, both the client and server can encrypt and decrypt data successfully, in addition to the data integrity checking done by the cryptographic hash function H(). Hence, they both possess the same symmetric session key K, generated from the same pre-master secret S.

It can be observed that the preceding process is one-way authentication, since only the client authenticates the server. The server has not authenticated the client at all. SSL provides an option for doing authentication in the opposite direction, too. If the server requests client authentication, the client sends the server their certificate. The server randomly generates another pre-master secret and encrypts it with the client’s public key. Similar to when the server is authenticated, if the client can decrypt the ciphertext, the server is certain that this is the client. Having said that, the request for client authentication is not usually done this way. Other means of authentication such as using a password is a more commonly adopted method.

As explained, at this point, the SSL handshake or the authentication process is complete. The client and the server can now use the newly established session key to encrypt and decrypt data as well as to validate message integrity using a category of cryptographic hash function known as message authentication code. Hence, a secure communication channel between the server and the client is generated in addition to a successful authentication procedure.

Secure socket layer provides us with enhanced security over the Internet. However, it does come with an overhead. Recently, there have been a lot of talks about the sluggishness of SSL. One factor behind this is the use of certificates. SSL uses certificates so that a client can obtain the server’s public key, and vice versa, in the case of mutual authentication. In more detail, after a digital certificate is issued by a certificate authority (CA), it is possible that it is compromised and needs to be revoked. This is why a certificate revocation list (CRL), which is a database containing invalid and compromised certificates, needs to be present. This means that when an SSL handshake is carried out, the CRL has to be queried in order to ensure that the certificate is valid. The problem is the CRL servers are not usually geographically distributed or tuned for performance. This implies that some time will be added to the typical page load time.

On the whole, SSL has given better protection of data, albeit with a little overhead. Moreover, SSL is an authentication protocol based on the use of public key cryptography and digital certificates. The next section introduces another authentication protocol, but this time, it will be different since it is designed and implemented based on symmetric cryptography.

Kerberos

In Greek mtyhology, Kerberos is a three-headed dog that guarded the entrance to Hades. In the context of security, Kerberos was designed at the Massachusetts Institute of Technology or MIT as a solution to the insecurity of computer networks. Kerberos is an authentication system that uses symmetric key cryptography. It allows entities to communicate and to prove their identity to one another in a secure manner.

At MIT, a Kerberos consortium was actually founded. Its main objective is “to establish Kerberos as the universal authentication platform for the world’s computer networks.” Nowadays, Kerberos has become a major foundation of desktops, server operating systems, core networking infrastructure, and much more. One of the main uses of Kerberos is to provide a single sign-on (SSO) environment . It also has the potential to integrate password-less authentication mechanisms to form a more convenient security solution. Moreover, it has been suggested that Kerberos has grown to become the most widely deployed system for authentication and authorization in modern computer networks.

Prior to explaining how Kerberos works, a typical scenario needs to be set. Suppose on a network, there are many individuals such as Alice, Bob, and Charlie. There are also resources, systems, and applications that can be accessed by the users. They include an email system, a web application, and a database server.

For any users to access and use those systems, typically they are required to log in. For example, for Alice to access her email, she needs to authenticate herself with the email system. Similarly, if she wants to access the web application, she will be asked to authenticate herself again, and so on. This means that on this network, the email system, the web application, and the database server, each has its own authentication system. The users will have to carry out authentication each time they want an access to a system. This results in inconvenience and, more importantly, potential issues with password reuse and weak passwords. This typical scenario is displayed in Figure 7-3.

Kerberos, as mentioned, functions based on the application of symmetric cryptography. Its main characteristics include the fact that it requires N keys for N individuals on a network and that the Kerberos authentication system relies on a trusted third party (TTP). Kerberos’ TTP is known as a key distribution center or a KDC . The key distribution center’s main job is to provide symmetric session keys and “tickets” for users to access the resources on a network. The key distribution center also shares a symmetric key with each individual, such as K_A with Alice, K_B with Bob, K_C with Charlie, and so on. The KDC also holds a master key of its own called K_KDC.

When using Kerberos, users accomplish two things. They are authentication for identity verification and session key establishment for secure communication. In order to achieve those two objectives, the key distribution center and the concept of Kerberos “tickets” are needed.

With reference to Figure 7-3, each individual is required to present a valid ticket to the system they are accessing before being granted the permission to access. In Kerberos, a ticket contains cryptographic key and other information required to access network resources. However, for any individuals to obtain those access tickets, another type of ticket has to be attained. That ticket is known as a ticket granting ticket or a TGT . That is, a ticket granting ticket is used to exchange for access tickets that are then used to allow access to network resources. For example, if Alice wants to access the web application on her network, as shown in Figure 7-3, she will have to get her ticket granting ticket verified by the key distribution center so that the key distribution center can create a valid access ticket and issue it to Alice. Alice will then present the obtained access ticket to the web application which will check its validity. If it is valid, Alice is granted an access. If not, Alice will be denied an access. The process described here is illustrated in Figure 7-4.

In more detail, each ticket granting ticket contains a session key, a user ID of the user to whom the TGT is issued, and an expiration time. One clever feature of Kerberos is that the ticket granting ticket is encrypted using K_KDC and can only be read by the KDC.

We now know that Kerberos is used for authentication and session key establishment. The protocol consists of various components including a key distribution center, a ticket granting ticket for each user, and access tickets for accessing network resources and systems. Let us now look at how Kerberos actually works, starting with the client login process and then Kerberos ticket exchange process.

Client Login

Before a user can access any resources on a network, they will have to complete the login process. The login process is a simple process that requires a user to log into their computer, which will communicate with the key distribution center (KDC). Kerberos will carry out its functions (which will be explained later). In the end, the key distribution center will hand a ticket granting ticket to the user. This client login process is shown in Figure 7-5.

The Kerberos client login in Figure 7-5 begins with Alice entering her username and password into her computer. The computer derives the key K_Alice from Alice’s password as K_Alice = H(Alice’s Password). It needs to be clarified that the key distribution center is not only responsible for distributing keys to users, it also acts as an authentication server, which means its other task is to authenticate users on the network. It, therefore, implies that K_Alice is the key shared between Alice and the key distribution center.

Alice’s computer will use K_Alice to obtain a ticket granting ticket (TGT) for Alice from the key distribution center. The KDC receives the TGT request and generates a new session key S_Alice and a TGT for Alice. The KDC encrypts S_Alice and TGT with the key K_Alice before sending the packet to Alice’s computer.

The next step is for the computer to decrypt the received packet with K_Alice to obtain the session key S_Alice and the TGT. The key K_Alice can now be forgotten. Note that the , which means that it can only be read by the KDC since the key K_KDC is only known by the key distribution center itself. Alice can now use this TGT to exchange for access tickets for accessing network resources later on.

Kerberos Ticket Exchange

After Alice has completed the Kerberos client login process and obtained the TGT, Alice can now start thinking about accessing network resources. Suppose Alice would like to access a service such as a web application in Figure 7-3. If Alice’s network utilizes Kerberos, Alice cannot just start accessing the required service straight away. There is a process of ticket exchange to be done beforehand. The ticket exchange process is illustrated in Figure 7-6.

From Figure 7-6, a few components need to be defined. The first is the REQUEST, which is defined as REQUEST = (TGT, Authenticator), where The next component is the REPLY, which is sent from the key distribution center to Alice’s computer. The REPLY message is defined as where K_AS is the symmetric key shared between Alice and the service she is trying to access. Moreover, within the REPLY message, .

Alice, more specifically Alice’s computer, presents Alice’s ticket granting ticket to the key distribution center, along with another piece of information called authenticator. The authenticator is composed of the user ID and timestamp, which is used to prevent replay attacks. The authenticator is encrypted using the client’s session key, S_Alice in this particular example. After the key distribution center verifies the authenticator, it responds with a “ticket to service” or an access ticket. Alice can then use the received ticket to access the required service.

It needs to be clarified that an access ticket is issued for an access to one particular service only. If a user wants to access another service on the network, a new access ticket will have to be issued by the key distribution center by following the same process illustrated in Figure 7-6.

Let us take a look at the REPLY packet in a little bit more detail. The REPLY message sent from the KDC to Alice’s computer contains three components: the name of the service “ServiceID”, the key K_AS, and the “ticket to service” or TicketToService. The components are all encrypted with the session key S_Alice shared between Alice and the KDC. What does the REPLY message really say? It tells Alice’s computer that the TicketToService is the ticket used to access that particular service, to communicate with the service, and the key K_AS must be used to secure the communications between Alice and the service.

The next step is for Alice’s computer to hand the TicketToService to the required service so that the service can grant Alice an access and Alice and the service can begin their secure communication. The TicketToService is composed of two components: Alice’s identity and the key K_AS. The two components are encrypted with the key, K_Service. Note that the K_Service belongs to the service and this key is shared only between the service and the key distribution center. When the service receives the ticket from Alice, it decrypts the packet and sees that the key K_AS is to be used for communication with Alice. At this point, Alice and the service are now holding the key, K_AS, and, therefore, can securely communicate with one another.

It has been explained that Kerberos is a very useful protocol for accomplishing user authentication and secure communications between client and network services or resources. However, there are a couple of limitations to the protocol that should be stated. They are as follows: The first obvious drawback to Kerberos is a single point of failure. It can be seen that the key distribution center or KDC plays an important role in Kerberos. The KDC is involved from the client login process to the ticket generation process. If the KDC is compromised or down, these processes cannot be carried out; hence, Kerberos stops working. One simple solution to this problem is to use multiple Kerberos servers.

The second limitation of Kerberos is time restriction. Kerberos requires that the times of the hosts involved are synchronized or at least loosely synchronized. This synchronization is needed because Kerberos tickets have an authenticator, which contains a timestamp. If the clock on the client’s side is not synchronized with the KDC, the timestamp checking process will fail and no further processes will be done.

It was mentioned earlier that one of the main uses of Kerberos was in a single sign-on environment. Single sign on or SSO is an authentication scheme that allows an individual to log into one service or application and that individual appears to be authenticated and signed into other services on the same network automatically. The word “appear” was used in the previous sentence because to the user, the process of authentication to other applications and services is practically nonexistent. However, what goes on in the background that allows the user to access those services and applications is actually Kerberos.

With reference to Figure 7-3 and with Kerberos being deployed, Alice carries out the Kerberos client login process to obtain a ticket granting ticket. When Alice wants to access her email, the ticket exchange is processed in the background so that Alice receives a ticket to access her email without having to log into the service. Alice then wants to use the web application on the same network, and the Kerberos ticket exchange is accomplished in the background, which means Alice is able to enter the web application without having to physically log in. This is how Kerberos is used for the single sign-on implementation.

It is evident from the previous sections that with clear objectives, it is feasible and possible to design an authentication protocol that can accomplish them. Unfortunately, it is not easy to have authentication schemes that do not have weaknesses. It, therefore, seems like a good place to take what has been learned from the classic and real-world authentication protocols and explain how authentication protocols should be thought of and designed. This is so that protocols with fewer vulnerabilities can be formed, while the required goals can still be achieved.

Designing Authentication Protocols

The three classic protocols explained in the earlier sections apply symmetric cryptography and asymmetric cryptography. They have all made a big impact in cryptographic and authentication protocol design, which has eventually led to the two real-world protocols in security socket layer (SSL) and Kerberos. However, as seen, the protocols explained previously, especially the classic ones, contain vulnerabilities. Potential attacks on these authentication schemes include replay attacks and man-in-the-middle attacks. Fortunately, there are mechanisms available to combat them. They include the use of a nonce value and a challenge-and-response method, as already explained in the beginning of the chapter. This section, based on what we have learned from those protocols, will provide an explanation of how we should look at authentication protocols and what we should consider when designing them so that we end up with a more secure scheme as a result.

It can be observed from all the protocols explained in the chapter that two main processes are involved within each protocol run. The first is authentication and the second is the establishment of a new session key. These mechanisms are evident in the Andrew Secure RPC, Needham–Schroeder, secure socket layer, and Kerberos protocols. Let us, therefore, talk a little bit about them here.

In early literature, all protocols concerned with setting up a new session key were commonly referred to as authentication protocols. However, many researchers and security practitioners did not think that this was satisfactory. It has since been suggested that the two mechanisms should be clearly distinguished between them. In other words, protocols that provide the process of identity confirmation or verification are to be called entity authentication protocols , while protocols that involve the process of setting up a new key are to be known as key establishment protocols .

We have already learned that the goal of authentication protocols is to confirm the identity of an entity. That is, an authentication mechanism is carried out in order to ensure that the entity is really who the entity claims to be. A key establishment protocol is something that we have not really formally come across before. Fortunately, we have seen that it is an important part of many of the existing protocols. Its goal is different from that of authentication in that key establishment protocols must generate a fresh session key, which is known only to the protocol participants and possibly some trusted third parties. What it means is that a key establishment protocol is aimed to set up a new key every time a protocol is executed in such a way that the key is fresh and unknown to unauthorized entities.

Even though authentication and key establishment are two very different processes, many researchers, including Whitfield Diffie and Martin Hellman, who are considered the gurus of the field, suggest that both mechanisms should be considered jointly, rather than separately. The claim has been supported by Mihir Bellare and Phillip Rogaway, another two cryptography experts, who have said that“an entity authentication is rarely useful in the absence of an associated key distribution (establishment), while key distribution (establishment), all by itself, is not only useful, but it is not appreciably more so when an entity authentication occurs alongside.”

Let us consider what those claims mean for a moment. Basically, when an authentication process is done without key establishment, the entities involved in the process are certain of the other party’s identity. The problem is without a newly established session key, there is a question of how these entities will be able to securely communicate with one another. Conversely, if a key establishment process is carried out without authentication, it will mean that the protocol principals will have no idea who they are communicating with. In other words, it is possible that a key is established with an unknown entity, which could also be an attacker. This would, therefore, be against the aim of a key establishment protocol which states that the key must only be known by authorized entities. However, in this non-authentication case, we have no idea who is participating in the protocol session. This is why it is common to have both authentication and key establishment mechanisms in a protocol run, usually in that order, so that the protocol entities are first certain of the identities of other entities prior to setting up a fresh session key. Hence, today’s protocols are known as authentication and key establishment protocols.

Due to the fact that it appears possible to design an authentication and key establishment protocol with vulnerabilities, especially with potential replay and man-in-the-middle attacks as well as lack of message confidentiality and integrity, it is essential to have principles that can be followed so that the risk of exposing protocol weaknesses can be reduced. We think it would be better to categorize these principles into two separate groups, which are specific principles and generic principles. No matter what group they belong to, it is recommended that when designing a protocol, these principles should at least be considered.

Generic Principles

Over the years, many authentication and key establishment protocols have been designed and implemented. Many have been in use in real-world situations. However, some are admittedly not very secure, as already seen in the classic protocols in the previous sections. This section, therefore, provides an attempt to present design principles for authentication and key establishment protocols. These principles have been gathered by security researchers, especially by Martin Abadi and Roger Needham, with an aim of having them as a basic guideline so that previously made mistakes can be avoided.

It has been evident that many authentication and key establishment protocols apply either symmetric or asymmetric cryptography. Hence, the very first thing that we would like to state is that protocol designers must choose provably secure encryption algorithms as part of their protocol. For example, AES should be considered rather than DES for symmetric encryption. For asymmetric cryptography, RSA is still claimed to be secure with Elliptic Curve Cryptography (ECC) being a possible alternative. As for cryptographic hash functions, MD5 and SHA-1 should probably be avoided since collisions can potentially be found. The SHA-2 family such as SHA-256 or SHA-512 or even the upcoming SHA-3 should be considered instead. These are just examples for more secure cryptographic algorithms that should be applied in authentication and key establishment protocols. What we will do next is to get into the generic design principles to help avoid previously published blunders.

Principle 1: Importance of message meaning

Every message of the protocol should say what it means. In other words, the meaning or the interpretation of each message should be from the components of the message. Assumptions should not have to be made by any entities. Protocol entities should be able to understand what each message means by the message itself. Moreover, it should be possible to express or explain each protocol message in plain written or spoken language.

For example, a server S may want to transmit a message to an entity A which is intended to be interpreted as “the server S sends to an entity A a secret key K, which is to be used for communications with another entity B.” This first principle recommends that every element that is necessary for this interpretation must be included in the message. This is so that the recipient, in this case A, can understand the intention without having to wait for any other messages.

In addition, it has been said that the trust in the message really depends on the elements within itself as well as previously received components. Therefore, every message must contain correct and complete components so that it is adequate to communicate the true intention of the sender.

Principle 2: Clear condition for protocol messages

The condition for a protocol message to be acted upon must be clearly specified so that any future protocol inspection can decide whether or not this particular condition is acceptable.

This second principle follows on from Principle 1. For a protocol message to be acted upon, purely understanding the meaning of the message is not enough. Any condition necessary for the correct protocol function must also hold. It is essential for protocol designers to express that a protocol message will only have an impact upon the protocol if this condition is true.

For example, in an authentication and key establishment protocol, one condition is intended by a protocol designer that a secret key K to be used in communication by entities A and B must be generated by a server S. Therefore, if there are messages in the protocol which suggest that K is generated by any other entities other than S, then these messages will not have any impact or influence on the protocol. This is because the specified condition has not been correctly followed.

Principle 3: Identification of protocol principals

If the name of an entity or the identity of the protocol principal is essential to the meaning of the protocol message or the authentication and key establishment on the whole, it is important to explicitly specify that identity in the protocol message.

In authentication and key establishment protocols, it is necessary to explicitly state the identity or identities of protocol participant or participants involved in a protocol run. In many cases, not specifying the identities can lead to potential attacks on the protocol, especially the man-in-the-middle attack and impersonation attack. This can simply be illustrated as follows.

Suppose that principals Alice A and Bob B are involved in an authentication protocol with Alice and Bob trying to authenticate one another. This is done by proving to one another that they possess the same secret key K_AB, which is the symmetric key shared between Alice and Bob. First, Alice sends a message to Bob saying that she is Alice, along with her nonce value Nonce_A. When Bob receives the message, he encrypts the component Nonce_A with the key K_AB shared between Alice and Bob. The ciphertext is transmitted to Alice together with Bob’s nonce value Nonce_B. Once Alice receives the message, she first decrypts the ciphertext to examine whether or not the resultant plaintext matches with Nonce_A she has generated and sent earlier. If they match, Alice knows that Bob shares the same key as hers. She then encrypts the component Nonce_B with the key she holds and sends the ciphertext to Bob. Finally, Bob decrypts the message to see whether or not the resultant plaintext matches with his Nonce_B. If so, Bob knows that Alice possesses the same key as his. This mutual authentication process can be expressed as follows:

where Nonce_i is the nonce value of an entity i,

K_AB is the symmetric key shared between Alice and Bob, and

is when a message M is being encrypted with the key K_AB.

It can be seen in the protocol that no identities of any of the protocol principals are specified in any of the messages. The problem with this is that the preceding protocol is vulnerable to an impersonation attack which can be explained in the following way.

Suppose there is an attacker called Charlie C who wants to impersonate Alice A. The attack begins with the first two messages that are the same as a normal protocol run, but this time, the first message is initiated by Charlie who begins his process of pretending to be Alice. When Charlie receives the second message from Bob B, of course, it is not possible for Charlie to encrypt Nonce_B because he does not possess the key K_AB. What Charlie can do here is start a new authentication session with Bob. During the new session, Charlie sends Nonce_B to Bob, who will follow the protocol by encrypting it and sending the ciphertext back to Charlie. Charlie, having received the ciphertext of Nonce_B, goes back to the first session and sends the ciphertext back to Bob. Bob will believe that Charlie possesses the same key as his and, therefore, will think that he is really communicating with Alice. As a result, Charlie has successfully impersonated Alice. Charlie’s attack can be expressed in the following manner:

Message 1: Charlie → Bob : I ^′m Alice, Nonce_A

Message 2:

Charlie begins a new session.

Message 3: Charlie → Bob : I ^′m Alice, Nonce_B

Message 4:

Charlie goes back to the old session.

Message 5:

where Nonce_i is the nonce value of an entity i,

K_AB is the symmetric key shared between Alice and Bob, and

is when a message M is being encrypted with the key K_AB.

The impersonation attack done in the way Charlie does in the preceding protocol works because there are no identities of the protocol principals in the protocol messages. That means that an easy way to solve the problem and thus to prevent such impersonation attack is to include the identity of the sender in the message as follows:

where Nonce_i is the nonce value of an entity i,

K_AB is the symmetric key shared between Alice and Bob, and

is when a message M is being encrypted with the key K_AB.

After stating the identity of the message sender, it is now not possible for Charlie to carry out the same impersonation attack on the protocol. This is evident that Charlie cannot use the ciphertext he receives from Bob in Message 4 (in the attack) and uses it to reply to Bob, because Bob will see his own identity in the message and knows that Charlie is not the one who encrypts the message. Hence, Charlie’s impersonation attack is unsuccessful.

Principle 4: Needs for encryption

It needs to be precisely clear why encryption is being used in the authentication and key establishment protocol. This is because encryption is not synonymous with security and not a computationally cheap process. An improper use of encryption could lead to a vulnerability and unnecessary computation.

There are many objectives to encryption. Protocol designers must clearly express their reasons why encryption is done and what it is used for. Examples of encryption uses include:

• Encryption is used to preserve confidentiality of information. In this case, the message recipient must possess the correct key in order to decrypt the message.

• Encryption is used to show authenticity of the message. In this case, the message does not necessarily need to be a secret. However, the sender encrypts it to show that the message is really from a trusted entity. If symmetric cryptography is used, the sender simply encrypts it with the key they are holding. If asymmetric cryptography is used, the sender’s private key is used in the form of digital signature.

• Encryption is used to produce random numbers. Some authentication and key establishment protocols, specifically the ones that apply a challenge-and-response mechanism, require the generation of random numbers or nonce values. Encryption can be used as a method to produce such numbers.

As already stated previously, because there are several objectives that encryption can be used to achieve, protocol designers must be clear to what encryption is used for. Some even suggest that an inappropriate use of encryption could actually lead to protocol errors. Furthermore, improper implementation of encryption algorithms could lead to protocol vulnerabilities waiting to be exploited by adversaries.

Principle 5: Inconclusiveness of message content knowledge

When a protocol entity digitally signs an encrypted message containing data, the recipient should not conclude that the sender knows the content of the message.

This can be explained with a simple example. Suppose that Alice A transmits a message M encrypted with Bob’s public key along with her signature to Bob B. Bob is the only one who can decrypt the message since the decryption process requires the use of Bob’s private key. The signature part can also be verified by Bob using the public key of Alice. The message that Alice sends to Bob can be written as

where is when a message M is encrypted with the public key of an entity i,

H(M) is the hash value of a message M, and

is the digital signature of an entity i on a message M.

In this case, Bob should not automatically believe that Alice knows what M actually is. For example, if M is some secret message or even a password, Bob cannot be certain that Alice knows it. As for the hash value of the message H(M), it is always possible that Alice may have received it from someone else. It is even worse when Alice sends the following message:

where is when a message M is encrypted with the public key of an entity i,

H(M) is the hash value of a message M, and

is the digital signature of an entity i on a message M.

It can be seen that all Alice does is that she takes the encrypted message , hashes it, and then signs it with her private key. In this example, Alice could have intercepted , signed it, and transmitted the message with her signature to Bob. It is, therefore, not wise for Bob to immediately be certain that Alice knows the content of the message.

One way to solve this issue is perhaps for the sender to sign the message with their private key before encrypting it for confidentiality.

Principle 6: Freshness of protocol messages

The entire or a part of a message transmitted between protocol principals must be fresh.

This principle ensures the freshness of protocol messages, which is important because freshness can help prevent a form of attack known as a replay attack. An example of a replay attack can be referred back to Figure 7-1. It can be simply described as the retransmission of previously used messages. Of course, one way to reduce the risk of being attacked by a replay is the use of cryptographic nonce. A cryptographic nonce or a nonce can be used to guarantee the freshness of each protocol message, usually also through a challenge-and-response mechanism. However, one thing to be considered is the protection of the nonce. This is especially the case if a predictable form of cryptographic nonce is used. It is, therefore, recommended that the nonce is protected so that an adversary cannot simulate the challenge as well as the response.

Cryptographic nonce is not the only method that can be used to prove the freshness of protocol messages. Another method is the application of timestamps. Many protocol designers prefer timestamps because they think that it is easier to use the time than to produce a random number for a nonce. However, a couple of things need to be considered when using timestamps. Firstly, the clocks on the sender and the recipient’s machines have to be synchronized so that when the message is received, the time of the message generation can be correctly inspected. This is by and large the case for Kerberos whose mechanism depends so much on timestamps. Secondly, if the synchronization of the clocks on the machines involved in the protocol cannot be perfectly done, the difference of the time should not be larger than the allowable age of the message. Otherwise, a replay attack will be possible if an adversary retransmits a message within the time interval. Hence, if the allowable age of the message and the time difference between the clocks are too large, it becomes more likely that a replay attack will be a success.

Before ending the section and chapter, there is one other point that we would like to emphasize. That is, the secrecy of some information in protocols is essential to their functioning. This is mainly true with cryptographic keys used for encrypting and decrypting purposes. Protocol designers need to be aware that losing such information could easily lead to the loss of confidentiality, integrity, and authenticity of protocol messages.

On the whole, what has been learned from many existing authentication and key establishment protocols can be extracted to become the six basic principles that we can follow. They are not absolute in any means. They simply provide suggestions for protocol designers to consider so that the same mistakes as the vulnerable classic protocols are not made in future authentication and key establishment protocols.

Summary

Many authentication protocols have been designed, implemented, and applied in real-world situations. Their importance will only increase in the future. We, therefore, think that there is a need for us to learn from other existing protocols so that more secure protocols can be designed.

The chapter begins with an explanation of what an authentication protocol is and how it is related to the process of session key establishment. We have given several examples of what we consider classic authentication and key establishment protocols in Andrew Secure RPC Protocol, Needham–Schroeder protocol, and Needham–Schroeder Public Key protocol. All of them have become major influences for today’s authentication protocols. Furthermore, secure socket layer and Kerberos, the two most commonly used authentication and key establishment protocols today, have also been explained in this chapter.

The mistakes and vulnerabilities that were made in the classic protocols and the way that secure socket layer and Kerberos work are then turned into protocol design principles. These principles can be considered as a basic guideline for authentication and key establishment protocol designers so that fewer vulnerabilities will be present and more resilient authentication and key establishment protocols can be proposed in the future.

Bibliography

Abadi, M., & Needham, R. (1994). Prudent Engineering Practice for Cryptographic Protocols. Proceedings of 1994 IEEE Computer Society Symposium on Research in Security and Privacy (pp. 122–136). IEEE.

Boonkrong, S. (2010). Some Remarks on Andrew Secure RPC. Proceedings of the 10th International Conference on Innovative Internet Community Systems (I2CS). Bangkok: Gesellschaft fur Informatik.

Boonkrong, S. (2011, June). Designing Cryptographic Protocols (in Thai). Journal of Information Technology, 7(1), 52–57.

Boonkrong, S. (2014). A More Secure and Efficient Andrew Secure RPC Protocol. Security and Communication Networks, 7(11), 2063–2077.

Boyd, C., Mathuria, A., & Stebila, D. (2003). Protocols for Authentication and Key Establishment. Springer.

Clark, J., & Jacob, J. (1995). On the Security of Recent Protocols. Information Processing Letters, 56(3), 151–155.

Gong, L., Needham, R. M., & Yahalom, R. (1990). Reasoning about Belief in Cryptographic Protocols. Proceedings of the IEEE Symposium on Security and Privacy (pp. 234–248). IEEE.

Hickman, K. E. (1994). The SSL Protocol. Netscape Communications Corp. IEFT.

Lampson, B., Abadi, M., Burrows, M., & Wobber, E. (1992). Authentication in Distributed Systems: Theory and Practice. ACM Transactions on Computer Systems, 10(4), 265–310.

Linn, J. (1996). RFC1964: The Kerberos Version 5 GSS-API Mechanism. USA: IETF.

Oppliger, R. (2009). SSL and TLS: Theory and Practice. USA: Artech House, Inc.

Satyanarayanan, M. (1989). Integrating Security in a Large Distributed System. ACM Transactions on Computer Systems, 7(3), 247–280.

Steiner, J. G., Neuman, C., & Schiller, J. I. (1988). Kerberos: An Authentication Service for Open Network Systems. Proceedings of USENIX Conference, (pp. 191–202).