6.2 Protocol Security Issues

First, let's revisit the underlying reason why the Kerberos protocol was developed. Kerberos was designed to protect authentication data from passing over a network in the clear. Before Kerberos, when a user wished to log into a remote service, the client software would pass the user's credentials (a password) to the server in clear text. Since networks are broadcast mediums, where every station connected to a network segment can "hear" all traffic on that segment, sending passwords in the clear over a network is extremely insecure. Therefore, Kerberos encrypts all authentication exchanges that occur over the network. Encryption is only part of the solution, however, and the designers of Kerberos have put much thought into ensuring as secure a system as possible. In this section, we'll explore several attacks against the distributed authentication systems, such as Kerberos. We'll also discuss the particular techniques that Kerberos employs to mitigate the threats posed by these attacks.

6.2.1 Dictionary and Brute-Force Attacks

In the original Kerberos 4 protocol, the KDC issues an encrypted TGT to any client that requests it. Recall from Chapter 3 that this TGT is encrypted with the user's secret key (derived from her password). The security of the entire system is dependent on not being able to decrypt this message, since if an attacker is able to retrieve the key used to encrypt the message, he now has the user's password and can impersonate that user at will. Therefore, if an attacker wishes to obtain a user's password, he can ask the KDC for a valid TGT for the victim's username. While there are no ways to break the encryption methods used in Kerberos tickets directly, the attacker can then continue to brute-force the decryption of the TGT by launching an offline dictionary attack.

During a dictionary attack, an attacker feeds a list of commonly used passwords, or a dictionary, to a cracking program. For each entry in the dictionary, a program attempts to decrypt the message using the password. If a hit is made, the program reports back to the attacker the user's password.

Since the transformation from the user's password to the encryption key is known (the string-to-key transformation covered in Chapter 3), it is trivial for an attacker to build a program that can translate common passwords into Kerberos encryption keys. Then, the attacker collects a large number of valid TGTs from the KDC and continues the work of cracking the TGTs off-line; that is, for each decryption attempt, he does not have to contact the KDC. Instead, once these TGTs are acquired from the KDC, no further communication is necessary to attack the passwords.

This method is made possible since there is a known plaintext included in the TGT, namely the string "tgt" itself. The Kerberos Ticket Granting Service principal name is always "krbtgt," and that principal name is the signal that indicates a successful decryption. By the time the attacker has successfully determined the password, the now unencrypted ticket has expired; however, the attacker now has a valid username/password combination to the Kerberos server and can obtain new tickets using that valid username and password.

Code is available to perform this attack against Kerberos 4 KDCs via a patch to the password cracker program John the Ripper. The code is available from Dug Song's web site at http://www.monkey.org/~dugsong/john-1.6.krb4.patch-3.

A dictionary attack forms a lower bound on the security of any password-based authentication system. No matter what kind of fancy encryption scheme is utilized, if the user's password is a simple, easily guessed word, then it will quickly succumb to a dictionary attack. Another attack, the brute-force attack, forms an upper bound on the security of Kerberos. Instead of attempting to decrypt messages by iterating over words in a pre-defined dictionary, a brute-force attack tries every encryption key, one by one, until the right key is found. Cryptosystems are designed with a large key space to make brute force attacks impractical. However, with the very fast pace of technology, key spaces that were once considered impractical to search are now within the grasp of even a moderately motivated attacker.

The encryption used in Kerberos v4, as well as the most common encryption type in Kerberos v5, is single DES. Single DES, designed in the late 1970s, has a 56-bit key length. When Kerberos was designed (in the late 1980s), brute-forcing a 56-bit key was not practical given the speed of the processors available. By today's standards, the 56-bit key space of single DES is considered relatively insecure. In 1998, the Electronic Frontier Foundation demonstrated that with a $200,000 investment, a determined attacker can build a specialized "DES cracker" which can brute-force the encryption key from a DES message within a matter of days.^[1] With the processing power available today (in 2002), the time to decrypt a message encrypted using single DES has fallen into the range of a couple of hours. The most dramatic demonstration of the fallibility of DES came on January 19, 1999, when distributed.net cracked a 56-bit DES key in 22 hours,^[2] using the spare cycles of thousands of computers worldwide and the EFF DES cracker in tandem.

^[1] http://www.eff.org/descracker.html

^[2] http://www.distributed.net/des/

