10.1 Public Key Extensions

Kerberos was designed when public key encryption was still in its infancy. Public key algorithms were not widely in use at the time, the technology was heavily patented by RSA Security, Inc., and the computing power commonly available at the time was not sufficient to sustain a large public key infrastructure. Today, these factors have changed: the patents on the popular RSA public key algorithm have expired, opening the door to royalty-free implementations of RSA, and Moore's law of exponential growth in computing speed has provided more than enough computing power to handle the large calculations involved in public key cryptography. The development and wide deployment of the Secure Sockets Layer (SSL) and its successor, Transport Layer Security (TLS), which use public key cryptography primarily for securing communication with web sites, have proven that public key cryptography is useful and can be trusted for secure systems.

The question is, then, what benefits can the introduction of public key cryptography bring to Kerberos? To answer this question, we need a clear understanding of what makes public key cryptography different from traditional, private key cryptography.

10.1.1 Public Key Cryptography

Traditional cryptographic systems require the sender and recipient to share a common secret key to communicate securely. The sender uses the secret key to encrypt messages to the recipient, and the recipient uses the same secret key to decrypt the incoming message. This is known as symmetric, or private key cryptography, and is the type of cryptography used by the Kerberos protocol. The problem, of course, is how the two parties agree on and communicate the secret key. This problem is generally known as key management, and is a crucial factor in the practical operation of any encryption scheme. Key management affects all encryption algorithms, regardless of their strength, and a compromised key in a relatively weak cryptosystem has exactly the same consequences as a compromised key in a relatively strong cryptosystem—namely, that all communications using that key are now easily decrypted by an attacker. Implementers of private key cryptosystems typically address the key distribution issue by using some form of personal contact between sender and recipient prior to the first message exchange to establish a secret key; for example, users requesting access to a Kerberos-protected network may have to apply for an account and receive an initial password from a system administrator in person. This process becomes unwieldy in a large environment; however, a different type of cryptographic algorithm provides another approach to the problem of key management.

Public key, or asymmetric key cryptography splits the encryption key into two parts. Each user in a public key system generates a key pair, consisting of a private key and public key. These two keys are mathematically linked so that messages are encrypted with one key and decrypted with the other. Furthermore, deriving one half of the key given the other half is mathematically very difficult, and the difficulty of performing this operation determines the relative strength of public key encryption algorithms.

The two parts of the encryption key are termed the private key and the public key. The private key is kept secret, and the public key is widely distributed to everyone that you wish to communicate with. When someone wants to send you an encrypted message, he encrypts the message with your public key. Once encrypted, the only person who can decrypt the message is the person who holds the other half of the key—the private key—which is securely stored on your computer. This demonstrates the advantage of key distribution that public key cryptography has over symmetric cryptography. Each participant simply publishes her public key, and we no longer have to worry about key distribution.

In addition to encryption, public key cryptography also provides a method for electronically signing messages. This is accomplished by simply reversing the keys involved in the encryption and decryption process. To sign a message, the sender encrypts it with his private key, and to ensure its authenticity, the recipient can decrypt it with the sender's public key. If the message is decrypted successfully with the public key of the sender, then the recipient is assured of the identity of the sender, as only the sender could have encrypted the message with his private key.

With all of these advantages over symmetric key cryptography, there must be some downsides to the use of public key cryptography. As it turns out, there are a few disadvantages of public key algorithms, but with some extra work, they can be overcome. The first issue with public key cryptography is its speed. Current public key algorithms require mathematical operations on numbers hundreds of digits long, which, even with today's processing power, can present a large performance penalty when encrypting large amounts of data. The second problem is related to the very issue that public key cryptography purports to solve: the problem of key distribution. The issue at hand is, while everyone can publish their own public key, and others can encrypt messages intended for a particular recipient with that person's published public key, how does the sender know that someone's published public key is really his public key?

10.1.1.1 Combining public key and symmetric key ciphers

To solve the first problem, we need to combine the power and flexibility of public key cryptography with the speed of symmetric key cryptography. Today's security products and protocols, such as PGP and SSL, use a hybrid approach that combines the use of both. First, a public key algorithm is used to encrypt a small amount of data, namely, an encryption key. This encryption key is then used to encrypt the remainder of the message using a traditional symmetric key algorithm. Through this approach, we combine the key management advantages of public key cryptography yet use a symmetric key cipher to encrypt the bulk of the message, leveraging the better speed of the symmetric key cipher.

This combination of methods does not lessen the strength of the resulting cipher. Instead, it uses each type of encryption's strength to its advantage. Since conventional symmetric key cryptography is much more efficient than public key algorithms, the use of symmetric key algorithms provide the speed and low CPU usage required for encrypting and decrypting large amounts of data. The public key algorithms excel at easy key distribution and so they are used to negotiate a secret key to be used for the subsequent symmetric key algorithms.

10.1.1.2 Public key cryptography key distribution

