Authentication in Distributed Systems: Theory and Practice

One-line summary: 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.

Overview/Main Points

• "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 tree).
• 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 group.
• 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 program P.
• 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.

Relevance

• (Probabilistically) secure RPC is lightweight--just pass an integer.
• 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 refreshable ones.
• Since every decision whether to grant access can be derived from a fairly short proof, the proofs can be put in the audit log.

Flaws