Bits and the Strength of Cryptosystems When reading about symmetric key cryptosystems such as DES, numbers of "bits" of encryption are invariably mentioned. However, what exactly does a "56-bit key" mean? How long would it take to try every key? What about a 128-bit key? The number of bits in a cryptosystem's key represents its key length, or the number of possible encryption keys that the cryptosystem can handle. DES, for example, has a 56-bit key length. That means that there are 256, or 72,057,594,037,927,936 possible keys. While that seems like a large number, a network of off-the-shelf personal computers can search that key space in the matter of only a few weeks. For the more determined attacker, specialized machines such as the DES cracker can be built to speed the process along. Since the number of keys grows exponentially with the number of bits in the key, a key length of 57 bits has twice the number of keys than a 56-bit key length. So, a 128-bit key contains more possible keys than there are protons in the visible universe. Brute-forcing that key with current computer technology would be impractical, to say the least. Finally, when comparing the strength of cryptosystems, the key length of symmetric key cryptosystems such as DES and triple DES cannot be compared directly with the key length of asymmetric key (or public key) cryptosystems such as RSA. Roughly speaking, a public key algorithm with a 512-bit key length is equivalent to a 56-bit key length in a symmetric key encryption algorithm.

Thankfully, in Kerberos v5, some new protocol features were introduced to mitigate this threat. First is the extensible encryption type support, which allows for the addition of stronger encryption techniques as computer power continues to grow. In addition, pre-authentication was added, which forces a client to prove their identity before the KDC issues encrypted tickets to the client. Pre-authentication limits the problem of an offline brute-force or dictionary attack. Instead, a remote attacker must contact the KDC every time she attempts a new password.

However, Kerberos v5's new encryption type support and pre-authentication features do not completely solve the dictionary and brute-force attacks. New encryption types will undoubtedly make a brute force attack less viable by increasing the difficulty of brute-forcing an encrypted message by many, many orders of magnitude. However, all servers, clients, and KDCs on the network must support new encryption types. If, for example, you have many different Kerberos client and server implementations installed across your network (for instance, a set of MIT Kerberos servers along with some Windows clients), you can only use a common encryption type supported by all machines in your network. MIT supports triple DES keys, but Windows does not, so communications between Windows- and MIT-based Kerberos implementations will be limited to single DES. The upcoming 1.3 release of the MIT Kerberos 5 distribution will support the RC4 cipher used by Windows, and therefore strengthen the encryption used for communications between the two implementations.

With pre-authentication in place, an attacker can no longer obtain valid, encrypted tickets on request from the KDC. However, the attacker can instead use a network "sniffer" to obtain KDC responses as they are sent through the wire to clients. These responses will include tickets encrypted with client's keys. While the attack has increased in difficulty by an order of magnitude, it is still a potential problem. In addition, most implementations of Kerberos (notably MIT) do not force clients to use pre-authentication by default, negating the security benefit that pre-authentication would provide.

6.2.2 Replay Attacks

Another attack that can be mounted against Kerberos is known as a replay attack. Since all protocol exchanges are simply electronic messages that are sent over a computer network, an attacker can listen to the network messages involved in a successful authentication exchange, make a copy of the messages, and replay them at a later time. The attacker doesn't need to guess the users' password or decrypt any messages in this scenario. Since the replay attack requires access to listen to all network messages as well as the ability to send fake messages, a replay attack is an active attack. A theoretical replay attack is pictured in Figure 6-1.

Figure 6-1. Kerberos replay attack

In this figure, we see that Alice (the innocent end user) successfully obtains tickets to authenticate to her mail server. Bob, the evil hacker, is surreptitiously listening to all network traffic between Alice, the mail server, and the Kerberos KDC. Bob cannot directly use the TGT that Alice requests in the first step, since the TGT must be decrypted with Alice's password, which Bob does not know (although he can certainly try to brute-force the password, as discussed in the previous section). However, when Alice sends her encrypted ticket and authenticator, Bob can intercept that message and replay it to impersonate Alice to the mail server.

The ticket is encrypted with the mail server's key, and the authenticator is encrypted with the session key shared between Alice and the mail server. When the mail server receives the ticket and authenticator, it decrypts the ticket with its key, retrieves the session key from the ticket, and uses the session key to decrypt the authenticator. If all decryptions are successful, then authentication succeeds.

Kerberos has several built-in protections to prevent successful replay attacks. As an administrator, you do not have to worry about enabling any of these protections; they are built in to the particular Kerberos implementation that you're using. These protections are:

Address field in tickets

