CSC 2231: Project Progress Report 1 Title: Fine Grained Access Control in Online Social Networks Group members: Amin Tootoonchian, Geoff Salmon, Ahmad Ziad Hatahet The Problem Revisited -------------------- A user, called the publisher, has content they wish to share on an online social network (OSN). Although the OSN may support certain access controls, the publisher wants to further restrict who can view the content to a set of people, called friends, with a certain relationship to the publisher. We assume that the publisher has access to his or her friends' public keys. Ideally the OSN would support fine-grained access control. In the absence of such support, we have proposed and evaluated several alternate approaches. Direct Approach: Encrypt Data ---------------------------------------------- Store content directly on the publisher's profile encrypted with a shared relationship key, which is given to all friend's in the relation. Problems: - It's undesirable to give the actual encrypted content to everyone viewing the publisher's profile. Those who cannot decrypt it may be tempted to store the encrypted content until a time when the encryption used can be easily broken. - Requires distributing and maintaining the relationship keys. - Changing a relationship key is expensive. Indirect Approach 1: Encrypt Exact Location of Data --------------------------------------------------- The publisher's profile contains only the locations of the real content, and the locations are encrypted with a shared relationship key. The actual content is stored elsewhere. Ideally the locations of content would be embedded in fake content of the same type as the real content, which allows the fake content to use the same features that the OSN would have provided to the real content. For example, the location of a real image would be embedded in a fake image. If the OSN provides thumbnail albums and comments for images, then the fake image could also appear in an album and receive comments. Improvements of Previous Approach: - Avoids giving the encrypted content to everyone. Problems: - Requires distributing and maintaining the relationship keys. - Changing a relationship key is expensive. Indirect Approach 2: Encrypt Partial Location of Data ---------------------------------------------------- In the previous approach, the content's real location was the same for each friend. In this approach it will be unique for each friend. The encrypted locations embedded in the publisher's profile contain only part of the data's actual location. The rest of the location is a unique identifier given to the friend by the publisher. This allows the publisher to revoke a friend's access to content by removing the copy of the content unique to that friend. Depending on the features provided by the server hosting the content, this approach may require hosting redundant copies of the content. Improvements of Previous Approaches: - Revoking access doesn't require the relationship key be replaced, but the key should still be changed over time. Problems: - Requires distributing and maintaining the relationship keys. - Changing the relationship key, although less frequent, is still expensive. - Redundant copies of the real content may be required. Indirect Approach 3: Location Map --------------------------------- Use two levels of indirection. The fake content on the publisher's profile contains an identifier of the real content and the URL of a LocationMap. The embedded information is not encrypted, so anyone can find the LocationMap. The LocationMap contains the real location of the content encrypted with the public key of each friend that is able to see the image. In practice, this will likely be implemented as a two-level mapping from user to relationship key and relationship key to content location. Improvements of Previous Approaches: - Relationship keys do not have to be distributed to every friend. They are contained within the LocationMap. - Any change to the relations or locations of images can be accomplished by replacing the LocationMap. The fake content on the OSN profile does not need to change. Problems: - Requires a place to store the LocationMap in addition to the real content. - LocationMap may reveal information about relation members. Progress -------- We have defined a format for the location map. Here is an example: ABEWRDFAEDC DEGSDFGERQF OSTEWFGSDGD WEWERWESDFS WVXSDFTEGQS 128732389741980 09219874567423368 Given a location map URL and a file id, a user would look up real content as follows: 1) Fetch the location map 2) Retrieve the file element corresponding to the file id, which contains the relations which have access to that file and locations encrypted with each locations key. 3) Retrieve the relation element for each relation, which contain the users in that relation 4) Determine if the hash of the user's public key matches any of the friend ids 5a) If there is no match, then the user cannot access the content. FAIL 5b) If there is a match, decrypt the key element's value with the user's private key to produce the relation's key. 6) Decrypt the actual location found in step 2 with the key from step 5b. 7) Fetch the actual content. SUCCESS Prototype --------- We have begun implementation of the LocationMap approach in a firefox extension. We initially prototyped several necessary features: - Replacing images in viewed web pages with other images - Fetching and parsing an XML document and retrieving values from it - Intercepting form submissions, replacing the uploaded file with another and posting the original file to another page. Next we implemented a limited prototype of the entire process. The scenario involves two PHP scripts. One script provides the features needed to host the real content: storing pictures with random URLs and storing a text file with a specific name. The other PHP script serves as the OSN profile where the publisher will post the images. The prototype extension intercepts images posted to our testing OSN, replaces them with a fake image, and uploads the real image to the other script with a random name. It then fetches and updates the LocationMap to include an entry for the new picture. When viewing the image on the test OSN, the extension fetches the LocationMap, looks up the images by name and replaces the images with the real ones. Limitations of the Prototype --------------------------- The LocationMap in the prototype is simplified and maps image names directly to real locations. There is no cryptography involved, and we have not implemented embedding information in images, so the URL of the LocationMap is hard coded in the firefox extension. Next Steps ---------- - Store some local state on the client containing the user's public/private key, the friends' public keys and the location of the user's LocationMap(s). - Provide a UI for managing local content and updates to the LocationMap. - Encrypt the contents of the LocationMap as described in the example above. - When posting an image, show a dialog asking the user whether to replace the image and, if so, which relations should have access to the image. - Embed information in images. This seems theoretically possible but from our initial research appears to be difficult to implement in a firefox extension. - Interface with real OSNs to host the real content. Future Problems --------------- Once the extension is performing the whole process, large LocationMaps may cause performance problems. It may be necessary to cache location maps or split them across multiple files. Many OSNs store an image at multiple resolutions. If a user is viewing a thumbnail album with many small, fake images it is unnecessary to fetch full resolution copies of the real images. To solve this we can store multiple copies of the real image at several resolutions and fetch the one closest to the desired resolution. Another interesting problem is how to reveal less information about the relations and friends to a third party reading the LocationMap. Timetable --------- Throughout the remaining time, we will attempt to improve on the LocationMap approach. Here are some specific milestones Nov 7: - Use the real LocationMap format which requires the following. Client must support cryptography and must show a UI dialog to the user to choose relations that get access to a image. Nov 14: - Post real images to a real website such as Picassa Web. - Investigate embedding data in images.