COEN 350
Kerberos
Kerberos
● Provide authentication for a user that works
on a workstation.
● Uses secret key technology
● Because public key technology still had patent
projection.
● Implements authentication by Needham &
Schroeder.
● On the market in versions 4 and 5.
Kerberos
● Kerberos consists of
● Key Distribution Center (KDC)
● Runs on a physically secure node
● Library of Subroutines
● Modifies known UNIX libraries such as telnet,
rlogin, …
Key Distribution Center
● KDC:
● Database of keys for all users
Alice KDC Bob
Alice wants
KAlice{ KAB Bob
for KBob{KAB for
Bob } Alice}
● Invents and hands out keys for each transaction
between clients.
Key Distribution Center
● Message from KDC to Bob has some
problems.
● Timing problem: Alice needs to wait to make
sure that Bob got the key.
● Change the protocol so that Alice receives a
ticket to talk to Bob.
Key Distribution Center
Alice KDC Bob
KAlice{Use
I’mAlice KAB
wants
Alice, my Bobfor is
ticket Bob}
KBob{Use KAB for
Ticket
Alice}for Bob :=
KBob{Use KAB for Alice}
Key Distribution Center
● Needham Schroeder:
● Combines KDC operation with authentication.
● Uses nonces instead of timestamps to prevent
replay attacks.
● A (sequential / random) number used only once.
Needham Schroeder
Alice N1, Alice, Bob KDC Bob
KAlice{N1, Bob, KAB, ticket to
Bob}
Ticket, KAB{N2}
KAB{N2-1, N3}
KAB{N3-1}
Ticket = KBob{KAB, Alice}
Needham Schroeder
Alice N1, Alice, Bob Trudy
KDC (KDC) Bob as Bob
Trudy
KAlice{N1, Bob, KAB, ticket to
Bob}
Ticket = KBob{KAB, Alice}, …
But the nonces make all messages unique!
Trudy
Trudy
Trudy can
of now
Trudywaits
Purpose now untilsuccessfully
impersonates the
incorporates
the Alice
nonce KDC
ismakes
Bob.
the authenticate
and
a request
following to herself
replays the old
scenario:KDC.to Alice
as Bob. message, which looks like a normal message.
captured
Assume that Trudy has stolen an old key of Bob’s and
stolen the message where Alice previously has
requested a key. Bob has in the meantime changed his
key.
Needham Schroeder
● Message 2: KAlice{N1, Bob, KAB, ticket}
with ticket = KBob{KAB,Alice}
● N1 prevents replay attacks.
● “Bob” to prevent Trudy from trying to play
Bob.
● Ticket does not have to be sent encrypted with
Alice’s key.
Needham Schroeder
● Message 3: ticket, KAB{N2}
● Alice presents a challenge together with her
ticket.
● Bob decodes ticket to find KAB.
● He decodes the latter part of the message to
find the challenge.
Needham Schroeder
● Message 4: KAB{N2-1,N3}
● Bob solves Alice’s challenge.
● Bob sends Alice his own challenge.
● Your turn: What is the vulnerability if message 4
were to read: KAB{N2-1}, KAB{N3} ?
Answer on next two slides.
Needham Schroeder
● Answer:
● Trudy eavesdrops on an exchange and then
splices her own messages to Bob:
Needham Schroeder
Alice Bob
Ticket, KAB{N2}
KAB{N2-1},
KAB{N3}
KAB{N2-1}
Replays Ticket,
KAB{N4}
KAB{N2}
Trudy (later) Trudy now resumes her first
connection: KAB{N4-1} and is
Ticket,
authenticated KAB{N4}
KAB{N4-1}
KAB{N5}
Trudy (second connection)
Needham Schroeder
● Expanded Needham Schroeder
● Prevents replay attacks after Alice’s master key
was stolen and Alice changed her master key.
Needham Schroeder
● Vulnerability Scenario
● Alice has a previous key JAlice that Trudy
captured.
● Alice has changed her key to KAlice.
● Trudy has captured a previous login request
from Alice to KDC:
● KDC sent
JAlice{N1,Bob,JAB,KBob{JAB,Alice}}
Needham Schroeder
● Vulnerability Scenario
● Trudy has JAlice{N1,Bob,JAB,KBob{JAB,Alice}}
● Trudy calculates JAB and KBob{JAB,Alice} with
JAlice.
● Trudy now impersonates Alice to Bob. She sends her
round 3 message to Bob:
N2, KBob{JAB,Alice}
● She can complete the Needham Schroeder protocol
with Bob.
● Since the KDC no longer participates, informing the
KDC of the change does not prevent Trudy from
succeeding impersonating Alice to Bob.
Needham Schroeder Vulnerability
Scenario
● Trudy has
● JAlice{N1,Bob,JAB,KBob{JAB,Alice}}, JAB.
KBob{JAB,Alice}.
● Trudy to Bob: JAB{N2}, KBob{JAB,Alice}
● Bob to Trudy: JAB{N2–1, N3}
● Trudy to Bob: JAB{N3–1}
● Trudy and Bob are mutually authenticated!
Needham Schroeder
● Solution:
● Prevent replays after long duration:
● Clock and date.
● Certificate from Bob.
● Extended Needham Schroeder picks the
latter.
Extended Needham Schroeder
Alice to Bob: I want to talk to you.
Bob to Alice: KBob{NB}
Alice to KDC: N1, “Alice wants Bob”, KBob{NB}
KDC to Alice: KAlice{N1,“Bob”,KAB, KBob{KAB, “Alice”,
NB}}
Alice to Bob: KBob{KAB, “Alice”, NB}, KAB{N2}
Bob to Alice: KAB{N2-1,N3}
Alice to Bob: KAB{N3-1}.
NB prevents the previous attack. Bob can determine
whether Alice is using the key that the KDC has.
Extended Needham Schroeder
● Alice now needs to receive a certificate
from Bob before starting standard Needham
Schroeder.
Otway Rees
● Replaces extended Needham Schroeder
● Uses only 5 messages
● Speed-up results from the “suspicious
party” (Bob) going to the KDC.
Otway Rees
Alice to Bob: NC, Alice Bob KAlice{NA,NC,“A.”,“B.”}
Bob to KDC: KAlice{NA,NC, Alice, Bob, KBob{NB,NC,“A.”,
“B.”}
KDC to Bob NC, KAlice{NA,KAB}, KBob{NB,KAB}
Bob to Alice: KAlice{NA,KAB}
Alice to Bob: KAB{NC}
Kerberos
● Based on Needham Schroeder, but uses
time instead of nonces.
● Approximate time is easy in distributed
systems.
Kerberos
● Kerberos Authentication Service:
Alice to KDC N1 “Alice wants Bob”
KDC to Alice KAlice{N1, “Bob”, KAB, KBob{KAB, Alice, expir.
Time}}
Alice to Bob KBob{KAB, “Alice”, expir. Time}, KAB{cur. Time}
Bob to Alice KAB{cur. Time +1}
Kerberos
● Kerberos Setup
● Master key shared by KDC with each principal.
● When Alice logs into her machine, her station asks the KDC
for a session key for Alice. The KDC also gives her a Ticket
Granting Ticket. (TGT)
● Alice’s workstation retains only the session key and the TGT.
● Alice’s workstation uses the TGT to receive other tickets
from the Ticket Granting Service (TGS).
Kerberos
● Two entities:
● Key distribution center.
● Authentication Server (AS)
● Ticket granting server (TGS).
● Both need the same database, so they are
usually on the same machine.
Kerberos
● Kerberos V. 4 Logging in:
Alice Workstation AS
Alice AS_REQ{Alice}
KAlice AS_REP{KAlice{SAlice,TG
T}}
TGT = KKDC{Alice,
Workstation calculates SA}
session key SAlice and
TGT, throws KAlice
away.
Kerberos
● Why wait for the password?
● Workstation should know Alice’s password for
minimum time.
● Kerberos v. 5 changes this.
● The workstation would contain data on which a
password cracker could be run.
Kerberos
● Kerberos V. 5 Logging in:
Alice Workstation AS
Alice AS_REQ{Alice}
AS_REP{KAlice{SAlice,TG
Password? T}}
KAlice TGT = KKDC{Alice,
Workstation calculates SA}
session key SAlice and
TGT, throws KAlice
away.
Kerberos
● Purpose of TGT
● AS, TGS does not need to retain session state.
● Can recuperate quickly from a crash.
Kerberos
● Remote Login
● Step 1: Get a ticket for Bob.
● Step 2: Use the ticket to log into Bob.
Kerberos
Alice Workstation TGS
rlogin Bob TGS_REQ{ Alice to Bob, TGT, SA{timestamp}}
Gets SA from TGT, verifies
timestamp, creates ticket to
Bob
KBob{ Alice, KAB }
TGS_REP{ SA{“Bob”, KAB, KBob{Alice,
KAB}}
Kerberos
Bob
A’s Workstation
AP_REQ{ KBob{Alice, KAB}, KAB{timestamp}}
Bob decrypts the ticket to find KAB.
He then checks the timestamp.
AP_REP{ KAB {timestamp + 1}}
Workstation authenticates Bob because Bob has proven he knows KAB.
Kerberos
● After the successful rlogin, Alice and Bob
are not forced to use KAB
● But they can.
Kerberos
● Replicated KDC
● To remedy single point of failure.
● To remedy bottleneck.
● Critical design point is the master key database.
● Can be made read-only at replicated KDC and updated
by a single master.
● Updates of the master key database need to be
protected against substitution attacks.
Kerberos
● Realms
● Every entity in a Kerberos realm trusts the
Kerberos TGS & AS.
● Each realm has its own master key database.
● Principals in one realm can be authenticated to
principals in another realm.
Kerberos
Realm 1
Alice
Request and ticket
for KDC in Realm
2 Realm 2
Request and ticket
for KDC in Realm
3
Realm 3
Request
Kerberos
● Realms V4:
● Principal names have three strings:
● NAME
● service
● INSTANCE
● typically server on which service runs
● REALM
● Version 5: Uses ASN.1
● NAME
● now arbitrary number of fields
● Realm
Kerberos
● A single rogue KDC cannot subvert this
process and grant tickets for things in other
realms.
Kerberos
● Tickets contain
● Newly minted authentication key KAB
● Name of requestor
● Expiration Time
● At most 23 hours
Kerberos
● Keys contain version numbers.
● Network resources (incl. KDC) remember
several versions of their master keys.
● This allows a key change without invalidating
all pending requests.
● Important for batch jobs when additional
authentication is not possible.
Kerberos
● Encryption is used to prevent disclosure and
modification.
● Key: Cannot be disclosed nor modified
● Name: cannot be modified.
● Version 4: Proprietary system with a few
flaws
● Plaintext Cipher Block Chaining
Kerberos: PCBC
● Modifying any Ci results in modifying all subsequent Ci.
● At end of message, put in something recognizable.
● Flaw: Swapping to adjacent blocks, subsequent blocks are
back in order.
Kerberos
● Kerberos V. 4 uses a checksum mechanism
for integrity.
● Algorithm is suspect, but not proven broken.
● Kerberos V. 5 uses a suite of possible
checksum algorithms
Kerberos
● Kerberos messages contain network
addresses in the TGT.
● The TGS checks for the network address
when granting tickets.
● This is not much of a protection
● It is easy to fake network addresses
● But together with a firewall might be useful to
thwart attackers from outside.
Kerberos
● Kerberos puts 4B IPv4 address inside a ticket.
● Recipient of ticket checks whether the source IP
address is the same as in the ticket.
● Prevents use of a stolen session key and TGT.
● Probably not worth the trouble, since it is easy to spoof
IP addresses.
● Generates problems with NAT.
● Makes delegation of rights difficult / impossible.
Kerberos
● Version 5 updates
● ASN.1 data representation language
● No fixed message formats.
● Adds considerable overhead.
ASN.1 is presented in COEN 351.
Kerberos
● Optional delegation of Rights:
● Delegation of rights allows someone to give them their
access rights for a limited scope and limited time.
● Important to allow access to resources by a long-lasting batch-
job.
● Cannot be done by handing out the master key, or there
would be no limitation to the delegation.
● Handing tickets to the batch-job will not work if they
are used after they expire.
Kerberos
● Optional delegation.
● Kerberos v. 5 allows Alice to ask for a TGT
with a network address different from her
address.
● This TGT is not usable by Alice, but can be
used by some entity to act on Alice’s behalf.
Kerberos
● Optional delegation.
● Limited Delegation
● Alice can give Bob tickets to the specific service that he will
need acting on her behalf.
● Instead of giving Bob a TGT.
● Alice can give Bob a TGT with the AUTHORIZATION-DATA
field specified.
● This field is interpreted by the application, not Kerberos.
● Application reads the field to determine what Bob can do.
● OSF/DCE and Windows 2000 use this field extensively.
Kerberos
● Optional Delegation
● Flag in TGT indicates whether delegation is allowed:
● Forwardable Flag
● TGT can be exchanged for a TGT with a different network layer
address.
● Alice decides whether the new TGT still has the
forwardable flag set. In this way, Bob can ask Carol to act
for him on behalf of Alice, …
● Proxiable Flag
● TGT can be used to request tickets (but not TGTs) with a
different network address.
Kerberos
● Ticket Lifetimes
● There is a need for longer lived tickets, but
granting them in general poses security risks.
● K v. 5 allows
● Specifying a start time.
● An end time.
● Authorization time.
● Renew till times.
Kerberos
● Alice can:
● Get a renewable ticket.
● Ticket is valid for 100 years.
● But Alice needs to renew it daily.
● Renewing a ticket is done by
● Giving the ticket to the KDC and have the KDC reissue it.
● If there is something wrong, the KDC can be told to not renew
the ticket.
● KDC only needs to retain revocation data for the ticket lifetime.
● Uses the renewable flag.
Kerberos
● Alice can:
● Get a postdated ticket.
● Used to run a batch-job sometimes in the future.
● Kerberos uses the Start-Time field to indicate the future
moment when the ticket becomes valid.
● Original post-dated ticket is marked invalid.
● If Bob wants to use the ticket, Bob has to present it to the
KDC, which clears the invalid field.
● This allows revocation of postdated tickets.
Kerberos
● Key Versions
● KDC maintains versions of keys.
● Stored as
● key (encrypted version of Alice’s key)
● p_kvno (Alice’s key version number)
● k_kvno (Version of KDC key used to obtain key)
● Needed for
● Post-dated tickets
● Renewable tickets
Kerberos
● Making Master Keys Different
● Master keys in different realms should be
different, when generated with the same
password.
● Kerberos v.5 uses a password to key hash
function that has the realm name as an
additional parameter.
● Keys are different in different realms in an
unpredictable way.