When a client requests a ticket from the KDC, it lists the network addresses from which the ticket is valid. For example, if the IP address of the workstation is 192.168.1.1, the workstation would fill that address in the address field in the ticket request, and the KDC would copy that into the ticket it returns to the workstation. This protection solves the problem of an attacker who attempts to replay a valid ticket on a workstation not listed in the ticket's address field. However, this protection is not enough to completely thwart replay attacks; the address field may be left blank, and the ticket would be valid for all addresses. Or, if the attacker had access to a machine listed in the addresses field, he could login and replay the ticket from there.

Time-based authenticators

Since address-based security is imperfect, Kerberos employs another scheme to thwart replay attacks. Every time a client wishes to use a Kerberized service, she generates an authenticator, which is submitted with the ticket to the service for authentication. The authenticator contains nothing but a timestamp, encrypted with the session key generated by the KDC for this particular ticket exchange. When the service receives this authenticator, it checks the decrypted timestamp against its system clock. If the two times differ by more than five minutes in either direction, the service will reject the ticket and refuse to authenticate the user. The 5-minute time period is designed to allow for some variation between different clocks on the network. However, even five minutes may be more than enough time for an attacker to replay valid tickets, especially if he employs an automated program to capture and replay tickets.

Replay caches

The last line of defense that Kerberos has against replay attacks is the replay cache. Both the Kerberos v4 and v5 protocols include the time-based authenticator. Kerberos v5 introduces the replay cache to avoid attackers reusing tickets in the short time period that authenticators are valid. Every Kerberized service maintains a cache of the authenticators it has recently received. When the service receives an authenticator, it checks the replay cache. If the service finds a copy of the authenticator already in the replay cache, it rejects the request. Otherwise, the service accepts the request and adds the authenticator to the replay cache to validate further requests.

6.2.3 Man-in-the-Middle Attacks

Finally, a man-in-the-middle attack affects most any protocol that attempts to verify the identity of connection endpoints (in this case, a user and the machine they wish to reach). A man-in-the-middle attack is an active attack, meaning that the attacker must be able to read all messages on the network as well as send out arbitrary messages of his own design.

The goal of the man-in-the-middle attack is to impersonate the server, resulting in the user thinking that he connected to the legitimate server, when in fact he is talking to the attacker. Once the attacker has control of the session, she can act as a simple pass-through (passing messages between the user and the legitimate server, without modification), or she can actively inject, modify, or delete messages between the user and the server. The attacker now is part of the conversation between the user and the legitimate server, and can modify any messages that pass through her, hence the name "man-in-the-middle."

The good news is that the Kerberos protocol has built-in protection against man-in-the-middle attacks. Since Kerberos performs mutual authentication, by confirming not only the end user's identity but also the server's identity, man-in-the-middle attacks are thwarted.

To prevent against man-in-the-middle attacks, some mechanism to validate the server's encryption key must exist. Other protocols use manual verification (such as Secure Shell, where the "fingerprint" of the server's public key is printed on the screen when the user first connects), or signing authorities (in the case of SSL-enabled web sites). Kerberos uses the fact that a copy of all of the keys for both services and users are stored on the KDC to ensure protection against man-in-the-middle attacks. Since the session key generated by the KDC and then sent to the service is encrypted with the service's key, an attacker cannot recover the session key without the service's secret key.

A client can then detect whether the server he is talking to is genuine by requesting mutual authentication, where the server must demonstrate her identity by recovering the session key, encrypting a response, and sending it back to the client. If the server is not genuine, and does not have a copy of the service key, then the server cannot send back a valid encrypted message, and the client disconnects.

While Kerberos provides the ability to perform mutual authentication, applications must have code to enable that protection. In addition, several applications, such as the PAM modules available for authentication against Kerberos passwords, do not use the ticket-based authentication process. Instead, they take in a password over the network (hopefully encrypted) and verify it on the server side by asking the KDC for a TGT and then decrypting the TGT. This is where a practical man-in-the-middle attack can be mounted against Kerberos.

In this case, the attacker wants to place herself in between the server and the KDC, so that she can spoof the application server into thinking she is the real KDC. Since KDC requests and responses are simple UDP messages, it is easy for an attacker to send out fake messages that purport to be from the KDC's real IP address. Thus, the attack is carried out through the following procedure:

To prevent this attack, the server must retrieve its host service key from its keytab, and then request a service key from the KDC using the TGT it just obtained on behalf of the user. Since only the server and the KDC know the host service key, an external attacker cannot produce a fake message and the account is denied access.

The KDCspoof program is a practical exploit of this vulnerability, and is available from http://www.monkey.org/~dugsong/kdcspoof.tar.gz.