Kerberos

THIS POST IS UNDER CONSTRUCTION

The 3-headed dog of Greek mythology, now synonymous with Active Directory, kerberos was designed and presented by MIT in 1988. It was designed as a method of authenticating users to network services in an untrusted network.

This dialogue provides a fictional example of how kerberos was built, under a different name of Charon (which I have renamed to Odin because I hate the spelling of Charon). I’ll expand upon the example, with (poor) diagrams and rewording.

Dramatis Personae

Athena = an up and coming system developer.

Ares = a seasoned developer and resident crank.

Prologue:

In ye olde days of 1988, computers were not anywhere near as capable as they are now. They existed as mainframes, many businesses couldn’t afford computers, one those that could, wouldn’t want to spend large sums of money on buying more. To tackle this issue, IBM came up with the concept of time-sharing. A computer’s resources could be shared across a large group of user’s, from terminals that would share the resources of the mainframe as and when they were required. Processing time was allocated by a supervisory program, allowing dozens of users to access without interfering of each other. Over time, as personal desktops became more capable, services dispersed across servers and were accessed individually. This is a similar method to what is employed today, where large-scale hypervisors provide virtual servers which offer network services, as opposed to many individual physical servers.

This dialogue is slightly outdated (being written in 1988) but the core concepts are the same. The below diagram shows how the network is at the beginning of Scene 1.

Scene 1:

A cubicle area. Athena and Ares are working at neighbouring terminals.

Athena: Ares, this timesharing system is a drag. I can’t get any work done because everyone else is logged in.

Ares: Don’t complain to me. I only work here.

Athena: You know what we need? We need to give everyone their own workstation so they don’t have to worry about sharing computer cycles. And we’ll use a network to connect all the workstations so folks can communicate with one another.

Ares: Fine. So what do we need, about a thousand workstations?

Athena: More or less.

Ares: Have you seen the size of a typical workstation’s disk drive? There isn’t enough room for all the software that you have on a timesharing machine.

Athena: We can keep copies of the software on separate servers. When you login to a workstation, the workstation accesses the software by making a network connection with one of the servers.

Athena: This setup lets a whole bunch of workstations use the same copy of the system software, and it makes software updates far more convenient. Just modify the system software.

Ares: All right. What are you going to do about personal files? With a timesharing system I can login and get to my files from any terminal that is connected to the system. Will I be able to walk up to any workstation and automatically get to my files? Or do I have to make like a PC user and keep my files on a USB? I hope not.

Athena: I think we can use other machines to provide personal file storage. You can login to any workstation and get to your files.

Ares: What about printing? Does every workstation have its own printer? Whose money are you spending anyway? And what about email? How are you going to distribute mail to all these workstations?

Athena: Ah . . . Well obviously we don’t have the cash to give everyone a printer, but we could have machines dedicated to print service. You send a job to a print server, and it prints it for you. You could do sort of the same thing with mail. Have a machine dedicated to mail service. You want your mail, you contact the mail server and pick up your mail.

Ares: Your workstation system sounds really good Tina. When I get mine, you know what I’m going to do? I’m going to find out your username, and get my workstation to think that I am you. Then I’m going to contact the mail server and pick up your mail. I’m going to contact your file server and remove your files, and–

Athena: Can you do that?

Ares: Sure! How are these network servers going to know that I’m not you?

Athena: Gee, I don’t know. I guess I need to do some thinking.

Ares: Sounds like it. Let me know when you figure it out.

Scene II

Ares’ office, the next morning. Ares sits at his desk, reading his mail. Athena knocks on the door.

Athena: Well I’ve figured out how to secure an open network environment so that unscrupulous folks like you cannot use network services in other people’s names.

Ares: Is that so? Have a seat.

She does.

Athena: Before I describe it, can I lay down one ground rule about this discussion?

Ares: What’s your rule?

Athena: Well suppose I say something like the following: “I want my electronic mail, so I contact the mail server and ask it to send the mail to my workstation.” In reality I’m not the entity that contacts the mail server. I’m using a program to contact the mail server and retrieve my mail, a program that is a CLIENT of the mail service program.

But I don’t want to say “the client does such-and-such” every time I refer to a transaction between the user and a network server. I’d just as soon say “I do such-and-such,” keeping in mind of course that a client program is doing things on my behalf. Is that okay with you?

Ares: Sure. No problem.

Athena: Good. All right, I’ll begin by stating the problem I have solved. In an open network environment, machines that provide services must be able to confirm the identities of people who request service. If I contact the mail server and ask for my mail, the service program must be able to verify that I am who I claim to be, right?

Ares: Right.

Athena: You could solve the problem clumsily by requiring the mail server to ask for a password before I could use it. I prove who I am to the server by giving it my password.

Ares: That’s clumsy all right. In a system like that, every server has to know your password. If the network has one thousand users, each server has to know one thousand passwords. If you want to change your password, you have to contact all servers and notify them of the change. I take it your system isn’t this stupid.

Athena: My system isn’t stupid. It works like this: Not only do people have passwords, services have passwords too. Each user knows her or his password, each service program knows its password, and there’s an AUTHENTICATION SERVICE that knows ALL passwords–each user’s password, and each service’s password. The authentication service stores the passwords in a single, centralized database.

Ares: Do you have a name for this authentication service?

Athena: I haven’t thought of one yet. Do you have any ideas?

Ares: What’s the name of that fellow from Iceland with the all seeing eye?

