Introduction / Problem statement

So I've been doing a lot of thinking over the last few days regarding Storm pointers.

The basic idea was, and the current implementation is, that a pointer URI contains a cryptographic public key. Pointer blocks signed with the corresponding private key would be valid.

This doesn't work for two reasons:

• Given enough time, it's feasible to obtain a private key from the public key; the recommendation is to change private keys after about two years.
• Private keys can be stolen.

This isn't really acceptable for either publishing or storage on your own computer: Once your key has been compromised somehow, no pointer URI using it will work reliably any more. There's no way to repair the problem, and there cannot be: You now have exactly the same information as the adversary who has obtained your key, and thus, they can do any (cryptographic) thing that you can do.

Key-based identity; hierarchical identity; axiomatic identity

Allow me to go a little theoretical and introduce three "types of identity" now. I'll keep it short.

Key-based identity:

The identity of an entity is its public key. Anything signed with the matching private key is taken to come from that entity.

Hierarchical identity:

A known entity can create "child" entities by assigning them names. The identity of a child entity is the parent's identity plus the name assigned by the parent entity. To know who the child entity is, ask the parent entity.

Example: DNS; to know which host is io.it.jyu.fi, ask it.jyu.fi.

Axiomatic identity:

An entity's identity is not concluded from some other information, but specified through some out-of-bounds means.

Examples: The DNS root servers; file names on a hard disk (the entity corresponding to /home/benja/foo.txt is "axiomatically" stated by the bits on my hard disk, not concluded from some other information).

(I have a hard time describing the third category well, so maybe it doesn't really make sense to lump the DNS root and files on your hard disk into the same category, but somehow I have this feeling that they're similar in a fundamental way. Hm. Comments appreciated.)

A first cut at the problem

So, let's examine how the above work out for Storm.

• We cannot use key-based identity for pointers because any private key can get exposed-- that's the motivation for this document.
• Using axiomatic identity would mean that for every entity signing pointers, we would have to establish out-of-bounds (manually) who they are, before we can read any documents from them. Clearly infeasible.
• So we're left with hierarchical identity, which works for DNS. (Of course, we need a root for the hierarchy; since key-based is out, its identity must be asserted axiomatically, as in DNS.)

A first cut:

• We have a root entity whose public key is specified through out-of-bounds means (e.g., "download from http://himalia.it.jyu.fi/pubkey").
• The root entity gives names to other entities and signs (name,pubkey) pairs with its own key.
• The other entities can do the same.
• Then, given a path like foo/bar/baz, we can find out who foo is, according to the root; who bar is, according to foo; and who baz is, according to foo/bar.

When any of the keys is revoked, the corresponding entity can ask its parent identity to sign a new key. The root identity will need out-of-bounds means.

Clearly, a parent entity can misrepresent a child entity-- foo assigns a key of its own to bar and can further on sign messages in bar's name.

It isn't the Storm-using Web surfer who needs to put trust in the parent entity, then. It's the child entity-- because the parent entity can misrepresent the child entity. In fact, an entity needs to trust all its ancestor entities.

(Just like your web hosting company can take your pages online and replace them by something else; it's the web page author who needs to trust the hosting company, not the person reading the page.)

In fact, I believe the problem cannot be solved without having to trust somebody: Because you cannot guarantee that your private key will not be exposed, you need to give somebody else the right to assign you a new key; which means you need to trust them not to assign your key to someone else.

Non-repudiability

Now, an important consideration here is non-repudiability: the inability to sign a message today and say tomorrow, "No, it wasn't me!"

Repudiability is a problem in public-key cryptography when keys expire oor are revoked. If anybody could have a copy of the corresponding private key, a signature given with it isn't worth anything-- even if it was given before the key expired, because we cannot prove that.

In our context, repudiability results in two problems:

• Web page authors can claim they never published a version of their page which they really did publish.
• Parent authorities deny the history of their child authorities. I.e., a parent authority changes the child authority's key to one that the parent authority controls; it doesn't sign the blocks that the child authority had signed, so all the blocks signed by the child authority are invalidated and all history of the data is lost.

Normally, timestamping is used to proof the validity of signatures after the key was revoked.