Paste: DSNP Protocol

Author: dbp
Mode: text
Date: Tue, 18 May 2010 22:38:21
Plain Text |

    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 fetched using SSL. This guarantees that a key has been provided by
       the server hosting the identity and has not been tampered with.


    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.


    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

    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.


    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

       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 

       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.
       ++NOTE: Doesn't this break the whole guarantee in the first place? since
               then if someone was supposed to have had their number updated but
	       hadn't yet, and recieved a message with the old number, then they 
	       would pick their highest number, which would be wrong.++

    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.


    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.


    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.

New Annotation