sks-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Sks-devel] Key subsets


From: Arnold
Subject: Re: [Sks-devel] Key subsets
Date: Fri, 22 May 2015 00:33:53 +0200
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Icedove/31.6.0

On 21-05-15 23:16, Yaron Minsky wrote:
> This seems like a very nice idea.  There are some algorithmic challenges, 
> though.

Thanks! No challenges, no fun ;-)

> 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.

I guess this is the P of the PTree database?

> 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.

It might help that the set of filters you have to apply are (more or less) fixed
for each of your peers. It might also be possible to determine the (most likely
large) set of keys that all your peers want, and do those computations in 
advance.
Or, perhaps, the total space can be divided in several subsets to cover all
combinations you need for your set of peers. For each subset the computations 
can
be done in advance and incrementally.

The 'ban list' filters will usually contain a (relative) small number of keys. 
The
number of filters having larger impact might be limited, I guess. If we only 
allow
a limited set of parameters or no parameters at all for things like 'age' 
filters
that impact is even more predictable.

Another approach might be to limit 'normal' reconciliation to all modifications 
of
the past n months (a limited number of keys, easy to calculate on demand). Once
every x weeks you can do a 'full' reconciliation. Or, perhaps better, once an 
hour
you do a 'historic' reconciliation, each time going one month further back in 
time,
or pick a random month in history from now to -20 yrs. After all, we expect
operators to start with a fresh dump.

> 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.

I'd be happy to assist in thinking about the architecture and the algorithm, 
etc.
However, ocaml is one of the languages I don't speak. I guess it won't be much
trouble learning to read it, but I don't have the time to really learn to write.

Arnold

> y
> 
> On Thu, May 21, 2015 at 3:29 PM Arnold <address@hidden 
> <mailto: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




reply via email to

[Prev in Thread] Current Thread [Next in Thread]