It turns out that the public key's principal strength (the ease of key distribution) is also its Achilles's heel. Since anyone can publish a public key, nothing stops an attacker from creating a key pair, keeping the private key, and publishing the public key under someone else's name. When someone encrypts a message in what she thinks is the victim's public key, the attacker is able to decrypt and read it instead. Furthermore, if the attacker has the intended recipient's real public key, the attacker can re-encrypt the message with the correct key and forward it on to the recipient without the recipient being aware that the message was intercepted.

This is a man-in-the-middle attack, similar to the man-in-the-middle attacks that we examined in Chapter 6. To prevent this attack, let's say that the original sender now signs his message, in addition to encrypting it, before sending the message to the recipient. This seems to solve the attack above, as now the attacker can't re-sign the message when forwarding it on to the recipient. But the problem still exists, only in reverse: how does the recipient know the true sender's public key? Furthermore, the most common implementation of public key cryptography in use on the Internet today, SSL, does not require the use of mutual authentication, as most users do not have a key pair.

One solution to this problem is called key certification. Before someone publishes their public key, he sends it to a Certification Authority (CA) whose job is to ensure that the person is genuinely who he says he is. The CA then signs the person's public key, which functions as a seal ensuring that the key does, in fact, belong to the person. The public key, along with the signature from the CA, and some identifying information such as the person's name, are all combined into one file, called a certificate. Of course this requires centralized control to determine the validity of signature requests and sign valid requests. This system of a centralized certificate signing authority is also referred to as a Public Key Infrastructure, or PKI.

Another, more decentralized approach, is taken by the package Pretty Good Privacy (PGP). In PGP, users generate their own key pair and have the public key signed by people they personally know. Multiple people can sign a single key, indicating that each signer vouches for the authenticity of the target's key.

10.1.2 Initial Authentication (PKINIT)

One situation where public key cryptography can benefit the Kerberos protocol is in the initial Authentication Server exchange. Instead of sharing a secret key between the client and KDC, the client possesses a public key pair that is signed by a Certification Authority, which is used to authenticate to the realm.

The key certification method described in the previous section may seem similar to the trusted third party system employed by Kerberos, and, in fact, it is very similar—with one important distinction. The difference is that while both Kerberos and public key certificate authorities employ a trusted third-party model, the trusted third-party is only involved in the public key method when signing the public keys. The rest of the time, the certification authority operates offline; that is, it doesn't have to be actively involved every time an authentication request is made.

The typical use of PKINIT is to provide each user in the Kerberos realm a signed public key certificate. Each user on their workstation generates a public/private key pair, and the public key is presented to a Certification Authority for validation. Once the key is signed, the certificate is returned to the user and stored on the local hard drive.

The only change to the Kerberos protocol is in the initial Authentication Server message exchange between the authentication client and the KDC. In the traditional symmetric key Kerberos protocol, the client requests a TGT from the KDC, and the KDC responds with a TGT encrypted with the user's secret key. If the realm requires pre-authentication, the user must supply a timestamp encrypted with the user's secret password (or other authenticator) to the KDC, providing reasonable proof that the client is genuine.

PKINIT extends the Kerberos protocol by using the pre-authentication field to house a public key certificate instead. When a user wishes to authenticate to a KDC that supports PKINIT, the user places his certificate in the pre-authentication field of the AS request. The KDC receives the request and returns the validated TGT encrypted with the public key contained within the user's public key certificate.

Of course, we don't want to simply issue everyone who has a public key pair a valid TGT to use our Kerberos network. Therefore, the KDC will validate the signature included in the user's certificate to ensure that a trusted Certification Authority signed the user's key. In addition, the client can validate the KDC's certificate included in its reply to the client, and determine whether it deems the KDC trustworthy or not. Once the initial AS request/response is finished, the remaining Kerberos protocol exchanges are unchanged. The TGT contains a conventional symmetric session key that can then be used to obtain tickets for further Kerberos resources.

10.1.3 Cross-Realm (PKCROSS)

PKCROSS simplifies the management of cross-realm relationships between Kerberos realms. Traditional cross-realm relationships in Kerberos require the participating realms to share secret keys, which imposes the key management problems inherent in symmetric key cryptography. Namely, secret keys must somehow be securely transmitted to each of the participating Kerberos KDCs. PKCROSS uses public key cryptography to eliminate the need for KDCs to share secret keys and allows for more scalable Kerberos cross-realm relationships.

From a client's perspective, communicating with two realms that use PKCROSS for cross-realm communication is exactly the same as communicating with two realms that use traditional Kerberos cross-realm shared keys. The operation of PKCROSS is entirely transparent to end users.

The PKCROSS extensions, instead, define a communication between the two KDCs involved in the cross-realm relationship. This is a major departure from traditional Kerberos protocols; no other Kerberos protocol exchange occurs between a KDC and another KDC. However, in this case, the direct KDC-to-KDC communication represents an elegant solution to public key cross-realm authentication. This way, Kerberos clients do not have to support public key encryption in order to communicate with realms that use PKCROSS for cross-realm authentication.

When a client requests a cross-realm TGT for two realms that support PKCROSS, the local KDC acts as a Kerberos client and requests a special cross-realm TGT from the remote realm's KDC. This process works much like the PKINIT process, except the role of client is played by the local realm's KDC.