Re: [Sks-devel] Key subsets (was: Proposal: Start verifying self-signatures)

[Yaron Minsky]

This seems like a very nice idea.  There are some algorithmic challenges, though.  Right now, SKS maintains an incrementally updated data structure corresponding to a kind of magic checksum of different subsets of keys.  These magic checksums are computed on subsets determined by a pre-arranged partitioning of the space.  

To do the reconciliation you propose, you'd need to be able to instead get your hands on the checksum of every key in a given range that passes a given filter criterion.  If we have a known set of filters, well, then we can compute those incrementally in advance.  If the filters are small (e.g., ban the following 30 keys) we can do them on demand.  But if you have filters that are not known in advance but make big changes to the set of admissable keys (e.g., drop all keys minted before the following date), well, that's trickier.

Changes along these lines are totally doable, but would require someone to really dig seriously into the SKS codebase.  I'm not going to have the time to do it myself.

y

On Thu, May 21, 2015 at 3:29 PM Arnold <address@hidden> wrote:

On 20-05-15 00:18, Yaron Minsky wrote:
> Let's think about a simpler question: deletion.

Hmm, simple? This question alone has at least two flavours:
 A) local deletion
 B) global, network wide deletion

> Can SKS support outright deletion of keys?
> I think a fundamental question is one of trust: is there a trusted set of
> people who could do the deletions?

Perhaps it's better to forget about deletion... It is no longer necessary once we
leave the idea of a "single set of keys" :-)

> If so, then one could pretty easily add the
> notion of a deletion certificate that could be gossiped around like a key, and
> would essentially eat some set of keys, causing them to be deleted from the database.
>
> The problem is, I don't know that such a universally trusted set exists. So, what
> do we do?  We could imagine having people volunteer to manage sets of banned keys.

It came up before, multiple operators want to ban different kind of keys for
different reasons. There is no "single set" of banned keys.

> You could subscribe to a banned key service, and just always reject any banned keys
> from your store.
> The question then is, what happens during reconciliation?  Maybe
> at reconciliation time, everyone just pretends to have all of the banned keys in
> their store, and so no one ever detects a difference based on banned keys.

> I haven't really thought much about the literature in this area for a few years.
> If real progress is to be made here, someone has to think carefully about what
> would be an effective protocol.  To think about SKS, you don't really have to know
> anything about the fancy math behind reconciliation.  Just think of it this way:
> you need to represent your knowledge as a set, and SKS gives you a cheap way to
> discover the symmetric difference of your set and someone else's set, and then you
> can synchronize based on that knowledge.  Deletion certificates just act as another
> thing in the set, and so everything works pretty straightforwardly from there.
>
> If you want to design a better SKS, you should think about whether you can build
> the semantics you want on top of this basic set-based model.

Yes, thank you Yaron! This brings me to another way of thinking. Just forget about
the idea of deletion. Think in "sets" instead! :-)

It might be possible to make SKS a key server with a "dynamic set" of keys it wants
to gossip with peers.

Each SKS operator can configure SKS to be limited to keys with (or without) certain
(predefined) properties. Examples might be:
- not on some URL-based ban-list,
- no picture uid over 1 kbyte,
- etc.

Upon reconciliation both peers exchange their filter settings. The fancy math for
reconciliation is applied on the subset of keys passing the filter rules of *both*
peers (the common set of keys they both want to have).

For example a US-server filters out certain keys on a US ban list, while a
EU-server filters out certain keys on a EU ban list. If both servers peer, they do
set reconciliation on those keys that are not on one of the ban lists. It does not
matter both servers have more keys than they advertise to their peer.
  If the EU-server later on peers with another EU-servers, they happily include all
keys on the US ban list in their set reconciliation.

This way, we *only gossip about the things we are interested in*. There is no need
to tell your peer to delete something or to fake you have something you don't
really have.

The advantage: each local administrator can freely delete all keys that do not pass
his filter criteria. However, he is free to keep those 'extra' keys on his server
as well. No forced deletion of keys in your local database.

This requires all SKS-servers to have knowledge about all possible filters.
However, once we have found a good architecture for the filters, this should not
really be a problem.

I guess the filters will be limited to some more technical filters (age, size,
pictures/binary data) and a general 'ban list' filter that can be configured with
multiple URL's. That way each operator can have his/her own (publicly accessible)
ban list (based on individual law suits or treats), while it is also possible to
have some central ban lists at the same time.

If the filter settings are available on the stats page, operators can look for
other operators to peer with, to obtain keys that their current peers filter out.

BTW I would suggest bare revocation certificates of keys generated less than 20
years ago (or something like that) do always pass filter criteria. The reason is:
without revocation, one might use encryption while being unaware of the security risk.
  In the other case of a valid (not revoked) key that is not served on a key
server, we make it difficult for one to use encryption. However, it never leads to
risks people are not aware of (they know they do not have the encryption key).

Let's first discuss about the technical feasibility for this kind of key exchange.
Once it is feasible, we can discuss consequences for inclusion in the pool,
generation of multiple pools, "official ban lists" allowed to be used by servers in
a certain pool and things like that.

I am curious what others think about this approach!

Arnold

_______________________________________________
Sks-devel mailing list
address@hidden
https://lists.nongnu.org/mailman/listinfo/sks-devel