[foaf-dev] [foaf-protocols] Fwd: working on a protocol for distributed social networking

[Peter Ansell]

2009/8/16 Melvin Carvalho <melvincarvalho at gmail.com>:
> FY: An outline of DSNP protocol is posted here for reference.  I think
> there are a lot of interesting elements including secure remote
> friending, secure distributed activity stream, and server side private
> key management.  I'll add some comments when I've been through it in
> more detail ...
>
>
> IDENTITY INITIALIZATION
> =======================
>
> 1. A user name and password is requested. These credentials will be used by the
> user to login as the owner of the identity.
>
> 2. A URI consiting of the site root name followed by the user name as the last
> component is assigned. This is an internet facing web address that the user has
> control of (possibly through a service provider). It represents their identity.
>
> 3. An RSA key pair is created. The key has no passphrase.
>
> 4. The public portion of the key is made publically available. The key must
> always be This must always be fetched using SSL.
>
> OWNER LOGIN
> ===========
>
> User submits credentials via a web form underneath URI and recieves a session
> cookie that indicates to the server that the user is logged in.
>
> FRIENDSHIP REQUEST
> ==================
>
> The person requesting friendship is the friender, with identity URI.
> The person who is receiving the request is the friendee, with FR-URI
>
> 1. The friender fills in a friend request form at FR-URI
>      a) friender answers a challenge (generic CAPTCHA, or personalized)
>      b) friender submits URI
>
> 2. Friendee server processes the request:
>      a) verifies challenge response
>      b) fetches the public key for URI (using SSL)
>      c) randomly generates a one-way relationship id (REQUESTED-RELID)
>      d) randomly generates a one-way request id (REQUESTED-REQID)
>      e) encrypts REQUESTED-RELID to friender and signs it
>      f) makes message available to be fetched using REQUESTED-REQID
> to identify it
>      g) redirects the user's browser to
> https://URI/return-relid?uri=FR-URI&reqid=REQUESTED-REQID
>
> 3. Friender server processes the return-relid request:
>      a) verifies browser is logged in as owner
>      b) fetches public key for FR-URI (using SSL)
>      c) fetches encrypted REQUESTED-RELID from FR-URI using REQUESTED-REQID
>      d) decrypts and verifies REQUESTED-RELID
>      e) randomly generates RETURNED-RELID
>      f) randomly generates RETURNED-REQID
>      g) encrypts "REQUESTED-RELID RETURNED-RELID" to friendee and signs it
>      h) makes message available at to be fetched using RETURNED-REQID
> to identify it
>      i) redirects the friender to
> https://FR-URI/friend-final?uri=URI&reqid=REQID
>
> 4. Friendee server processes the friend-final request:
>      a) fetches encrypted RETURNED-RELID using RETURNED-REQID
>      b) decrypts and verifies message, must contain correct REQUESTED-RELID
>      c) stores request for friendee to accept/deny
>
> FRIENDSHIP ACCEPT/DENY
> ======================
>
> The next time the friendee logs in they are presented with the friendship
> request. They can either accept or deny the request.
>
> The acceptor sends accept notification with both relids. They are sent back
> indicating that the friendship was registered on the other end. The acceptor
> then registers the friendship and sends a registered message. It can can now
> send broadcast key and broadcast tree insertion messages. The other end can
> send these messages after it receives the registered message.
>
> PUBLISHING TO FRIENDS
> =====================
>
> 1. Broadcast Encryption Keys
> ----------------------------
>
> Use a broadcast key. Gives the sender some control over who can read broadcast
> messages. Requires sending out session keys ahead of time. This does not stop a
> bad friend from forwarding a session key. But the protocol doesn't have this
> feature. Session keys must be signed.
>
> 2. Distribution Tree
> --------------------
>
> The most simple approach is to iterate through your list of friends and deliver
> broadcast messages. However, a large number of friends multiplied by lots of
> activity results in many messages.
>
> To mitigate this cost a user's set of friends is organized into a complete
> binary tree and broadcast messages are forwarded through this tree, resulting
> in log n steps to distribute a broadcast.
>
> Doing this means that each of your friends must know the server at which a
> couple of your other friends have their identity hosted. This revelation does
> not cross friend-partition boundaries, however. It is a minor weakening of the
> claim that your friend list is private.
>
> This reduces the time to get messages out, but complicates matters when a node
> fails to forward a message on behalf of a friend. The approach I'm considering
> is to send acknowledgment messages back up the tree of friends and back to the
> originator as confirmation. If the ack does not arrive back in time there is a
> distribution problem that needs to be corrected by discovering the faulty node
> and removing it or swapping it with a leaf node. The message can then be
> rebroadcast.
>
> A faulty node can be reported to the originator at the point of failure, either
> due to a timeout, or an inability to connect.
>
> 3. Tree Generaion Numbers
> -------------------------
>
> To speed up the distribution of messages, a user's list of friends is
> organized into a tree. Each friend forwards broadcast messages on to
> other friends. This requires that there be agreement on the correct
> structure of the tree among a user's friends. Friends do not need to
> have a view of the complete tree, just their children.
>
> Another way to view the issue of agreement is that all operations that
> modify the friend's view of the tree need to be atomic across all
> friends that are involved in the modification. A message that passes
> through the tree must either see all of a change or none of it. When
> adding a member to the tree this is easy, the new member is added as a
> leaf node and just one node (its parent) needs to be modified.
>
> When removing a node from the distribution tree there is more than one
> modification that needs to be made among the friends. To ensure that
> these modifications are atomic, I am using a tree generation number.
> Each broadcast message carries with it the generation of the
> distribution tree that should be used to propagate the message. When the
> tree is modified, the generation number is incremented. Friend nodes
> that are modified keep the old tree generation data around during the
> modification process and continue to use it for any messages that arrive
> with the old generation number. When the changes are complete, new
> messages are sent with the new generation number, making the new tree
> effective.
>
> While this gives us atomic operations, it has the unfortunate property
> that all nodes need to have their generation number updated even if they
> are not involved in an update to the tree. To get around this, friends
> do not look up the exact generation number of messages to find forward
> information, but rather the youngest generation that is less than or
> equal to the generation number of the message. This lets us avoid
> updating the generation number with every friend.
>
> 4. Roles and Friendship Types
> -----------------------------
>
> The different roles poeple play in their lives are often reflected in a
> categorization of their relationships. It would be useful in DSNP to support
> friendship categories. Each category should have it's own broadcast key and the
> distribution trees should not be disconnected. The categories should not
> necessarily be comprised of disjoint sets of friends however. Your brother can
> be both in your friend category and your family category. You grandmonther,
> however, can just be in your family category so you can shelter her from the
> details of that crazy weekend in Montreal.
>
> LOGIN AS A FRIEND
> =================
>
> This allows people to login to a friend's page to see the content that has been
> summarized by their feed. It is an open-id style login.
>
> User:     URI,    RELID
> Friend:   FR-URI, FR-RELID
>
> 1. User fills in a login-as-friend form
>      a) User visits https://FR-URI/login-as-friend
>      b) submits URI
>
> 2. The friend's server processes the request.
>      a) verifies that URI is a friend
>      b) randomly generates a token
>      c) encrypts the token to the user and signs it.
>      d) makes it available under to be fetched with FR-RELID as identifier
>      e) redirects user to https://URI/return-token?uri=FR-URI
>
> 3. The user's server verifies the user owns the identitiy.
>      a) checks that FR-URI is a friend
>      b) if browser is not logged in, fails the process (possibly with
> redirect to loging screen)
>      c) fetches the token using from FR-URI using FR-RELID to identify it
>      d) decrypts and verifies the token
>      e) redirects the browser to https://FP-URI/submit-token?uri=URI&token=TOK
>
> 4. Friend login final
>      a) Verifies (URI, TOK)
>      b) grants friend credentials to the browser using cookie-based session.
>
> CHARACTERISTICS
> ===============
>
> * Your list of friends can be treated as private information. It is impossible
> for someone to probe your list of friends if you don't want to publish it.
> The list must be explictly granted, even to current friends (see next point
> for a minor exception). This makes it possible to partition your
> relationships into differnet groups, such as family, close friends,
> co-workers, and people you hardly know but might like to get to know better.
>
> *The user must trust the server that is hosting their identity. But like email,
> blogs, and other forms of internet identity, we are free to choose our service
> providers and the truely paranoid and technically inclined are free to host
> their own identity on their own server. Perhaps a more difficult problem is
> that the user must trust the server that is hosting their friend's identities.
> However, this is not a problem unique to DSNP. This is true of email as well.
>
>

