Kerberos: The Problem It Solves

Kerberos takes the third approach. Every request is authenticated as coming from a named user, not from a machine, and the server can be asked to prove itself too, because, in the paper's words, someone elsewhere on the network "may be masquerading as the given server".

What an attacker on such a network can do

Three threats follow directly from the setting, and every part of the design exists to defeat one of them.

1. Pretending to be another user at a workstation. The student controls the machine, so anything the machine says about who is logged in can be made to say anything.
2. Pretending to be another workstation. A server that trusts a network address trusts something any machine on the network can change. This is exactly why the second approach in the table fails.
3. Listening, and replaying. Anything that crosses the network can be recorded. The 1988 paper defines the replay precisely: a message "stolen off the network and resent later". A recorded message that worked once may work again.

And a fourth, which the first three hide: a fake server. A machine that pretends to be the file server can collect whatever the students send it, which is why authentication must run in both directions.

Why "send the password to every server" fails

The obvious design is the one every student proposes first: each server asks for the user's password and checks it. It fails in five separate ways.

1. The password crosses the network in the clear, and threat 3 records it. One capture and the attacker is the user, on every server, until the password is changed.
2. Every server must hold every password. At Athena's scale that is 5,000 × 65 = 325,000 stored password records, where one database of 5,000 would do. Breaking into any one of 65 servers yields everybody's password.
3. A fake server collects passwords simply by asking for them. The user has no way to tell the real file server from an impostor.
4. The user types the password again for every service. People who must type a password many times a day choose short ones.
5. Nothing stops a replay. Even a scrambled password, sent the same way each time, is a recording that can be replayed.

Every one of those five is an argument, not an opinion, and a question asking "why was Kerberos needed" is answered by stating them.

The four requirements

The 1988 paper lists four requirements the service had to meet. They are worth knowing by name because they are exactly what the design trades against each other.

The idea: a referee that knows every key

Kerberos is built on the trusted third party of the Needham and Schroeder protocol, with the timestamps that Denning and Sacco proposed, which is the ground the authentication protocols chapter covered. RFC 4120's own introduction names both.

Every party that uses Kerberos is a principal: a user, or a network service. The Kerberos server holds a database with one secret key for every principal.

• A service's key is a long random key, generated when the service is registered and installed in a protected file on the server's machine (in version 4, /etc/srvtab).
• A user's key is computed from the user's password by a one-way function, so the database holds the key, and not the password itself. The version 5 method, from RFC 3962, runs the password through PBKDF2 (a deliberately slow, repeated keyed hash) with a salt made of the realm name followed by the user's name, 4,096 times by default.

Because the referee shares a key with everyone, it can write a message that only one particular server can read, and put inside it a statement that the server will believe: this request comes from Asha. That sealed statement is a ticket.

The price, which the key management chapter named in advance: the referee knows every key. Whoever controls the Kerberos server controls every identity on the network, which is why the paper insists that the machine holding it be physically secure.

Building the design, one defect at a time

The dialogue in the next chapter is six messages long. It did not arrive in one piece, and the fastest way to understand it is to build it the way its problems force it.

Attempt 1: the password goes to each server

Rejected above, for five reasons. It is in the run below only so that its failure can be seen.

Attempt 2: one authentication server, and a ticket

Put a single authentication server (AS) in charge of passwords. Asha sends it her name and her password and the name of the server she wants; it checks the password and returns a ticket: her name, her workstation's address and the server's name, all encrypted under the server's secret key. She hands the ticket to the server, which decrypts it and believes it, because only the AS could have made it.

That fixes two things. Only one machine holds passwords, and the ticket cannot be forged or altered by Asha, because she does not have the server's key. Two defects remain. Her password still crosses the network, now to the AS. And she needs a new ticket, and so types her password again, for every new server she uses.

Attempt 3: the password never travels, and it is typed once

Two changes fix both.

The password stops travelling. Asha sends only her name. The AS encrypts its reply under Asha's key, the one derived from her password. The workstation asks her for the password, derives the key, and decrypts the reply. The password never leaves the keyboard: what crosses the network is a reply that only her password can open.

The password is typed once. The AS no longer issues tickets for each server. It issues one special ticket, a ticket-granting ticket (TGT), for a second server, the ticket-granting server (TGS). Whenever Asha wants a new service she presents the TGT to the TGS, which issues the ticket for that service without asking for her password. The workstation keeps the TGT and forgets the password.

