One-Time Pads

One-time pad authentication requires that both parties have an identical list of pairs of numbers, words, or symbols. The most secure lists are randomly generated. When one party (Alice) requests an interchange with the other (Bob), Bob sends Alice a challenge in the form of one of the items selected from the list. Alice must respond with the corresponding paired item (Figure 1-1). After a challenge has been used, it is crossed off the list and never used again.

The one-time nature of one-time pad authentication makes it impossible for someone to guess the appropriate response to any one particular challenge by a brute force attack—that is, by responding to the challenge repeatedly with different answers until hitting the right answer. Similarly, it is impossible to guess what the next challenge should be. Assuming that the lists are truly randomly generated, the only way to break such a system is to know some portion of the contents of the list of pairs.

For this reason, after the one-time pad has been shared securely, it can be used over insecure communication channels. If someone snoops the communication, they can obtain that challenge-response pair. However, that information is of no use to them, since that particular challenge is never issued again.

The first problem with challenge-response pairs is that generating truly random lists is difficult with computers. Pseudorandom lists are much easier to obtain, and can (in principle at least) be duplicated, given the right algorithm and a good guess at the seed value. The second problem is that this method is useful only if every pair of correspondents has a unique set of lists. Otherwise, it is impossible to determine which holder of the list is authenticating. Finally, as with any shared secret method, the lists must be kept secret when they are shared and stored securely. If one of the lists is obtained by a third party, the method is compromised and the security breach might be undetectable.

Time-Based and Event-Based Authentication

Time-based authentication is a shared secret method in which the secret is changed periodically in a way known only to the two parties involved.

For example, in one variant, both parties begin with the same small set of seed numbers (as few as two or three) and use a mathematical function that calculates a new number from them. Every time interval (for example, once per minute), a new number is calculated from the previous two or three numbers, and the oldest number is discarded.

As long as both parties keep their clocks synchronized and start with the same seed numbers, they can calculate the current authentication number. In order to guard against a third party intercepting enough numbers to calculate the series or authenticating themselves before the number expires, the numbers should be transmitted over a secure communication channel. To further increase security (for example, if the number-generating ID card is lost or stolen), the generated number is combined with a password or PIN known only to the two parties.

As with other shared secret methods, time-based authentication depends on the physical security of the shared secret, and each individual user must have a unique generated number and PIN.

Event-based authentication is very similar to time-based authentication, except that the generation of a new value is triggered by an explicit user action instead of a timer.

In one common variation of this scheme, the user presses a button on a hardware token to generate a new value (computed based on the previous few values).

Whenever someone authenticates successfully, the server stores the last value used for logging in (and the values used to compute it). When the server receives a subsequent request, it computes the next few values in the sequence, beginning with the first value after that stored value (where the exact value of “few” is implementation dependent).

If the user enters one of those computed values, the user is authenticated, and that new value is stored (along with the values used to compute it) for future use.

Kerberos Authentication Process

There are several phases to Kerberos authentication. In the first phase, the client obtains credentials (blocks of data that identify and authenticate an entity) to be used to request access to kerberized services. In the second phase, the client requests authentication for a specific service. In the final phase, the client presents those credentials to the service. Figure 1-2 and Figure 1-3 illustrate this process.

Figure 1-2 shows the first phase, in which the client, labeled Alice in the figure, requests credentials from the Kerberos KDC.

The steps are as follows:

1. Alice looks up the user ID for her username using a directory server.

   Alice then sends a request to the KDC asking for credentials, providing that user ID (in cleartext).

   The KDC gets Alice’s password from the directory server, and applies a hashing function to it, thus turning it into a temporary encryption key. This temporary key is known as Alice’s secret key.

2. The KDC creates an encryption key called a session key for use by Alice the next time she wants to request service from a kerberized server, and encrypts that key with the Alice’s secret key.

   It also creates an identification credential called a ticket-granting ticket (TGT), which contains a copy of the session key encrypted with the KDC’s secret symmetric key (plus other information).

   Both the session key and the TGT include timestamps and expiration times to limit the chances of their being intercepted and used by unauthorized persons.

   The KDC sends both credentials to Alice, along with information about how to transform Alice’s password into her secret key.

   Because Alice knows her password, Alice uses it, along with that hash information, to compute her secret key. Alice then uses her secret key to decrypt the session key and stores it for later. She can’t decrypt the TGT or modify it, but saves it for later use as well.

In the second phase, Alice uses the TGT to request identification credentials from the KDC in order to use a kerberized service, labeled Bob in the figure. Because Alice has a TGT, the KDC does not have to reauthenticate her, so Alice is not asked again for her password.

In the third phase, Alice sends the credentials to Bob, and Bob sends authentication information to Alice. The second and third phases are illustrated in Figure 1-3.

The steps are as follows:

1. Alice sends two messages to the KDC:

   • An authenticator—a request to open a session with Bob that includes the client ID ad a timestamp—encrypted using the session key

   • A message that contains the TGT that the KDC issued earlier

