zooko.com

introduction | current events | projects | stuff

Newsflash 2006-01-30: I've noticed more people citing this web page and discussing it. While this web page is important for historical reasons, there are more current -- and probably more coherent -- discussions of the issues elsewhere. I recommend that you start with Marc Stiegler's An Introduction to Petname Systems. See also Tyler Close's web pages about YURLs, cited below. --Zooko 2006-01-30

Update: Tyler Close has written a nice analogy about "naming versus pointing", and has proposed that secure, non-human-meaningful names be called "pointers" instead of "names". I think this is an excellent idea, that obviates a lot of conflict by helping people think of human-meaningful "naming", and secure "pointing" as separate. Tyler's company, Waterken, has developed a secure pointing standard named "YURL". Read more about it at their website: http://www.waterken.com/dev/YURL/Analogy/.

Non-Self-Authenticating Names Cannot Span Trust Boundaries

There are two kinds of name-value pairs: those that are self-authenticating and those that aren't. A name-value pair is "self-authenticating" if, given the name-value pair, you can verify on your own that the mapping from that name to that value is correct. (For example, if the name comes with a public key and the value comes with a digital signature made by the corresponding private key, then it is easy to verify without any other information that the value is a valid value for that name.)

If your decentralized namespace confines itself to serving self-authenticating name-value pairs, then you can easily be free from the risk of deception and the only remaining security issue is to prevent denial of service attacks.

If your decentralized namespace allows non-self-authenticating name-value pairs, then I doubt that it will be secure. I have not seen any proof that such a system is even possible in principle, it isn't even clear what the intended behavior should be, and the best designs that I have seen are complex, limited, and risky.

In this essay, I use the word "decentralized" to denote that the system spans trust boundaries. This means that two peers can use this system to interoperate with each other, while neither of them is vulnerable to the other nor is either vulnerable to a third party.

Self-Authenticating Names Cannot Be Meaningful To Humans

Examples of self-authenticating name-value pairs are those where the name is the secure hash of the value (Freenet's CHKs and Mnet's mnetids) and those where the name includes the id of a public key and the value includes a digital signature from the corresponding private key (Freenet's SSKs and Self-certifying File System's directory names).

Okay, so if we can have a decentralized namespace to securely share self-authenticating pairs but not non-self-authenticating pairs, then why don't we just satisfy ourselves with the former? Because they are not meaningful to humans.

Cryptographic values such as hashes and public keys are too long and random-looking for humans to use them as meaningful names.

"Humans are incapable of securely storing high-quality cryptographic keys, and they have unacceptable speed and accuracy when performing cryptographic operations. (They are also large, expensive to maintain, difficult to manage, and they pollute the environment. It is astonishing that these devices continue to be manufactured and deployed. But they are sufficiently pervasive that we must design our protocols around their limitations.)"

             -- Kaufman, Perlman, and Speciner quoted in Anderson's "Security Engineering"

But Your Computer Can Remember Things For You

Okay, that's funny, but we don't have to design every namespace to support human-meaningful keys. For example, I often cut-and-paste URLs from amazon.com. They look like this:

http://www.amazon.com/exec/obidos/ASIN/0312862075/

I have never memorized one of these or used one in spoken conversation, and I probably never will.

If you are designing a decentralized namespace, think about whether you have to support human-meaningful, non-self-authenticating keys, at the cost of losing the ability to safely span trust boundaries. For some applications, you do need human-meaningful keys, for others you don't.

Further, consider that your human user might have a loyal computer assistant at hand, which can translate self-authenticating names into human-meaningful names as described in the Pet Names Markup Language and as implemented in Self-certifying File System. If so, then you can have both the safety of self-authenticating keys and the human-friendliness of traditional names. Indeed, the way that my desktop software, editor and e-mail software allow me to cut-and-paste URLs from one application to another is an example of how tools can free humans from the need to remember names. I didn't need any new software tools to use the amazon.com URL above as an opaque reference -- just a web browser and a text editor.

Two Ways To Design A Namespace That Does Not Span Trust Boundaries

The current state of the art, as far as I have seen, tends to fall into one of two traps.