Tickets now carry the time they were issued and a lifetime, so a ticket stops working when it is old. At Athena the TGT's lifetime was eight hours: a working day.

What is still missing

Attempt 3 is close, and its remaining defect is the one the whole of version 4 is designed around. A ticket proves nothing about who is presenting it. It says "this is for Asha", and anyone who copies it off the network can present it. The server can check the address inside against the address the request came from, but threat 2 says an address can be changed. So a thief with a copied ticket and a changed address is Asha, until the ticket expires.

The lifetime cannot fix that. A short lifetime shrinks the thief's window and makes Asha type her password all day; a long one is convenient and hands the thief the whole day. The fix is not in the ticket at all. It is a second, fresh item that only the real Asha can produce, which the next chapter calls the authenticator. And one more defect remains untouched: nothing yet proves to Asha that the server is the real one.

The run

The listing builds attempts 1 and 3 and attacks both. Tickets are sealed with encrypt-then-MAC, a stand-in for the DES of version 4 and the AES of version 5, so that any change to a ticket is detected; the protocol's logic, not the cipher, is the subject here. Asha's key is derived exactly as RFC 3962 derives it, and the derivation is first checked against the output the RFC prints.

# The problem Kerberos solves, run: a password that travels, and a ticket that is not proof.
import hashlib, hmac, json, random

rng = random.Random(610)                 # seeded, so every run prints the same thing

def string_to_key(password, realm, name):
    # RFC 3962's first step: PBKDF2 with HMAC-SHA1, salt = realm + name, 4,096 rounds
    return hashlib.pbkdf2_hmac('sha1', password.encode(), (realm + name).encode(), 4096, 16)

rfc = hashlib.pbkdf2_hmac('sha1', b'password', b'ATHENA.MIT.EDUraeburn', 1200, 16)
print('PBKDF2 step matches RFC 3962 Appendix B (1,200 rounds):',
      rfc.hex() == '5c08eb61fdf71e4e4ec3cf6ba1f5512b')

