l13-kerberos.md

Kerberos

Note: These lecture notes were slightly modified from the ones posted on the 6.858 course website from 2014.

Kerberos setting

• Distributed architecture, evolved from a single time-sharing system.
• Many servers providing services: remote login, mail, printing, file server.
• Many workstations, some are public, some are private.
• Each user logs into their own workstation, has root access.
• Adversary may have his/her own workstation too.
• Alternatives at the time: rlogin, rsh.
• Goal: allow users to access services, by authenticating to servers.
• Other user information distributed via Hesiod, LDAP, or some other directory.
• Widely used: Microsoft Active Directory uses the Kerberos (v5) protocol.

What's the trust model?

• All users, clients, servers trust the Kerberos server.
• No apriori trust between any other pairs of machines.
• Network is not trusted.
• User trusts the local machine.

Kerberos architecture

• Central Kerberos server, trusted by all parties (or at least all at MIT).
• Users, servers have a private key shared between them and Kerberos.
• Kerberos server keeps track of everyone's private key.
• Kerberos uses keys to achieve mutual authentication between client, server.
  • Terminology: user, client, server.
  • Client and server know each other's names.
  • Client is convinced it's talking to server and vice-versa.
• Kerberos does not provide authorization (can user access some resource).
  • It's the application's job to decide this.

Why do we need this trusted Kerberos server?

• Users don't need to set up accounts, passwords, etc on each server.

Overall architecture diagram

                                 +-----------------------+
                  c, tgs         |                       |
  [ User: Kc ]  <-------->  [ Kerberos ]                 |
       ^      \                  |           Database:   |
       |       \                 |             c: Kc     |
       V        \    s           |             s: Ks     |
 [ Server: Ks ]  \-------->   [ TGS ]                    |
                                 |         KDC           |
                                 +-----------------------+

Kerberos constructs

Basic Kerberos constructs from the paper:

• Ticket, T_{c,s} = { s, c, addr, timestamp, life, K_{c,s} }
  • usually encrypted w/ K_s
• Authenticator, A_c = { c, addr, timestamp }
  • usually encrypted w/ K_{c,s}

Kerberos protocol mechanics:

• Two interfaces to the Kerberos database: "Kerberos" and "TGS" protocols.
• Quite similar; few differences:
  • In Kerberos protocol, can specify any c, s; client must know K_c.
  • In TGS protocol, client's name is implicit (from ticket).
  • Client just needs to know K_{c,tgs} to decrypt response (not K_c).
• Where does the client machine get K_c in the first place?
  • For users, derived from a password using, effectively, a hash function.
• Why do we need these two protocols? Why not just use "Kerberos" protocol?
  • Client machine can forget user password after it gets TGS ticket.
  • Can we just store K_c and forget the user password? Password-equivalent.

Naming

• Critical to Kerberos: mapping between keys and principal names.
• Each principal name consists of ( name, instance, realm )
  • Typically written name.instance@realm
• What entities have principals?
  • Users: name is username, instance for special privileges (by convention).
  • Servers: name is service name, instance is server's hostname.
  • TGS: name is 'krbtgt', instance is realm name.
• Where are these names used / where do the names matter?
  • Users remember their user name.
  • Servers perform access control based on principal name.
  • Clients choose a principal they expect to be talking to.
    • Similar to browsers expecting specific certificate name for HTTPS
• When can a name be reused?
  • For user names: ensure no ACL contains that name, difficult.
  • For servers (assuming not on any ACL): ensure users forget server name.
  • Must change the key, to ensure old tickets not valid for new server.

Getting the initial ticket: "Kerberos" protocol

• Client sends pair of principal names (c, s), where s is typically tgs.
• Server responds with { K_{c,s}, { T_{c,s} }_{K_s} }_{K_c}
• How does the Kerberos server authenticate the client?
  • Doesn't need to -- willing to respond to any request.
• How does the client authenticate the Kerberos server?
  • Decrypt the response and check if the ticket looks valid.
  • Only the Kerberos server would know K_c.
• In what ways is this better/worse than sending password to server?
  • Password doesn't get sent over network, but easier to brute-force.
• Why is the key included twice in the response from Kerberos/TGS server?
  • K_{c,s} in response gives the client access to this shared key.
  • K_{c,s} in the ticket should convince server the key is legitimate.

General weakness: Kerberos 4 assumed encryption provides message integrity.