2. The KDC decrypts the TGT and extracts the session key it issued earlier to Alice. (Recall that when the KDC sent the session key to Alice earlier, it was encrypted with Alice’s secret key, so only the KDC and Alice can know this session key.) Because the TGT is encrypted with the KDC’s secret key, it cannot have been altered, and thus the KDC trusts that session key.

   The KDC obtains Alice’s client ID by using the main session key to decrypt the authenticator.

   The KDC then generates a new client-server session key for Alice to use when communicating with Bob, encrypts it with the main session key, and sends it to Alice.

   The KDC also creates a ticket for Alice to send to Bob. This ticket contains a new session key, and Alice’s client ID. This key is encrypted with Bob’s secret key, so Alice (or an intruder) cannot read or modify it. The KDC sends this ticket to Alice.

3. Alice sends the ticket to Bob. Alice also sends a new authenticator (client ID and timestamp) encrypted using the client-server session key.

   Bob decrypts it with his secret key. Because only the KDC and Bob know his secret key, Bob knows the ticket was issued by the KDC. Bob extracts the client-server session key.

   Bob uses the client-server session to decrypt the authenticator. It then sends back a message containing the timestamp from the authenticator plus one, encrypted using the session key.

4. Because Alice knows that only she and Bob have this session key, she knows that the credential must have come from Bob. She checks the value and compares it with the one she received earlier from the KDC. If they are off by one (as expected), she knows that the Bob has been authenticated by the KDC.

Note that this procedure does not involve sending either Alice’s or Bob’s secret key over the network. Because both Alice and Bob are authenticated to each other, Bob knows that Alice is a valid user and Alice knows that Bob is the server with which she intended to do business. All credentials are further protected with timestamps and expiration times. Kerberos has other security features as well; for details, see the MIT Kerberos website at MIT's kerberos page.

Kerberos and Authorization

Kerberos is an authentication protocol, not an authorization protocol. That is, it verifies the identities of both the client and the server, but it does not include any information about whether the client has a right to use the services provided by the server. In terms of the preceding discussion, after Bob is satisfied that the request for services really came from Alice, it is up to Bob to determine whether to grant Alice access to those services. The ticket that Bob receives from Alice contains enough information about Alice to enable Bob to make that determination.

Starting with Kerberos version 5, Kerberos tickets provide a mechanism for the tamperproof transmission of authorization information. When the client requests a ticket, it includes information about itself in the request and can request that the KDC include additional authorization in the ticket. The KDC inserts this information into the authorization data field of the ticket and forwards it to the server. Kerberos does not define how this authorization information should be encoded; it provides only a secure mechanism for its transmission. It is up to the client and server to implement the authorization protocol.

Single Sign-on

macOS uses Kerberos for single sign-on authentication, which relieves users from entering a name and password separately for every kerberized service. With single sign-on, after a user enters a name and password in the login window, the user does not have to enter a name and password for Apple file service, mail service, or other services that use Kerberos authentication. In other words, Kerberos authenticates the user once, and thereafter uses tickets to identify the user.

To take advantage of the single sign-on feature, services must be configured for Kerberos authentication and users and services must use the same Kerberos KDC. In macOS, user accounts in an LDAP directory that have a password type of Open Directory use the server’s built-in KDC. These user accounts are automatically configured for Kerberos and single sign-on. The server’s kerberized services also use the server’s built-in KDC and are automatically configured for single sign-on.

Large Networks

At a high level, you can usually think of the Kerberos Key Distribution Center (KDC) as a single entity. However, a KDC consists of two separate software processes: the authentication server and the ticket-granting server. The authentication server verifies a user’s identity by prompting the user for a name and password and asking the directory server for the user’s password. The authentication server then looks up the user’s secret key, generates a session key, and creates the ticket-granting ticket (TGT), as shown in Figure 1-4.

Thereafter, the user sends the TGT to the ticket-granting server whenever the services of a kerberized server are required, and the ticket-granting server issues the ticket, as shown in Figure 1-5.

Many networks are too large to efficiently store all the information about users and computers in a single directory server. Instead, a distributed model is used, where there are a number of directory servers, each serving a subset of the network. In Kerberos parlance, this subset is referred to as a realm. Each realm has its own ticket-granting server and authentication server. If a user needs a ticket for a service in a different realm, the authentication server issues a TGT and the user sends the TGT to the authentication server, as before. The authentication server then issues a ticket, not for the desired service but for the remote ticket-granting server for the realm that the service is in. The user then sends the ticket to the remote ticket-granting server to get the ticket for the actual service.

In fact, in a large network, the user might have to contact the remote ticket-granting server in a sequence of realms before finally getting the ticket for the desired service. When a ticket for the application service is finally issued, it contains an enumeration of all the realms consulted in the process of requesting the ticket. An application server that applies strict authorization rules is permitted to reject authentication that passes through realms that it does not trust.