def keystream(key, nonce, n):
    blocks = (hashlib.sha256(key + nonce + i.to_bytes(4, 'big')).digest()
              for i in range(n // 32 + 1))
    return b''.join(blocks)[:n]

def seal(key, record):
    # encrypt, then MAC: a stand-in for version 4's DES or version 5's AES
    nonce = rng.getrandbits(64).to_bytes(8, 'big')
    plain = json.dumps(record, sort_keys=True).encode()
    body = nonce + bytes(p ^ s for p, s in zip(plain, keystream(key, nonce, len(plain))))
    return body + hmac.new(key, body, hashlib.sha256).digest()

def unseal(key, blob):
    body, tag = blob[:-32], blob[-32:]
    if not hmac.compare_digest(tag, hmac.new(key, body, hashlib.sha256).digest()):
        raise ValueError('integrity check failed')
    nonce, data = body[:8], body[8:]
    return json.loads(bytes(c ^ s for c, s in zip(data, keystream(key, nonce, len(data)))))

REALM = 'COLLEGE.EXAMPLE'
wire = []                                 # everything anyone on the LAN can record

def send(frm, to, what):
    wire.append((frm, to, what))
    return what

# ---- attempt 1: the password goes to every server ---------------------------
print()
print('ATTEMPT 1: Asha sends her password to each server she uses')
stored = {}
for server in ('files', 'print', 'mail'):
    stored[server] = {'asha': 'monsoon-lab-7'}          # each server must hold it
    send('10.0.5.21', server, 'user=asha password=monsoon-lab-7')
print('  copies of her password held on servers :', len(stored))
print('  password readable in the wire recording:',
      any('monsoon-lab-7' in str(w) for w in wire))

# ---- attempt 3: one authentication server, and a ticket-granting ticket -----
print()
print('ATTEMPT 3: the password never leaves the keyboard')
wire.clear()
K = {'asha': string_to_key('monsoon-lab-7', REALM, 'asha'),
     'tgs':   rng.getrandbits(128).to_bytes(16, 'big'),
     'files': rng.getrandbits(128).to_bytes(16, 'big')}
LIFETIME = 8 * 3600                       # Athena's 1988 figure: eight hours

def authentication_server(user, service, addr, now):
    tgt = seal(K['tgs'], {'user': user, 'addr': addr, 'service': service,
                          'issued': now, 'life': LIFETIME})
    return seal(K[user], {'tgt': tgt.hex()})              # readable only with Kc

def ticket_granting_server(user, service, tgt, addr, now):
    t = unseal(K['tgs'], tgt)
    if t['user'] != user or t['addr'] != addr:
        return None
    if not t['issued'] <= now < t['issued'] + t['life']:
        return None
    return seal(K[service], {'user': user, 'addr': addr, 'service': service,
                             'issued': now, 'life': LIFETIME})

def file_server(user, ticket, addr, now):
    try:
        t = unseal(K['files'], ticket)
    except ValueError as e:
        return 'refused: ' + str(e)
    if t['user'] != user or t['addr'] != addr:
        return 'refused: wrong user or address'
    if not t['issued'] <= now < t['issued'] + t['life']:
        return 'refused: ticket expired'
    return 'access granted to ' + t['user']

now = 1000
reply = send('as', '10.0.5.21', authentication_server('asha', 'tgs', '10.0.5.21', now))
typed = string_to_key('monsoon-lab-7', REALM, 'asha')     # typed at the workstation
tgt = bytes.fromhex(unseal(typed, reply)['tgt'])
try:
    unseal(string_to_key('monsoon-lab-8', REALM, 'asha'), reply)
except ValueError as e:
    print('  the reply opened with a wrong password :', e)

send('10.0.5.21', 'tgs', ('asha', 'files', tgt))
ticket = send('tgs', '10.0.5.21',
              ticket_granting_server('asha', 'files', tgt, '10.0.5.21', now + 5))
print('  password readable in the wire recording:',
      any('monsoon-lab-7' in str(w) for w in wire))
print('  Asha, from her own machine             :',
      file_server('asha', ticket, '10.0.5.21', now + 10))

altered = bytearray(ticket)
altered[20] ^= 1                                          # she edits one bit
print('  Asha, with one bit of the ticket edited:',
      file_server('asha', bytes(altered), '10.0.5.21', now + 20))

# ---- and the defect: a copied ticket is as good as the original -------------
print()
print('THE DEFECT: Ravi records the ticket off the wire')
copied = [w[2] for w in wire if w[1] == '10.0.5.21' and w[0] == 'tgs'][0]
print('  Ravi, from his own address             :',
      file_server('asha', copied, '10.0.5.77', now + 60))
print('  Ravi, after changing his address       :',
      file_server('asha', copied, '10.0.5.21', now + 60))
print('  Ravi, nine hours later                 :',
      file_server('asha', copied, '10.0.5.21', now + 9 * 3600))

# ---- what the lifetime trades away -------------------------------------------
print()
print('A copied ticket is usable until it expires, so the lifetime is a trade:')
for hours in (1, 8, 21.25):
    logins = 1 if hours >= 8 else round(8 / hours)
    typing = '1 password entry' if logins == 1 else f'{logins} password entries'
    print(f'  lifetime {hours:>5} h: a stolen ticket works for up to {hours:>5} h;'
          f' an 8 h day needs {typing}')

What the run establishes, in order.

The key derivation is the real one. Before any key is made, the PBKDF2 step reproduces RFC 3962 Appendix B's printed value for the password password, the salt ATHENA.MIT.EDUraeburn and 1,200 rounds. The salt is that realm followed by that user's name, which is RFC 4120's default rule.

Attempt 1 leaks the password to anyone listening, and leaves a copy on every server.

Attempt 3 does not. The recording of every message on the network contains no trace of the password, and a reply opened with the wrong password fails its integrity check instead of yielding a ticket.

The ticket is sealed against its owner. Asha changes one bit of it and the server refuses it. She cannot read it or edit it, only pass it on.

And the defect is real. Ravi records the ticket. From his own address the server refuses it, because the address inside does not match. From Asha's address, which he has only to claim, the server grants him access as Asha. Only the expiry stops him, nine hours later.

The lifetime is a trade, not a fix. One hour protects better and costs eight password entries a day; eight hours costs one entry and gives a thief the day. The last line uses version 4's longest possible lifetime, 21.25 hours, which the chapter after next derives.

Key terms

Distinctions that carry marks

What beginners get wrong here

Saying Kerberos uses public-key cryptography. It does not. RFC 4120 describes Kerberos as authenticating "by using conventional (shared secret key) cryptography". Public-key extensions exist, and they are outside the core protocol.

Saying the password is sent encrypted. It is not sent at all. What is sent is the user's name, and what comes back is a reply encrypted under a key derived from the password.

Treating a ticket as proof of identity. A ticket proves that the KDC issued it for somebody; it does not prove that the person presenting it is that somebody. That is the job of the authenticator, and it is the most examined idea in the next chapter.

Confusing authentication with authorisation. Kerberos tells the file server who is asking. Whether that person may read a given file is the file server's decision.

Believing Kerberos needs no trust. It needs complete trust in one machine. The KDC holds every key, so whoever controls it controls every identity.

Where Kerberos stops

RFC 4120 s.1.6 lists what the protocol assumes rather than solves, and each item is a likely short question.

• Denial of service is not solved. An attacker can stop the authentication steps from happening.
• Principals must keep their keys secret. Anyone who steals a key is that principal.
• Password guessing is not solved. A recorded reply encrypted under a key derived from a weak password can be attacked offline, one dictionary word at a time. The chapter after next shows what version 5 did to make this harder.
• Clocks must be loosely synchronised, typically within 5 minutes, and a network clock service must itself be secured. This is the price of timestamps that the authentication protocols chapter named, now paid.
• Principal names are not recycled quickly, so that a new user never inherits an old user's permissions.

The 1988 paper adds its own open problems, all still instructive: choosing a ticket lifetime, letting a server act on a user's behalf, and trusting a public workstation that someone may have altered to record passwords as they are typed.

Quick revision

• Kerberos: MIT, Project Athena; trusted third party; conventional (secret-key) cryptography; the password is typed once and never crosses the network.
• Scale it was built for (1988 paper): 5,000 users, 650 workstations, 65 servers; sole authentication at Athena from January 1987.
• Three approaches: trust the workstation, trust the host's word, make the user prove it to each service. Only the third works on an open network.
• Threats: impersonating a user at a workstation, impersonating a workstation by address, eavesdropping and replay, and a fake server.
• Four requirements: secure, reliable, transparent, scalable.
• Design steps: one AS and a ticket; the reply encrypted under the password-derived key; a TGT and a TGS so the password is typed once; tickets with a lifetime.
• Remaining defect: a copied ticket works for the thief until it expires, so a fresh authenticator is needed, and the server must prove itself too.
• Not solved by Kerberos (RFC 4120 s.1.6): denial of service, password guessing, stolen keys; clocks within about 5 minutes are assumed.

Test yourself

1. Why can a server on an open campus network not simply trust the workstation to identify its user? Because the user controls the workstation. They can restart it, run their own operating system on it, or attach their own machine to the network, so anything the workstation reports about who is logged in can be made to say whatever its user wants. Only the user proving their own identity to the service, independently of the machine, can be relied on.

2. Give three reasons why sending the password to every server is unacceptable. The password crosses the network in the clear, where anyone listening can record it and then impersonate the user everywhere. Every server must then hold every user's password, so breaking into any one server exposes all of them. And a fake server can collect passwords merely by asking, since the user cannot tell it from the real one. Further reasons: the password must be typed for every service, and the same message can be replayed.

3. How does Kerberos let a user authenticate without sending the password? The user sends only their name. The authentication server replies with a message encrypted under a key derived from the user's password, which it holds in its database. The workstation asks the user for the password, derives the same key and decrypts the reply locally. Only someone who knows the password can open the reply, and the password itself never crosses the network.

4. What is the ticket-granting server for? It lets the password be typed once per session. At login the authentication server issues a single ticket-granting ticket. Whenever the user needs a ticket for a new service, the workstation presents the ticket-granting ticket to the ticket-granting server, which issues the service ticket without the password being needed again.

5. A ticket is encrypted under the server's key and cannot be forged. Why is it still not enough to authenticate its presenter? Because anyone who copies it off the network can present it. The ticket says whom it was issued to, not who is presenting it, and an address check inside it can be defeated by changing one's network address. A thief can therefore use a copied ticket until it expires. The fix is an authenticator, a fresh item that only the holder of the ticket's session key can produce.

6. State the four requirements Kerberos was designed to meet, and one thing it does not solve. It had to be secure, reliable, transparent and scalable. It does not solve denial of service, and it does not solve password guessing: a recorded reply encrypted under a key derived from a weak password can be attacked offline.