• There were some attacks where adversary can tamper with ciphertext.
• No explicit MAC means that no well-defined way to detect tampering.
• One-off solutions: kprop protocol included checksum, hard to match.
• The weakness made it relatively easy for adversary to "mint" tickets.
  • Ref: http://web.mit.edu/kerberos/advisories/MITKRB5-SA-2003-004-krb4.txt

General weakness: adversary can mount offline password-guessing attacks.

• Typical passwords don't have a lot of entropy.
• Anyone can ask KDC for a ticket encrypted with user's password.
• Then try to brute-force the user's password offline: easy to parallelize.
• Better design: require client to interact with server for each login attempt.

General weakness: DES hard-coded into the design, packet format.

• Difficult to switch to another cryptosystem when DES became too weak.
• DES key space is too small: keys are only 56 bits, 2^56 is not that big.
• Cheap to break DES these days ($20--$200 via https://www.cloudcracker.com/).
• How could an adversary break Kerberos give this weakness?

Authenticating to a server: "TGS" protocol

• Client sends ( s, {T_{c,tgs}}_{K_tgs}, {A_c}_{K_{c,tgs}} )
• Server replies with { K_{c,s}, { T_{c,s} }_{K_s} }_{K_{c,tgs}}
• How does a server authenticate a client based on the ticket?
  • Decrypt ticket using server's key.
  • Decrypt authenticator using K_{c,s}.
  • Only Kerberos server could have generated ticket (knew K_s).
  • Only client could have generated authenticator (knew K_{c,s}).
• Why does the ticket include c? s? addr?life?
  • Server can extract client's principal name from ticket.
  • Addr tries to prevent stolen ticket from being used on another machine.
  • Lifetime similarly tries to limit damage from stolen ticket.
• How does a network protocol use Kerberos?
  • Encrypt/authenticate all messages with K_{c,s}
  • Mail server commands, documents sent to printer, shell I/O, ..
  • E.g., "DELETE 5" in a mail server protocol.
• Who generates the authenticator?
  • Client, for each new connection.
• Why does a client need to send an authenticator, in addition to the ticket?
  • Prove to the server that an adversary is not replaying an old message.
  • Server must keep last few authenticators in memory, to detect replays.
• How does Kerberos use time? What happens if the clock is wrong?
  • Prevent stolen tickets from being used forever.
  • Bound size of replay cache.
  • If clock is wrong, adversary can use old tickets or replay messages.
• How does client authenticate server? Why would it matter?
  • Connecting to file server: want to know you're getting legitimate files.
  • Solution: server can send back { timestamp + 1 }_{K_{c,s}} after it receives ticket and authenticator from client

General weakness: same key, K_{c,s}, used for many things

• Adversary can substitute any msg encrypted with K_{c,s} for any other.
• Example: messages across multiple sessions.
  • Authenticator does not attest to K_{c,s} being fresh!
  • Adversary can splice fresh authenticator with old message
  • Kerberos v5 uses fresh session key each time, sent in authenticator
• Example: messages in different directions
  • Kerberos v4 included a direction flag in packets (c->s or s->c)
  • Kerberos v5 used separate keys: K_{c->s}, K_{s->c}

What if users connects to wrong server (analogue of MITM / phishing attack)?

• If server is intercepting packets, learns what service user connects to.
• What if user accidentally types ssh malicious.server?
  • Server learns user's principal name.
  • Server does not get user's TGS ticket or K_c.
  • Cannot impersonate user to others.

What happens if the KDC is down?

• Cannot log in.
• Cannot obtain new tickets.
• Can keep using existing tickets.

Authenticating to a Unix system.

• No Kerberos protocol involved when accessing local files, processes.
• If logging in using Kerberos, user must have presented legitimate ticket.
• What if user logs in using username/password (locally or via SSH using pw)?
  • User knows whether the password he/she supplied is legitimate.
  • Server has no idea.
• Potential attack on a server:
  • User connects via SSH, types in username, password.
  • Create legitimate-looking Kerberos response, encrypted with password.
  • Server has no way to tell if this response is really legitimate.
• Solution (if server keeps state): server needs its own principal, key.
  • First obtain user's TGS, using the user's username and password.
  • Then use TGS to obtain a ticket for server's principal.
  • If user faked the Kerberos server, the second ticket will not match.

Using Kerberos in an application.

• Paper suggests using special functions to seal messages, 3 security levels.
• Requires moderate changes to an application.
  • Good for flexibility, performance.
  • Bad for ease of adoption.
  • Hard for developers to understand subtle security guarantees.
• Perhaps a better abstraction: secure channel (SSL/TLS).

Password-changing service (administrative interface)

• How does the Kerberos protocol ensure that client knows password? Why?
  • Special flag in ticket indicates which interface was used to obtain it.
  • Password-changing service only accepts tickets obtained by using K_c.
  • Ensure that client knows old password, doesn't just have the ticket.
• How does the client change the user's password?
  • Connect to password-changing service, send new password to server.

Replication

• One master server (supports password changes), zero or more slaves.
• All servers can issue tickets, only master can change keys.
• Why this split?
  • Only one master ensures consistency: cannot have conflicting changes.
• Master periodically updates the slaves (when paper was written, ~once/hour).
  • More recent impls have incremental propagation: lower latency (but not 0).
• How scalable is this?
  • Symmetric crypto (DES, AES) is fast -- O(100MB/sec) on current hardware.
  • Tickets are small, O(100 bytes), so can support 1M tickets/second.
  • Easy to scale by adding slaves.
• Potential problem: password changes take a while to propagate.
• Adversary can still use a stolen password for a while after user changes it.
• To learn more about how to do replication right, take 6.824.

Security of the Kerberos database

• Master and slave servers are highly sensitive in this design.
• Compromised master/slave server means all passwords/keys have to change.
• Must be physically secure, no bugs in Kerberos server software, no bugs in any other network service on server machines, etc.
• Can we do better? SSL CA infrastructure slightly better, but not much.
  • Will look at it in more detail when we talk about browser security / HTTPS.
• Most centralized authentication systems suffer from such problems. .. & globally-unique freeform names require some trusted mapping authority.

Why didn't Kerberos use public key crypto?

• Too slow at the time: VAX systems, 10MHz clocks.
• Government export restrictions.
• Patents.

Network attacks.

• Offline password guessing attacks on Kerberos server.
  • Kerberos v5 prevents clients from requesting ticket for any principal.
  • Must include { timestamp }_{K_c} along with request, proves know K_c.
  • Still vulnerable to password guessing by network sniffer at that time.
  • Better alternatives are available: SRP, PAKE.
• What can adversary do with a stolen ticket?
• What can adversary do with a stolen K_c?
• What can adversary do with a stolen K_s?
  • Remember: two parties share each key (and rely on it) in Kerberos!
• What happens after a password change if K_c is compromised?
  • Can decrypt all subsequent exchanges, starting with initial ticket
  • Can even decrypt password change requests, getting the new password!
• What if adversary figures out your old password sometime later?
  • If the adversary saved old packets, can decrypt everything.
  • Can similarly obtain current password.

Forward secrecy (avoiding the password-change problem).

• Abstract problem: establish a shared secret between two parties.
• Kerberos approach: someone picks the secret, encrypts it, and sends it.
• Weakness: if the encryption key is stolen, can get the secret later.
• Diffie-Hellman key exchange protocol:
  • Two parties pick their own parts of a secret.
  • Send messages to each other.
  • Messages do not have to be secret, just authenticated (no tampering).
  • Two parties use each other's messages to reconstruct shared key.
  • Adversary cannot reconstruct key by watching network messages.
• Diffie-Hellman details:
  • Prime p, generator g mod p.
  • Alice and Bob each pick a random, secret exponent (a and b).
  • Alice and Bob send (g^a mod p) and (g^b mod p) to each other.
  • Each party computes (g^(ab) mod p) = (g^a^b mod p) = (g^b^a mod p).
  • Use (g^(ab) mod p) as secret key.
  • Assume discrete log (recovering a from (g^a mod p)) is hard.

Cross-realm in Kerberos.

• Shared keys between realms.
• Kerberos v4 only supported pairwise cross-realm (no transiting).

What doesn't Kerberos address?

• Client, server, or KDC machine can be compromised.
• Access control or groups (up to service to implement that).
• Microsoft "extended" Kerberos to support groups.
  • Effectively the user's list of groups was included in ticket.
• Proxy problem: still no great solution in Kerberos, but ssh-agent is nice.
• Workstation security (can trojan login, and did happen in practice).
  • Smartcard-based approach hasn't taken off.
  • Two-step authentication (time-based OTP) used by Google Authenticator.
  • Shared desktop systems not so prevalent: everyone has own phone, laptop, ..

Follow-ons.

• Kerberos v5 fixes many problems in v4 (some mentioned), used widely (MS AD).
• OpenID is a similar-looking protocol for authentication in web applications.
  • Similar messages are passed around via HTTP requests.