In any distributed scenario you are going to have to trust all parties
that have access to enough information in order to read unencrypted
communications. Transferring public keys by encapsulating the
communication in SSL as is frequently referred to in this model
doesn't have anything to do with the fact that all of the servers have
access to the freetext of the communications, including all of the
public keys, and apart from a captcha, which is uniquely binding this
protocol to humans, the server could have been anyone once the
connection is made. What allowance is there in the model for non-human
participants given the reliance on one-time challenges before
relationships are initialised?

If you really want to be secure in a distributed scenario it would be
better to have user managed communication so that the servers only
know about routing protocols and never have enough information to
decrypt communications. There is nothing stopping a particular server
from routing the message to anywhere it wants, other than a moral
imperative not to do this with users messages. A level of deniability
with distributed messaging never goes astray... Although this is
common to email, if you are trying to make up a secure distributed
version of email (in a similar way to Wave), then you should offer
something more than the idea that you simply have to trust every
server and hope for the best. Step 2 in "LOGIN AS A FRIEND" is
particularly worrying in this respect, as it requires the users
browser to have faithfully accessed the authorisation for its own
identity in order to confirm this with the friends server that is
waiting on this step for identity authentication as the submission of
a simple URI matching the users identity has no meaning for the
friends server really. Maybe Step 3C is incorrect but I would imagine
the friend server would at least have to access the URI directly
without the users involvement to have any sort of certainty about the
process.

It might be nice to make the message distribution more efficient by
having a distributed broadcast model, but making it necessary that
tree servers need to be informed about the fact that a change has
occurred to the list of people being sent a particular communication
chain seems to leak information, as a rogue, (or overloaded/dead)
server could use this to either intentionally or unintentionally
disrupt the communication because it may be required to know about at
least a subset of the peers in order to be a necessary part of the
distribution. Some sort of failsafe communication is necessary to get
around normal network anomalies, even though there is apparently some
sort of atomicity with at least changes to the set of message
receivers. Relying on users back to the originating server through the
distribution tree allows some sort of knowledge, but as I said before
what is stopping a rogue server from acknowledging all of its peers to
have received the message without sending the actual message, and how
much of a pain would it be to have to resend every message just to
accommodate for one unresponsive peer that happens to be somewhere
between the two servers?

How is this distinctly different from the distributed model that the
Google Wave XMPP model uses to manage communications and authorise
users? If you could review this in comparison to that model [1]  (as
it seems to have a lot in common with this) it would be good.

It would also be nice to simply use OpenID or OAuth for authentication
instead of trying to replicate it as part of the model when the
elements match up pretty cleanly between the two models since the
authentication isn't actually distributed like the rest of the model
so it would reduce the dependencies for the model if it was not
necessarily included.

Cheers,

Peter

[1] http://www.waveprotocol.org/draft-protocol-spec