Re: [Sks-devel] Re: Delete key from keyserver

[Yaron Minsky]

I'm not sure that inserting the new tag in the offending key is really the simplest way of encoding this.

Here's a short description of the algorithm I have in mind.  The basic thing to understand about SKS is that it works by agreeing on sets of values.  When node A and B (with sets S_A and S_A) communicate, they figure out the hash-values that each is missing from the other, i.e., S_A - S_B and S_B - S_A.  Then, based on those hash values, A and B request the missing data.

Currently, the set elements are keys.  To support deletion, you would want to extend the values so they logically were a union type:

type set_element = | Key of Key.t
                   | Deletion of Hash.t

where Key.t is a PGP key, and Hash.t is the type of the hash of a set_element.

The idea is that when a key-server adds a Deletion to its set of keys, it actually deletes the corresponding element from its data set.  Now, consider what happens if A has a deletion for a value that B still has.  A will discover it's missing the key in question, and B will discover it's missing the deletion.  Each will request the missing element from the other. A's request will succeed, but will have no effect, since A will know to delete the key.  B's request will succeed, and it will as a result delete the key in question from its database.

If we want to delete the deletions, we can extend set_element with one more variant:

type set_element = | 
Key of Key.t
                   | 
Deletion of Time.t * Hash.t
                   | Deletions_stable of Time.t

We've added a time to the Deletion, which is the time the deletion was added to the system.  The Deletions_stable element is meant to indicate that all deletions sent before the specified time are assumed to be stable, and can thus be discarded (and older Deletions_stable elements can also be discarded).  Thus, if someone periodically sends out a Deletions_stable after a decent time period, then this will clean out old deletions from the system.

Presumably, the Deletion and Deletions_stable entries would need to be signed by some trusted key before they would be accepted by a given keyserver.  But that goes to the policy question...

y

On Tue, Sep 7, 2010 at 10:28 PM, Jeff Johnson <address@hidden> wrote:

On Sep 7, 2010, at 9:50 PM, Yaron Minsky wrote:

> I think that a basic form of deletion is pretty easy, and requires no real research  The algorithm is simple.  You simply add a new kind of pseudo-key to be gossiped around: a deletion token.  In the simplest version, the deletion token never expires; it's a permanent addition to the database.  But the effect of adding the deletion token is that the thing it wants to delete is effectively removed.  With a small amount of extra cleverness, one can allow the deletion token to be removed eventually as well.  But given the small number of deletions that appear to be necessary, it hardly seems urgent.
>

Thanks.

When I hear "pseudo-key" and "deletion token", I also hear a form of "white out".

Since RFC-2440/4880 already has well understood attributes of revocation and expiry,
then I would hope that a "pseudo-key" could actually be grafted on as another attribute tag
on an existing revoked/expired pubkey with the additional meaning
       This pubkey is now a "pseudo-key deletion token" and should be ignored while gossiping.

If all the key packets except
       the pubkey
       the revocation
       the additional attribute that indicates never distribute
are stripped out (specifically the userid and all certification signatures), that might be sufficient
even for lawyers -- is it possible to "own" 1 or more MPI's  if there are no identifying marks to
indicate the owner? I'll leave that to others with the usual IANAL disclaimer.

So my next question would be:

       Is it feasible to craft up a special "pseudo key" as above that -- when fed manually to
       each SKS server  -- would replace, not augment, the existing offending pubkey and
       NEVER be gossiped.

I add "manually" solely to uncouple the token from its distribution.

What I don't know is
  1) Can the deletion be handled as an attribute?
  2) How should that attribute be represented as a RFC 2440/4880 tag?

The next step would be to relax the "fed manually" so that the pseudo-key could be gossiped,
thereby replacing every occurrence of the offending pubkey with the "pseudo key deletion token".

Does that sound like the basic framework that would be needed?

73 de Jeff

> There is a policy question: who gets to add a deletion token to the system?  The owner of the key to be deleted?  Or perhaps there are a set of trusted administrators shared by the whole network who can ask for deletions?
>
> And, of course, there's the question of who is going to do the work.  I don't have the time to devote to SKS at this point, so if this feature is to be added, someone else needs to do it.
>
> y
>