• First trap:

  1. Assume that you need arbitrary keys including non-self-authenticating ones.
  2. Think about the problem of crossing trust boundaries, and solve by delegating to a "trusted third party".
  3. Forever after you will be vulnerable to MicrosoftNSIVerisignICANNUSGovInc. and anyone (including their employees) who can subvert one of their servers. When this bloated monopoly screws something up, your system will pay the price for their incompetence. You will not be able to choose a different name authority, because everyone else will also be tied to the central monopoly and you will need their service in order to interoperate with the world. (Does this scenario sound familiar to anyone?) In addition, they will charge you a tax on every packet for the privilege of continued service.

• Second trap:

  1. Assume that you need arbitrary keys.
  2. Don't think about trust boundaries.
  3. Publish.
  4. Try to figure out how to make it secure without introducing a central "trusted third party".
  5. Go to step 4.

You Can't Have It All, But You Can Have Some Of It

To summarize, you cannot have a namespace which is all three of: 1. decentralized (which is the same as saying that the namespace spans trust boundaries), 2. secure in the sense that an attacker cannot cause name lookups to return incorrect values that violate some universal policy of name ownership, and 3. using human-memorizable keys.

So what should you do? There are at least five alternatives:

1. You can have a namespace that is secure and allows human-memorizable keys, but that is centralized in terms of trust -- all participants must trust a central authority, or perhaps a hierarchy of authorities leading ultimately to a central "root" authority. Many people seem to think that this is the only possible kind of namespace, perhaps because of their familiarity with DNS, which is an example of this design. Corporations like VeriSign/NSI, Microsoft, Time/Warner/AOL/Netscape, and others apparently believe that such a namespace is a natural monopoly rich in unexploited profits. This belief of theirs is revealed by the amount of money they are spending in the attempt to gain control of the namespace.
2. You can have a namespace that is decentralized and uses human-memorizable keys but is not secure, in the sense that anyone can change any name to point to any value at any time. It may sound silly, but such namespaces do actually get deployed, usually when the user base is very small or when they all know one another.
3. You can have a namespace that is decentralized and secure but does not have human-memorizable keys. Freenet's CHKs, Mnet's mnetids, and Chord's keys do this for immutable key-value pairs (where a given name refers to a bitwise copy of an object and that name can never be made to refer to any other bit pattern). Freenet's SSKs, SPKI's certificates, and Self-certifying File System's directory names do this for mutable key-value pairs (where a given name, which includes a public key, can be made to refer to a new object in addition to the old object, but only by using the private key).
4. You can have a namespace that is decentralized and secure, as in #3, and in addition you can offer your users a computer agent, which runs locally to them and is loyal to them, which translates the self-authenticating names into human-memorizable names for their use. Since most uses of a decentralized namespace will already include a user agent (e.g. a web browser, handheld wireless device, an e-mail user agent, etc.), this requirement is not as burdensome as it might appear. The Pet Names Markup Language is a specification for a very simple markup language for this purpose. Self-certifying File System implements this feature with a simple tool which is familiar to every Unix user: the symbolic link.
5. Show me that I'm wrong. I didn't prove that it is impossible to have all three features, I only said that I doubted that your namespace will have all three. If you think your namespace design can provide all three, then lay out an argument that it can do so. The first step will be to specify what it means for the decentralized human-memorizable names to be secure, which is the same as specifying what universal policy should govern ownership of names. (For example, in the case of CHKs, to be secure means that you can't have a collision such that one CHK identifies two different bitstrings which, conveniently enough, is part of the definition of security for cryptographic hashes. In the case of SSKs, to be secure means that only the holder of the private key can change the mapping from a given SSKs to its object, which is conveniently similar to the traditional notion of security for digital signatures.) If your decentralized namespace satisfies all three criteria then (a) you should carefully justify your claim that it does so, starting with a specification of what the ownership policy is and including a specification of what kind of threat model it is secure under, and (b) publish! It will be the first published design that does so!

If you want my advice, I recommend strategy #3 and the optional added feature of #4. The best example to emulate is probably Self-certifying File System.

Thanks to Mark Miller for teaching me about the important distinction between self-authenticating and non-self-authenticating key-value pairs and for helpful comments on an earlier draft of this article. Thanks to Aaron Swartz and others for suggestions.

Links mentioned on this page:

• Freenet
• Mnet
• Self-certifying File System
• Pet Names Markup Language
• Chord
• SPKI