Pet Name Markup Language
Mark S. Miller
markm@caplet.com
Sun, 07 May 2000 07:13:41 -0700
In the mutually suspicious decentralized electronic world we find ourselves
in, humans face a dilemma. Computers need to communicate securely with
other computers, and in so doing, securely designate various objects. No
problem so far, there are a number of cryptographic means by which a bit
string (usually no less than 128 bits) can be used globally (ie, between
mutually suspicious parties, and without translation) as secure designators.
The clearest example is public key fingerprints, used to designate that
entity which knows and uses the corresponding private key. Let's call such
global cryptographic identifiers "keys".
(Note: In E, a "key" is a cryptographic capability, and is represented by a
triple: a public key fingerprint, an unguessable secret number (known as a
SwissNumber), and TCP/IP location hint information used to try to contact
the object. This last part is not assumed to have any security properties.)
Humans also need to communicate securely with other humans, and in so doing,
securely designate various objects, including yet other humans.
Unfortunately, due to their peculiar nature, humans are unable to memorize
large numbers of keys, and use them as names for a multitude of objects.
Fortunately, a human-computer symbiote -- a human augmented with a personal
computer which he trusts (a personal TCB) -- can securely speak to other
such symbiotes using only keys as designators. In order for the human part
of such a symbiote to be effective, the computer part must translate between
the world of keys and the world of human-understandable and memorable names.
This translation must provide the human with a local world of name-based
designation whose security properties match the security properties of keys.
The progression of attempts to solve this problem has followed a trajectory
from more centralized to more decentralized solutions.
* The Central CA Model (VeriSign). 'Nuff said.
* The PGP Web of Trust. No central authority, but still a global name space.
* SPKI. Decentralized network of name-spaces, but no translation-on-
introduction mechanism.
* The Communities.com Pet Name System.
The last, unfortunately, was never documented for external consumption.
Though http://www.eros-os.org/~majordomo/dcms-dev/0036.html and
http://www.eros-os.org/~majordomo/dcms-dev/0039.html document Jonathan
Shapiro's adaptation of this idea for use in a configuration management system.
In another forum where cryptographic capability ideas are being vigorously
challenged, a valid concern was raised for which we don't currently have a
publicly documented answer, beyond the above two brief email messages. How
can we enable humans to deal securely with cryptographic capabilities as
human-memorable designators? This note is my attempt to answer that
question. Since the discussion in that forum is already using EChat as an
example, and since Communities.com originally developed the Pet Name system
for a multi-way chat application, I will present the ideas in terms of a
hypothetical augmented EChat.
This proposal derives from thinking about the lambda-calculus/capability
perspective on naming. Program text also uses variable names rather than
designating particular objects directly. An argument variable name is used
to send an anonymous object reference to be bound to a parameter variable
name on reception. It doesn't matter whether the two names are the same,
since names are only in a local scope. This proposal started as a faithful
application of the principles that make lambda's magic work. It has grown
some from there, but this isn't necessarily good.
Note that this proposal is useful not just for supporting capabilities
specifically, but more generally whenever human speak in a textual fashion
to other humans and would like to embed keys in much the way they type in,
or read, a normal name. Besides EChat, this could all probably be applied
to PGP email (thereby augmenting it with user-local names).
The Pet Name Markup Language
To be fashionable, I will present the proposal in terms of a proposed new
markup language -- The Pet Name Markup Language (PNML). Why a markup
language? I frankly think markup languages are silly ways for software to
speak to other software. Objects are better, and if the two pieces of
software are in different address spaces, then serialized object graphs are
fine. However, humans often speak to other humans in fairly unstructured
text containing embedded objects or designators. For this, markup languages
are not too bad, in that they take the literal text to be the "normal" case,
and require some kind of anti-quote for the non-literal part.
PNML consists of just two tags: <pn>pet-name-string</pn> and
<key>stringified-cryptographic-key</key>. (In a more speculative section
below we'll introduce a third tag: <s/>.) When used in a context where
multiple kinds of cryptographic key need to be distinguished but aren't self
identifying, we augment the <key> tag with a "type" attribute, but postpone
standardizing the values of this attribute. For E, the stringified key
would be exactly E's stringified "cap://..." URI.
The goal is that machines should only send to each other text with embedded
<key> elements, not <pn> elements, since those are the form of designation
that works robustly between machine. Conversely, humans should only need to
type or see <pn> elements containing names meaningful to them. However, we
define one markup language containing both tags, rather than two markup
languages, so humans can embed <key> elements, as they will often wish to do
using cut-and-paste from other applications (such as PGP).
Just as each PGP user has his own key-ring, each PNML user-agent has a
persistent mutable private 1-to-1 mapping from pet names to keys. This
user-agent knows how to translate text received from its user into text
transmittable to other user-agents -- replace all <pn> elements with <key>
elements by looking up the pet-name-strings in the local name-space. If a
given pet name isn't found, the text isn't accepted and the user is notified.
Human types: Did you get that letter from <pn>HoneyBunney</pn>?
Machine sends: Did you get that letter from <key>cap://...</key>?
More interesting is when a user-agent receives text from another user-agent
and needs to translate to for display to its user. As expected, it replaces
all <key> elements with <pn> elements by looking up the keys in the local
name-space.
Machine receives: Did you get that letter from <key>cap://...</key>?
Human reads: Did you get that letter from <pn>Ms. Jones</pn>?
And if the key isn't found? Let's assume we have some way to come up with
an initial proposed pet name for this key. We'll revisit this issue later,
but for now it can simply be the string "unknown". If this name isn't
already taken, the user-agent remembers this as the new pet name for this
key. Otherwise, it searches successive names derived from this name:
"unknown-1", "unknown-2", etc, until it finds one that isn't taken, and
remembers that instead. It then uses that name in the replacement <pn>
element. In also places this name in a separate persistent, mutable,
private ToBeRenamed table, associated with a copy of the text which
introduced this key. This table remembers the names not chosen by the user,
and therefore ones for the user to think about renaming.
Machine receives: Did you get that letter from <key>cap://...</key>?
Human reads: Did you get that letter from <pn>unknown-3</pn>?
Going back to the case where the incoming key is found, if the associated
pet name is in the ToBeRenamed table, then a copy of this text is added to
the text remembered in that table. That table therefore maps from names to
lists of text.
Now "unknown-3" isn't very informative. However, while there are better
answers (see below), there are no answers which are more correct. Assuming
the existing inter-human channels have characterizable security properties,
and (inductively) assuming that the reader's name space has so far
maintained a name-key mapping that the reader can use reliably, then the
only thing the reader knows for sure is what specific others have said to
this reader about the designated entity. That's why we save all incoming
text that designates an entity the reader hasn't named yet. This text is
the information the reader has to work with to choose a reliable name.
Maintaining a Name-Space
The user-agent exports to it user, through its user-interface, operations
for examining and editing its data structures. The most important
operation, of course, is rename, which by default also removes that name, if
present, from the ToBeRenamed table.
Naming Paths
Starting from here, we should eventually(!) import more of SPKI's power by
allowing naming paths rather than simple names. We introduce a kind of
designatable object called a name-space (doesn't have to be 1-to-1, can be
many-to-1), and a a standard way of either invoking it remotely (the E way)
or of authenticatedly replicating it (the SPKI way). Now
Human says: Did you get that letter from <pn>Bob<s/>Mom</pn>?
can be though of like "Did you get that letter from Bob's Mom?" (The
apostrophe-s trick for naming paths is taken from Smalltalk-72.) Now the
sending user-agent can translate in one of two ways. It can look up the
<pn>Bob</pn> public name-space object, and ask it what key is associated
with "Mom". Or it can just translate <pn>Bob</pn> and send
Machine sends: Did you get that letter from <key>cap://...<s/>Mom</key>?
When the user-agent receives this, it can translate it all the way by doing
the same lookup:
Human reads: Did you get that letter from <pn>Ms. Jones</pn>?
or it can present a path:
Human reads: Did you get that letter from <pn>Robert<s/>Mom</pn>?
Where do these public name-space objects come from? Well, anyone should be
able to create and maintain one, and publicly export a read-only facet. In
an EChat- or PGP-like scenario, it is probably done by deliberately marking
a subset of one's pet-name name space for export.
Feedback, especially from SPKI folk, would help narrow down these options.
However, they all correctly preserve the required security properties.
Choosing Better Proposed Pet Names
"unknown" really sucks as a base to generate an initial proposed pet name.
This is where the notion of nickname is relevant, although more mechanism is
needed in order for there to be nicknames. As long as Robert's choice of
the nickname "Bob" can't cause Alice to confuse him with someone she has
already installed as "Bob", then we should be willing to start with Robert's
proposed name. If there's a conflict, Alice will end up seeing "Bob-3", and
knowing that she didn't generate this name because it's in her ToBeRenamed
table. This still tells Alice what Robert suggests she call him, which is
useful.
In E, the user agent might ask the designated object whether it responds to
"getNickname". If it says yes, it could ask it for its nickname. Otherwise
we could fall back to "unknown". The EChat object representing a user
would, of course, respond to getNickname.
Were we to add all this to PGP, the names encoded in the PGP keys would be
our nicknames. We could get PGP key, and therefore nicknames, from
fingerprints (keys in our sense) by, for example, asking the PGP key
servers. Each signed key endorsements in PGP can be seen as the equivalent
of signed text in the ToBeRenamed table of the form:
Carl Says: <key>...</key> is the person I know as Bill Frantz
Asides
Why "pet name"? We started with "nickname", but this had the wrong
connotations. My nickname is usually understood as a property of me. It's
a unary operator: nickname(MarkMiller) => MarkM. By contrast, pet names are
understood to be specific (and private!) to the relationship between two
people. My Mom's pet name for is, well, I'm not telling. By our
definition, SPKI is a pet name system.
Jonathan, I think you should adopt a term other than "true name" for the key
information. Vernor Vinge's "true name" is the human legible name (or other
information) than enables people, such as governments, to figure out which
physical breathing human body you inhabit, and perhaps point guns at you.
Fortunately, none of the 3 kinds of name we're dealing here are necessarily
that kind.
Note: The second email linked to above states that Communities.com is
currently working on a product version of this system. I want to make it
clear that I left Communities.com 18 months ago or so, and have no idea how
these notions evolved in the meantime. Neither party should be taken to
speak for the other. Also, the ideas I present in this note evolved from
the Pet Name system that I knew at Communities.com, but it is not a
description of that system.
Credit where due: When I originally told Jonathan about these ideas, I was
in a hurry, so when he asked, I said "credit it to 'Mark Miller and others
while at Electric Communities'", which he did. This is a good time to
repair my sloppiness. As far as I can remember, the people who worked on or
influenced the Pet Name system include: Eric Messick, John Sullivan, Trevor
Morris, Bill Frantz, and Ellen Isaacs. Perhaps also Randy Farmer.
Apologies if I've left anyone out. Please let me know.
Norm Hardy's http://www.mediacity.com/~norm/CapTheory/Personal.html is a
very different start on exploring the issues of giving capabilities a secure
user interface. I believe it and this note are complementary.
Cheers,
--MarkM