Kerberos (thing)

Kerberos is a distributed authentication protocol that originated from the Athena Project at MIT. The protocol identifies users on a TCP/IP network and then authenticates them to application servers. Kerberos is also the name of the program that implements the protocol.

The software and the protocol are both named after the three-headed dog that guards the gates of Hell in Greek mythology.

The idea is to allow users to log in to a single computer, and for all other necessary authentification to occur transparently. It works surprisingly well, and an awful lot happens behind the scenes to make it so.

The idea of single sign-on has recently re-surfaced in MS Passport. Kerberos was first released in 1985. Microsoft wisely adopted a slightly modified version of Kerberos for Windows 2000, and it is now the default mechanism for network authentication.

Whereas Passport is intended to provide transparent authentication across websites, Kerberos authentication is normally built in to FTP, telnet¹ and rlogin daemons, with the initial sign-on normally taking place in the login program, or in a similar location.

For some time, Kerberos the program was unavailable outside of the USA because of export restrictions on strong cryptography. Although the MIT site still refuses to let you download from outside the US, several implementations are available from sites such as wiretapped.net in Australia.

Kerberos shows just how difficult it is to get things right when trying to introduce reliable authentication to computer networks. The principles are fairly simple - the protocol only consists of 5 basic messages - but making it work in practice quickly becomes complicated. That said, Kerberos does make sense, eventually.

Kerberos is currently at version 5. Version 4 was the first to be published - versions 1, 2 and 3 were test-beds.

How it works

• A Kerberos server contains records of all clients.

• A client is generally can be a user or a program that needs access to an application server.

• An application server is any computer that runs services (such as telnet or FTP) that require Kerberos authentication from a key distribution center before they can be used.

• A key distribution server (or KDC) can use information given to the client by the Kerberos server to authenticate the client to various application servers.

This seems arcane, and it gets worse. However, this model allows for central administration of users at the Kerberos server, and compartmentalized administration of applications.

A real-world use case of this:

The system administrator for a company manages users. Each department has their own applications, and manages access control for those applications.

The accounts department manages access to their financial software, while development manages access to source code repositories.

Each department has their own key distribution server (compartmentalization), while the master Kerberos server manages users.

How it really works

Cryptographically, the Kerberos protocol is a variant on the Needham-Schroeder protocol, using time-stamps in place of nonces. Only symmetric ciphers are used - no public key cryptography is employed. Version 5 of the protocol is described. Kerberos 5 supports a fair few ciphers, including DES, Triple DES, and AES (I think).

The protocol in English

The Kerberos server shares secret keys with all the clients, key distribution centers, and application servers. The secret keys are generally a function on a password.

When the client first logs on, it sends it's identity to the Kerberos server, along with the identity of the key distribution server that the client uses. The Kerberos server looks up the client's identity in it's own database.

If it finds the identity of the client in it's database, it generates a ticket-granting ticket for that client.

Tickets are Kerberos data structures that can be safely sent across a network that, when valid, prove to it's recipient the authorisation of the client to use the recipients services.

The ticket-generating ticket (or TGT) is used by the client to request tickets from the key distribution centers. All tickets in Kerberos are encrypted with the key of the recipient, and adhere to a standard structure which among other things contains:

• The client identity.
• The client network address.
• The client session key.
• A valid-from time-stamp.
• A valid-to time-stamp.

The ticket generated here is encrypted with the shared secret key of the key distribution center. The client session key in the ticket here is copied and encrypted with the shared key of the client.

Both the ticket and the encrypted client session key are sent to the client.

If the client has the correct password, then it may decrypt the session key. No further communication is required with the Kerberos server. Subsequent communication takes place with the KDC, and must be encrypted with this session key. If the client has an incorrect password, it cannot obtain a session key.

At this point, the client possesses the same session key twice. One copy is decrypted into plaintext where it can be used for encrypting and decrypting communications. The other copy is part of the ticket-granting ticket. As the ticket-granting ticket is encrypted with the key of the KDC, it can safely be sent over the network without fear of passive attackers - eavesdroppers.

The next step is normally the client requesting access to the services controlled by the KDC. To gain access to the services, the client must possess a ticket from the KDC. To get this ticket, the client creates an authenticator to send to the KDC. Authenticators are encrypted with the session key, and contain:

• The client identity.
• A time-stamp.

The purpose of the time-stamp in the authenticator is to prevent replay attacks.

Both the ticket-granting ticket and the authenticator are then sent to the KDC.

The ticket-granting ticket was encrypted with the key of the KDC, which is known by the original encryptor, the Kerberos server. The KDC now decrypts the ticket, gaining access to the client session key.

The KDC uses the client session key to decrypt the authenticator. Upon successful decryption, three tests are performed on the information in the authenticator.

Firstly, the KDC verifies that the client identity in the ticket is identical to the client identity in the authenticator. This ensures that the Kerberos server has granted access to the client who constructed the authenticator.

Secondly, the KDC also compares the client network address from the ticket to the address from which it received the authenticator. This ensures that the Kerberos server granted access to the same computer that is now requesting access.

