Abstract: The design of secure and usable access schemes to personal data represent a major challenge of online social networks (OSNs). State of the art requires prior interaction to grant access. Sharing with users who are not subscribed or previously have not been accepted as contacts in any case is only possible via public posts, which can easily be abused by automatic harvesting for user profiling, targeted spear-phishing, or spamming. Moreover, users are restricted to the access rules defined by the provider, which may be overly restrictive, cumbersome to define, or insufficiently fine-grained. We suggest a complementary approach that can be easily deployed in addition to existing access control schemes, does not require any interaction, and includes even public, unsubscribed users. It exploits the fact that different social circles of a user share different experiences and hence encrypts arbitrary posts. Hence arbitrary posts are encrypted, such that only users with sufficient knowledge about the owner can decrypt. Assembling only well-established cryptographic primitives, we prove that the security of our scheme is determined by the entropy of the required knowledge. We consequently analyze the efficiency of an informed dictionary attack and assess the entropy to be on par with common passwords. A fully functional implementation is used for performance evaluations, and available for download on the Web.
Introduction
Online Social Networks (OSNs) currently present users with a binary choice regarding privacy: posts are either restricted to a pre-defined list of "friends" or they are made entirely public. The former approach is often too restrictive, blocking individuals in a user's wider social circle who are not explicitly on a contact list. Conversely, public posts are vulnerable to automated web crawlers that harvest data for user profiling, identity theft, and targeted phishing.
This paper introduces Partial Knowledge-based Access Control (PKA), a non-interactive encryption scheme designed to protect "public" social media posts from automated harvesting while allowing friends—even those not explicitly connected on the platform—to access the content.
The PKA Framework
The PKA system leverages the fact that individuals within the same social circles share common experiences and knowledge. It utilizes three well-established cryptographic building blocks to secure content:
- Symmetric Encryption (AES-256): Used to encrypt the actual content of the post.
- Cryptographic Hashing (SHA-256): Converts attribute values (e.g., a city name or a shared memory) into encryption keys.
- Shamir’s Secret Sharing (SSS): This allows a master key to be split into $n$ shares, where any $t$ shares are sufficient to reconstruct the secret.
When a user creates a post, the PKA plugin generates a master key $K$ and encrypts the post. It then takes $n$ personal attributes and uses SSS to create $n$ shares of $K$. Each share is encrypted using the hash of one attribute value. To read the post, a recipient must correctly provide $t$ out of $n$ attributes. This $t$-of-$n$ flexibility accounts for the fallibility of human memory, ensuring the system remains usable even if a friend forgets a specific detail.
Security via Social Entropy
The security of PKA is rooted in "social entropy"—the difficulty for an outsider to guess the chosen attributes. While a dedicated stalker might uncover specific details, the primary goal of PKA is economic deterrence. By forcing an automated crawler to attempt millions of attribute combinations for every single post, the computational cost of the attack becomes higher than the value of the stolen data.
To test this resilience, researchers utilized datasets from German social networks (meinVZ and XING) alongside official demographic data to simulate an "informed dictionary attack," where a bot uses common names, cities, and universities to guess attributes.
Evaluation and Results
The researchers found that PKA is highly resilient to automated attacks. For a 3-of-4 attribute scheme, an informed dictionary attack would require an average of 54 days of continuous computing to crack a single protected post.
As illustrated in the performance evaluations, the success probability for bots remains negligible even with a high number of attempts. Furthermore, the system introduces minimal overhead. A proof-of-concept Firefox extension demonstrated that key generation and encryption take less than 45 milliseconds, while decryption takes approximately 31 milliseconds—speeds well below the typical latency of loading a webpage.
Conclusion and Future Work
PKA offers a clever middle ground for OSN privacy, providing a deployable solution that protects against mass data harvesting without requiring complex manual key exchanges. While it cannot protect against targeted social engineering if a user chooses easily discoverable attributes, it significantly raises the bar for automated threats. Future research will explore extending the implementation to multimedia content and implementing weighted attribute schemes to further refine security and usability.
Summary updated