[messaging] distributed social graph, was: collaborative random number generation

carlo von lynX lynX at i.know.you.are.psyced.org
Sat Dec 12 06:39:53 PST 2015

On Mon, Dec 07, 2015 at 11:28:43PM -0800, Trevor Perrin wrote:
> It's not clear how this relates to secure messaging.  Are you
> proposing something like this?:
>  1) Every user has a key pair.


1) Every user has several key pairs for circles of their social
   network. There is one public identity which is available to
   attackers and only gives access to obvious public contacts,
   if at all.

This implies that it takes a social exchange protocol such as
PSYC in order to let "friends" have access to the social graph
in the intended ways. First they make contact with the public
identity and after having established authenticity are passed
the "public key" information of private identities.

The terminology "public key" is getting less and less adequate
in a setting where pubkeys are being used like access tokens.

>  2) Every user assigns "petnames" to other users.

... within their private identities, chosen according to people who
*should* be able to access each other's social graph. If not you
can still generate private identities for each contact.

>  3) Petnames are short, human-readable names (basically just the names
> you use for people in your address book).
>  4) A user assigns petnames by signing the recipient's (petname,
> public key) and publishing that record in a DHT
>  5) The location in the DHT is determined by a hash of the issuing
> user's public key and the petname.

Improvement: The location in the DHT is determined by a hash of the
issuing user's private "public key" and the petname. This procedure 
can be repeated for as many social circles as appropriate and isn't
accessible to unauthorized attackers.

>  6) The data stored in the DHT entry is encrypted by a hash of the
> issuing user's public key and the petname.
>  7) Users can lookup a chain of petnames, starting from any user's
> public key.  For example, if I know your public key, I can lookup your
> "Alice", and that person's "Bob", and so on, so that I get "Jeff's
> Alice's Bob" (SDSI style naming).

Only "friends" that have been privately given access to the private
identity can attempt to brute force the social graph given to them,
but they might as well have also been given a list of people in that
circle - as the "security by obscurity" option isn't essential to the
functionality and only incentivates attacks.

> If that's the idea, I have the same concerns I expressed earlier about GNS:
> https://moderncrypto.org/mail-archive/messaging/2014/000943.html

Could have been useful to point me to it back in November 2014 when
I first joined the list and mentioned GNS - so we could have cleared
up this misunderstanding a year earlier. There was another occasion
to correct this in January when we again spoke about GNS as an
alternative to DP5.

(from that message)
> * "Query privacy" doesn't seem enough to prevent harvesting a lot of the social graph.

Correct. It takes the management of multiple identities which has
been implemented during the last year I believe. "Query privacy"
is still a great feature for applications where the public key
may need to be truly public but the look-up items do not need to be
easy to guess strings.

>  * Recursively-scoped names are going to be a confusing and new
> concept for most users.

I too find jack.jill.gnu indeed too complicated for some of us less
techie humans, but if you provide a proper GUI it becomes pretty simple:

You go to Jill's profile, view her friends and click on Jack. Then
you have the option to adopt Jack as a friend trusting Jill to have
given you the correct public key. Even better if all the social
graphs of your other friends are available to your social app, then
it can tell you that Jack is the same Jack that is also in Peter,
Paul and Mary's social circle. That's the kind of thing secushare is 
meant to do - making distributed e2e crypto as easy as using Facebook.
You see a picture, a nickname and the list of friends in common -
if all agreed to let you have this information. If you have no friends
to trust you can still use traditional authentication means.

> The Tor HSdir mechanism is solving a different problem - it makes it
> hard to become a DHT node that will store certain entries.

Something GNS already provides, AFAIU.

>  I don't know how much you care about that.  I also don't know how
> feasible it is for users to frequently re-publish all their petnames,
> under different randomization.

secushare also considers using its distributed pubsubs as a
means for keeping the social graph in *alternative* to GNS as it
doesn't need any refreshes and may therefore prove a lot more
efficient. The implementation of psycstore is available in the 
gnunet source code tree. The pubsubs' purpose is to model all
synchronous and asynchronous, one-to-one and multiparty multicast
communications that a social networking medium requires, but
nothing keeps it from also hosting the social graph rather than
to have it in GNS. Yet, I haven't found anything semantically
wrong about GNS either, so we will want to try out both methods
and see which ones performs better.

  E-mail is public! Talk to me in private using encryption:

More information about the Messaging mailing list