Back to index
Authentication in Distributed Systems: Theory and Practice
Butler Lampson, Martin Abadi, Michael Burrows, Edward Wobber, DEC SRC
Formal description of how to build the end-to-end-secure (e2es) OS,
based on notion of a "principal" (requesting agent), the relation that
one principal can "speak for" another, a few varieties of "speak-for"
that combine and limit authority in various ways,
and various formal proofs that
show how to securely generate and "hand off" the different kinds of
speaks-for relation among principals.
- "A speaks for B": if A says it, we can assume B would have said
it (did say it), i.e. we can act as if B had said it.
- Roles: "A as B" means "A in the role of B", which may carry
different authority than A by itself.
- Delegations: "A for B": B has delegated specific authority to A
to do something on B's behalf.
- Handoff rule: If A' speaks for A, and A' says that B speaks for
A, then we may assume that B speaks for A. A' hands off A to B.
- Using a relay allows shared-key to simulate public-key. A
trusted relay R can accept a message from you, decrypt it, and
(securely) send you the result. Kerberos does this, even though
it wasn't specifically designed that way.
- To set up a secure channel: A and B securely (i.e. using public
keys) exchange random numbers; then they securely exchange the
one-way hash K of the two random numbers. Then A believes that K
speaks for Kb, since only B could have constructed it.
- Principals with names: a secure certification authority that
speaks for A can be trusted when it says certificate C speaks for
A (by the handoff rule).
- Exceptions: Used for handling authentication in a hierarchy of
certification authorities (or other resources). E.g.: "((P except
M) quoting N) speaks for (P quoting N)" allows P to access
anything in subtree N except for M (authors explicitly add
"except .." to RHS to prevent subversion by going back up the
- Groups: Each group member is a principal that speaks for the
group. Membership can be verified by a CA (though this makes it
impossible to prove that someone is not a member) or by
having a group private key, so that an outside principal can
verify group membership of a sender but cannot speak for the
- Roles and programs: "A as R" may not have the same authority as A
acting on its own. So handoff rule allows us to hand off "A as
R" rather than handing off just "A", i.e. the recipient of the
handoff cannot do something that is allowed for A but not alloed
for "A as R" (or vice versa). To load a program securely,
user U hands off to some process the right to speak for U as
- Booting: goal is to assure that W (workstation) can speak for M
(machine) as P (program or OS image booted). The hardware is the
base case for authentication; it stores a private key in NVRAM
which is secretly chosen at installation time, and makes the
public key available. At boot, machine can invent key KN and
make a certificate that says "KN speaks for KM as P". Before
doing this, M can check the digests of programs against read-only
representations it knows, to gain assurance that P will be
running trustworthy programs.
- To simplify the whole thing, all we need to do is have the boot
ROM know a digest of a trusted boot program.
- Delegation: "A says (B quoting A) speaks for (B for A)". A gives
B the right to speak for it for specific operations. Timeouts
are used to revoke delegation.
- Secure RPC: encode A as an auth identifier (aid), which is
integer-sized. Receiver must verify that C_aid speaks for A.
See derivation on p. 178 for how this is done.
- Revokable certificates: Login results initially in a
long-term delegation by user U to KW^KL (KW is workstation's key,
KL is temporary public key created by login program). KL signs a
short-term certificate that says KW speaks for KL. By handoff we
can get (KW|KU) speaks for (KL|KU), and by the "exercise of joint
authority" theorem (P12 on p.168), we get (KW|KU) speaks for (KW
for KU). This last delegation has a short lifetime, because the
certificate saying that KW speaks for KL is short-lived, and
therefore so is (KW|KU) speaks for (KL|KU). Ugh.
Formal discussion of how to build an OS that is end-to-end-secure, from
booting through running programs in an untrusted
infrastructure while allowing secure transfer of authority from user to
hardware to program. Some contributions include:
- (Probabilistically) secure RPC is lightweight--just pass an
- Shows how to do secure booting and program loading.
- Delegation can combine or limit (through quoting mechanism)
authority of the "compound principal" thus created.
- Long-lived certificates can be countersigned with short-lived
- Since every decision whether to grant access can be derived from
a fairly short proof, the proofs can be put in the audit log.
Rambling, not well written, not tightly argued, a lot of effort to get
to the main points (which though relevant are not spelled out).
Terminology not consistent with earlier related papers (e.g. A Logic of
Back to index