Athena: Odin? From the famously hot and sunny Iceland?

Ares: Sure, that’s the one.

Athena: Odin? Famous for despising fake identities, and hating trickery…

Ares: Have you got a better name?

Pause.

Athena: No, not really.

Ares: Then let’s call the authentication service “Odin.”

Athena: Okay. I guess I should describe the system, huh?

Let’s say you want to use a service, the mail service. In my system you cannot use a service unless, ah, Odin tells the service that you are who you claim to be. And you can’t get the okay to use a service unless you have authenticated yourself to Odin. When you request authentication from Odin, you have to tell Odin the service for which you want the okay. If you want to use the mail server, you’ve got to tell Odin.

Odin asks you to prove your identity. You do so by providing your secret password. Odin takes your password and compares it to the one that is registered for you in the Odin database. If the two passwords match, Odin considers your identity proven.

Odin now has to convince the mail server that you are who you say you are. Since Odin knows all service passwords, it knows the mail service’s password. It’s conceivable that Odin could give you the password, which you could forward to the mail service as proof that you have authenticated yourself to Odin.

The problem is, Odin cannot give you the password directly, because then you would know it. The next time you wanted mail, you could circumvent Odin and use the mail server without correctly identifying yourself. You could even pretend to be someone else, and use the mail server in that other person’s name.

So instead of giving you the mail server’s password, Odin gives you a mail service TICKET. This ticket contains a version of your username that has been ENCRYPTED USING the MAIL SERVER’S PASSWORD.

Ticket in hand, you can now ask the mail service for your mail. You make your request by telling the mail server who you are, and furnishing the ticket that proves you are who you say you are.

The server uses its password to decrypt the ticket, and if the ticket decrypts properly, the server ends up with the username that Odin placed in the ticket.

The service compares this name with the name you sent along with the ticket. If the names match, the mail server considers your identity proven and proceeds to give you your mail.

What do you think of those apples?

Ares: I’ve got some questions. Athena: I figured. Well go ahead. Ares: When a service program decrypts a ticket, how does it know that it has decrypted the ticket properly? Athena: I don’t know. Ares: Maybe you should include the service’s name in the ticket. That way when a service decrypts a ticket, it can gauge its success on whether or not it can find its name in the decrypted ticket. Athena: That sounds good to me. So the ticket looks something like this:

(She scrawls the following on a pad of paper:) TICKET - {username:servicename} Ares: So the service ticket contains just your username and the servicename? Athena: Encrypted with the service’s password. Ares: I don’t think that’s enough information to make the ticket secure. Athena: What do you mean? Ares: Let’s suppose you ask Odin for a mail server ticket. Odin prepares that ticket so that it has your username “tina” in it. Suppose I copy that ticket as it wizzes by on its way across the network from Odin to you. Suppose I convince my insecure workstation that my username is “tina.” The mail client program on my workstation thinks I am you. In your name, the program forwards the stolen ticket to the mail server. The server decrypts the ticket and sees that it is valid. The username in the ticket matches the name of the user who sent the ticket. The mail server gives me your mail . . . Athena: Oh! Well that’s not so good. Ares: But I think I know a way to fix this problem. Or to at least provide a partial fix to it. I think Odin should include more information in the service tickets it produces. In addition to the username, the ticket should also include the NETWORK ADDRESS from which the user asked Odin for the ticket. That gives you an additional level of security.

I’ll illustrate. Suppose I steal your mail ticket now. The ticket has your workstation’s network address in it, and this address does not match my workstation’s address. In your name I forward the purloined ticket to the mail server. The server program extracts the username and network address from the ticket and attempts to match that information against the username and network address of the entity that sent the ticket. The username matches, but the network address does not. The server rejects the ticket because obviously it was stolen.

Athena: Bravo, bravo! I wish I had thought of that. Ares: Well that’s what I’m around for. Athena: So the revised ticket design looks like this:

She scrawls the following on a chalkboard:

TICKET - {username:ws_address:servicename} Athena: Now I’m really excited. Let’s build a Odin system and see if it works! Ares: Not so fast. I have some other questions about your system. Athena: All right. (Athena leans forward in her chair) Shoot. Ares: Sounds like I’ve got to get a new ticket every time I want to use a service. If I’m putting in a full day’s work, I’ll probably want to get my mail more than once. Do I have to get a new ticket every time I want to get my mail? If that’s true, I don’t like your system. Athena: Ah . . . Well I don’t see why tickets can’t be reusable. If you get a ticket for the mail server, you ought to be able to use it again and again. For instance, when the mail client program makes a request for service in your name, it forwards a COPY of the ticket to the mail server. Ares: That’s better. But I still have problems. You seem to imply that I have to give Odin my password every time I want to use a service for which I don’t have a ticket. I login and want to access my files. I fire off a request to Odin for the proper ticket and this means that I’ve had to use my password. Then I want to read my mail. Another request to Odin, I have to enter my password again. Now suppose I want to send one of my mail messages to the print server. Another Odin request and, well you get the picture. Athena: Uh, yeah, I do. Ares: And if that weren’t bad enough, consider this: it sounds like when you authenticate yourself to Odin, you send your secret password over the network in cleartext. Clever people like yours truly can monitor the network and steal copies of people’s passwords. If I’ve got your password, I can use any service in your name. Athena sighs. Athena: These are serious problems. Guess I need to go back to the drawing board.