Lastly, the time-stamp in the authenticator is compared to the current time. This check prevents replay attacks.

If the received authenticator decrypts successfully, and passes these three tests, then the KDC generates a new ticket. The recipient of this ticket is the service that the client wishes to access, and as such the ticket is encrypted with the key of the service. A new session key is generated for the ticket by the KDC.

The KDC encrypts the new session key with the old session key, and sends this and new ticket to the client.

The client then obtains the new session key by decrypting the first part of the response with the old session key. The client now has two copies of the new session key. One is in the clear, where it can be used by the client, and one is in a ticket that can safely be sent across a network.

The client composes a new authenticator, this time for the service it wishes to access. This authenticator contains the same information as the one outlined above, and is encrypted with the new session key. The client then sends this authenticator and the ticket it received from the KDC to the service it wishes to access.

The service then performs operations identical to that of the KDC. It decrypts the body of the ticket with it's own secret key - unknown by the client - to obtain the session key. It uses the session key to decrypt the authenticator, and compares the information within it to the information from the ticket. If the information is verified, the server that the client is attempting now is certain:

• The client was identified by the Kerberos server.
• The client was authorized by the KDC.

And thus, our client is allowed access.

The protocol, formally

The Kerberos documentation makes extensive use of some shortcuts that make describing the process above simpler but more cryptic. I've tried to standardize this.

Actors

• C - the Client
• T - the Trusted Kerberos server
• D - the key Distribution center
• S - the Server

Variables

• c - The identity of the client C
• s - The identity of the server S
• a - The network address of the client C
• v - validity time-stamps
• d - The identity of the key distribution server D
• t - A time-stamp

Keys used

• K_D - secret key for the key distribution server D
• K_S - secret key for the application server S
• K_CD - session key for client C and key distribution server D
• K_CS - session key for client C and application server S

The protocol

1. One time setup

   The trusted Kerberos server T shares a secret key with KDC D. D shares a secret key with application server S.

2. Protocol Messages

   (1) C -> T : c, d
   (2) C <- T : K_D(c, a, K_CD, v)
   (3) C -> D : K_CD(c,t), d, K_D(c, a, K_CD, v)
   (4) C <- D : K_S(c, a, K_CS, v)
   (5) C -> S : K_CS(c,t), s, K_S(c, a, K_CS, v)

3. Protocol Actions

   1. The client C sends the Kerberos server T it's identity c and the identity d of the key distribution center who's services it wishes to access.

   2. If the client exists in the Kerberos database, T returns a ticket for that KDC, consisting of the client identity c, client network address a, validity time-stamps v, and a session key K_CD, all encrypted with the key of the KDC, K_D.

   3. The client C sends the KDC D an authenticator, consisting of time-stamp t and client identity c, both encrypted with session key K_CD, as well as the ticket outlined above.

   4. The KDC D decrypts the ticket and uses the extracted session key K_CD to decrypt the authenticator. If the client identity c and network address a are valid, and the time-stamp t is correct, then the KDC returns a ticket with the session key K_CS, for use between the client C and the server S.

   5. The client C creates a new authenticator, this time encrypted with session key K_CS, along with the ticket received from the KDC D.

Attacks

While time-stamping defeats most replay attacks that would work with nonces in place, one side-effect is that for effective operation, Kerberos requires all parties to have secure and synchronized clocks. In the MIT implementation, this is taken as a given, and no special attention is given to this. But a secure and reasonably reliable method of ensuring uniform time settings is necessary to prevent replay attacks.

The Kerberos server shares secret keys with all the clients, key distribution centers, and application servers. As such, the Kerberos server and KDC servers represent high-value potential points of entry for an attacker. However, physically securing servers tends to be easier than securing their networking.

The secret keys shared by the various principals with the Kerberos server are generally derived from passwords. As such, the standard recommendations for choosing good passwords apply.

One assumption that has shifted underfoot, so to speak, is that the user would be running trusted applications. This is no longer a valid assumption for many users.

Kerberos has been studied extensively in the cryptography community, and has held up remarkably well.

(If anyone spots mistakes, please /msg)

1: Telnet is, IMHO, a bad idea nowadays except for network diagnostics - use ssh instead.

Notes: The Kerberos home page (which I really should have read before writing this) is at:
http://web.mit.edu/kerberos/www/
If you're looking for user account management etc, there was a fairly good Ask Slashdot:
http://ask.slashdot.org/article.pl?sid=02/02/20/2333259&mode=nested
Implementations of Kerberos servers and clients for UNIX-alikes can be found here:
http://www.mirrors.wiretapped.net/security/cryptography/apps/kerberos-servers/
Kerberos clients for Windows and Macintosh can be found here:
http://www.mirrors.wiretapped.net/security/cryptography/apps/kerberos-clients/

Sources:
The Kerberos installation, system administrators and users guides
Applied Cryptography - Bruce Schneier
Handbook to Applied Cryptography - Menezes et al
Security Engineering - Ross Anderson