Pudding: Private User Discovery in Anonymity Networks

Pudding: Private User Discovery in Anonymity Networks

Speakers: Ceren Kocaogullar, University of Cambridge; Daniel Hugenroth, University of Cambridge; Martin Kleppmann, University of Cambridge; Alastair R. Beresford, University of Cambridge

Conference: IEEE S&P

YouTube: https://www.youtube.com/watch?v=EEUdslTwYZ8

Overview

In the evolving landscape of digital communication, end-to-end encryption has become a widely adopted standard for securing message content. However, the talk "Pudding: Private User Discovery in Anonymity Networks" by Ceren Kocaogullar and her collaborators at the University of Cambridge highlights a critical, often overlooked aspect of privacy: metadata privacy. This form of privacy protects information about a message's context, such as who is communicating with whom, when, and where. While anonymity networks like Tor and Nym are designed to provide robust metadata privacy, they traditionally lack user-friendly mechanisms for user discovery, leaving users to exchange complex, unmemorable addresses.

Pudding addresses this gap by proposing a novel application-layer protocol that enables private user discovery using familiar identifiers like email addresses, similar to how conventional messaging apps operate. The protocol is built on top of the Lupix anonymity network architecture and is designed to uphold the strong privacy guarantees inherent in such networks. By making user discovery practical and private, Pudding aims to remove a significant barrier to the widespread adoption of metadata-private communication systems, fostering an environment where users can connect securely without compromising their privacy.

The significance of Pudding lies in its potential to bridge the usability gap between mainstream messaging platforms and advanced anonymity networks. By integrating human-readable addresses and automated contact discovery, Pudding not only enhances the user experience but also maintains stringent privacy properties, including unlinkability, impersonation resistance, external identity verification, and membership unobservability. This work is crucial for enabling a new generation of privacy-preserving applications that are both secure and accessible to a broader audience, particularly for those who require strong privacy, such as journalists and whistleblowers.

Background

▶ Watch: Introduction to Pudding and the metadata privacy problem (0:00)

The push for digital privacy has largely focused on securing the content of communications through end-to-end encryption. While this is a vital step, it only addresses one facet of privacy. As demonstrated by numerous real-world incidents, the metadata surrounding communications—who talks to whom, when, and how frequently—can be just as revealing, if not more so, than the content itself. This information can expose relationships, activities, and even identities, making metadata privacy a paramount concern for truly secure communication.

Anonymity networks, such as Tor and Lupix (and its commercial deployment, Nym), are specifically engineered to provide strong metadata privacy. They achieve this by routing messages through multiple layers of "mix nodes" and "provider nodes," obfuscating the sender-receiver relationship. However, a persistent challenge for these networks has been the lack of a usable user discovery mechanism. Unlike traditional internet services that use memorable email addresses or phone numbers, anonymity networks typically generate long, opaque cryptographic keys or network addresses that are impractical for users to exchange or remember. For instance, a Nym address appears as a complex string of characters, making it difficult for users to find each other or for applications to integrate contact lists. This usability barrier significantly hinders the adoption of these powerful privacy tools.

Attempts to adapt traditional user discovery models, such as a centralized key lookup server, to anonymity networks quickly reveal severe privacy and security vulnerabilities. If an adversary controls such a server, they could learn who is looking for whom, thereby breaking unlinkability. They could also serve a malicious public key, leading to impersonation attacks where messages are redirected. Furthermore, a malicious user could query the server with arbitrary usernames to determine if a user exists on the network, compromising membership unobservability. These issues underscore the need for a discovery protocol specifically designed for the unique constraints and privacy requirements of anonymity networks.

Recognizing these challenges, the Pudding protocol was developed with four core privacy and security goals:

1. Unlinkability: Prevent an adversary from determining who is friends with whom.
2. Security against impersonation: Ensure that an adversary cannot redirect user messages or trick users into communicating with the wrong party.
3. External identity verification: Allow users to verifiably link their in-system identity to an external one, like an email address, crucial for trust in sensitive communications (e.g., journalists, whistleblowers).
4. Membership unobservability: Prevent an adversarial user from determining if a username belongs to a registered user unless that user explicitly chooses to disclose their presence.

These goals form the bedrock of Pudding, distinguishing it from conventional discovery mechanisms and making it suitable for the stringent privacy demands of anonymity networks.

Key Findings

▶ Watch: Why naive key lookup fails for anonymity networks (3:40)

Pudding introduces a robust and practical solution for private user discovery within anonymity networks, directly addressing the long-standing usability and privacy challenges in this domain. The core findings and contributions of this work are multifaceted, spanning protocol design, security guarantees, and practical implementation.

Firstly, Pudding successfully designs and implements an application-layer protocol that enables users to discover each other using familiar email addresses, akin to mainstream messaging applications like WhatsApp or Signal. This significantly enhances the usability of anonymity networks, making them more accessible to a broader user base without requiring modifications to the underlying network infrastructure.

Secondly, the protocol is structured around four distinct subprotocols: Lookup and Contact Init, Add Friend, and Register. Each subprotocol serves a specific function, from initial contact and key exchange to establishing long-term authenticated communication channels and optional user registration for discoverability. This modular design contributes to the protocol's flexibility and comprehensive coverage of user discovery needs.

Crucially, Pudding rigorously achieves its four foundational privacy and security goals:

• Unlinkability is ensured through the innovative use of deterministic single use reply blocks (SERBs) and blinded keys, preventing adversaries from linking search requests to users.
• Security against impersonation is maintained by requiring users to receive consistent responses from a majority of Discovery nodes, making it difficult for a malicious actor to inject false information.
• External identity verification is facilitated by leveraging existing email infrastructure, specifically DKIM signatures, to authenticate email addresses during registration, providing a trustworthy link to real-world identities.
• Membership unobservability is a cornerstone of Pudding, achieved by ensuring that search responses for non-existent users are indistinguishable from those for real users, and by relying on the anonymity network to hide message patterns, thus preventing user enumeration.

Finally, the practical implementation of Pudding on the Nym network demonstrates its viability and efficiency. Despite the inherent latency of anonymity networks, registration and discovery operations exhibit mean latencies of less than 13 seconds. The research also highlights that Pudding's performance is directly influenced by the throughput capabilities of the underlying anonymity network, suggesting that improvements in network speed will further enhance Pudding's responsiveness. These findings collectively establish Pudding as a significant advancement in making metadata-private communication both secure and user-friendly.

Technical Deep Dive

▶ Watch: Pudding's four core design goals for privacy and security (4:45)

Pudding is built as an application-layer protocol on top of the Lupix anonymity network architecture, requiring no modifications to the underlying network infrastructure. Lupix is characterized by provider nodes that act as user inboxes/outboxes, and multiple layers of mix nodes that relay messages, encrypting them in layers to obscure the path. A key primitive in Lupix is the single use reply block (SERB), which allows a recipient to reply to a sender without knowing the sender's public key or network address, as the SERB contains the necessary routing information prepared by the original sender.

Pudding leverages a set of Discovery nodes, specifically 3f+1 nodes, where 'f' is the maximum number of faulty or malicious nodes. This Byzantine fault tolerance ensures that the system remains operational and secure even if less than a third of the Discovery nodes are compromised.

Lookup and Contact Init Subprotocol

The core of user discovery in Pudding is the Lookup and Contact Init subprotocol, designed to enable Alice to find Bob by his email address while preserving privacy.

1. Deterministic SERB Generation: A crucial innovation is the modification of the SERB generation process to be deterministic. Instead of being random, SERBs are generated by seeding a pseudo-random generator with a hash of the lookup email address and a secret value shared among the Discovery nodes. This ensures that all honest Discovery nodes will generate the same SERB for a given user lookup request, which is vital for security against impersonation.

1. Blinding Public Keys: When Alice searches for Bob, each Discovery node generates a blinding factor derived from the same seed used for deterministic SERB generation. This blinding factor is then used to blind Bob's public key. The Discovery nodes respond to Alice with both the deterministic SERB and the blinded public key. They also send the blinding factor to Bob.

1. Reflector Mechanism: Alice uses the blinded public key to encrypt a message (e.g., a contact request) for Bob. She then creates a new message whose payload contains this encrypted note and the SERB she received. Critically, she does not use the SERB as the header directly. Instead, she sends this message to the Discovery nodes. The Discovery nodes then act as reflectors: they take the SERB from Alice's payload and use it as the header for a new message, sending Alice's encrypted note to Bob. This indirection prevents a malicious Discovery node from linking Alice's initial lookup request to the subsequent message sent to Bob.

1. Bob's Decryption: When Bob receives the message from the Discovery nodes, he blinds his private key with the blinding factor he previously received from the Discovery nodes. This allows him to decrypt Alice's message, which was encrypted with his blinded public key.

1. Membership Unobservability: If Alice searches for a non-existent user, the Discovery nodes blind a fake public key and generate a SERB for a fake address. Alice receives these values, which are indistinguishable from real ones, and proceeds as if the user exists. She encrypts her note with the fake blinded key and sends it to the Discovery nodes. The Discovery nodes reflect this message, but it ultimately gets dropped by the anonymity network because the SERB points to an invalid address. Because SERBs and blinded keys are pseudo-random and the underlying Lupix network hides messaging patterns, Alice cannot discern if the user exists or not, achieving membership unobservability.

Add Friend Subprotocol

The Add Friend subprotocol is used to establish long-term, authenticated communication channels between Alice and Bob after an initial contact. This is crucial for ensuring that users are indeed communicating with the correct person they intended to find.

• Modified Sigma Authenticated Key Exchange: Pudding employs a modified Sigma authenticated key exchange protocol. Sigma is chosen for its simplicity and proven correctness, though other authenticated key exchange protocols could be substituted. The modification specifically supports blinded key signatures, allowing the protocol to operate seamlessly with the blinded keys used in the discovery phase.
• Identity Verification: This subprotocol ensures that Alice can verify she is talking to the owner of "[email protected]", and similarly, Bob can verify Alice's identity if she chose to disclose her username in the initial contact message. This is particularly important for scenarios like a whistleblower contacting a journalist, where strong identity assurance is paramount.

Register Subprotocol

Registration in Pudding is optional but necessary for a user to be discoverable by their email address. It also plays a critical role in achieving membership unobservability.

• Paradox of Authentication: The protocol highlights a "paradoxical" requirement: to achieve membership unobservability, external verification of email addresses is needed. Without it, an attacker could register with arbitrary pseudonyms and, by observing success or failure, deduce if a username already exists.
• Email-Based Authentication: When Alice wants to register "[email protected]", she sends a message to the Discovery nodes, specifying one node (e.g., D4) to orchestrate the registration.
• Challenge-Response Mechanism: Each Discovery node generates a challenge value and sends it to D4. D4 collects these challenges (and generates its own), then sends Alice an email containing all challenges, her contact information, and username.
• DKIM Signature Verification: Alice replies to D4's email. Crucially, her response email is signed on its way out by her mail service provider using a DKIM signature. A DKIM signature is a digital signature on the email header, verifiable against a public key published by the domain owner in a DNS text record. This verification confirms that the email originated from an SMTP server authorized by the domain owner, preventing spoofing.
• Distributed Verification: D4 distributes Alice's signed response email to all other Discovery nodes. Each Discovery node verifies the DKIM signature and checks if its own challenge is included in the email body.
• Threshold Confirmation: If both verifications pass, the Discovery nodes register Alice. Alice waits for 2f+1 "registration successful" messages from the Discovery nodes to confirm her registration. This threshold ensures resilience even if the set of faulty Discovery nodes changes between subprotocols.

By combining these innovative subprotocols, Pudding provides a comprehensive, secure, and privacy-preserving user discovery mechanism for anonymity networks, making these powerful tools more usable for everyday communication.

Demo / Proof of Concept

▶ Watch: Pudding's architecture: application layer with multiple discovery nodes (6:10)

The Pudding protocol was not merely a theoretical construct; it was implemented as a proof of concept on the Nym network infrastructure. This practical deployment demonstrated the viability and performance characteristics of the proposed system in a real-world anonymity network setting, without requiring any modifications to Nym's core architecture.

The implementation focused on validating the operational speed and efficiency of the protocol's key functions: user registration and user discovery. The results indicated that all operations exhibited mean latencies of less than 13 seconds. This is a significant finding, as initial contact and registration are typically one-time or infrequent operations, making this level of latency acceptable for user experience, especially given the inherent delays introduced by routing messages through multiple mix nodes in an anonymity network.

The project also observed that the performance of Pudding is directly influenced by the throughput limits of the underlying anonymity network. This implies that as anonymity networks like Nym continue to optimize their performance and increase their message throughput, Pudding's operational latencies would further decrease, leading to an even more responsive user experience. This practical demonstration underscores Pudding's readiness for integration into privacy-focused applications built on Nym and similar anonymity networks.

Defensive Implications

▶ Watch: Addressing SURB determinism and unlinkability in user discovery (7:40)

The Pudding protocol carries significant defensive implications, primarily by enhancing the security and privacy posture of users and applications operating within anonymity networks. For defenders—whether they are privacy advocates, application developers, or security architects—Pudding offers a blueprint for building more usable and robust privacy-preserving communication systems.

Firstly, Pudding directly addresses a critical usability gap that has long hindered the widespread adoption of anonymity networks. By providing a private and verifiable user discovery mechanism using familiar identifiers like email addresses, it removes a major barrier for average users. This means that applications built on top of anonymity networks can now offer a user experience closer to mainstream messaging apps, encouraging more users to embrace metadata-private communication. Increased adoption of such systems inherently strengthens the overall privacy landscape, making it harder for adversaries to conduct mass surveillance or target specific individuals.

Secondly, the protocol’s stringent adherence to its four privacy goals – unlinkability, security against impersonation, external identity verification, and membership unobservability – provides robust protections against various adversarial tactics. Defenders can leverage these properties to:

• Prevent user enumeration: By ensuring membership unobservability, Pudding makes it extremely difficult for an attacker to build lists of active users on an anonymity network, thereby protecting individuals from being identified or targeted simply for their participation.
• Combat impersonation and phishing: The requirement for deterministic SERBs, blinded keys, and a majority consensus from Discovery nodes for key delivery significantly reduces the risk of an attacker impersonating a legitimate user or redirecting communications to malicious endpoints. The Add Friend protocol’s use of authenticated key exchange with blinded key signatures further solidifies this defense, ensuring users can verify who they are communicating with.
• Establish trust with external identities: The Register protocol's innovative use of DKIM signatures for email verification provides a strong, verifiable link between an in-system identity and an external email address. This is invaluable for high-stakes communications, such as journalists protecting sources or whistleblowers verifying the authenticity of their contacts. Defenders can integrate similar external verification mechanisms to build verifiable trust into their privacy-preserving applications.

Finally, Pudding serves as a strong example of how to design privacy-preserving protocols that are resilient against Byzantine adversaries. The use of 3f+1 Discovery nodes ensures that the system can tolerate a significant number of faulty or malicious actors without compromising its integrity or privacy guarantees. This architectural approach provides a valuable lesson for designing other distributed privacy systems, emphasizing the importance of fault tolerance in adversarial environments.

In essence, Pudding empowers defenders by providing the tools and principles to build a more private and secure digital ecosystem. It demonstrates that usability and strong privacy guarantees are not mutually exclusive, offering a pathway for broader adoption of technologies that safeguard fundamental communication rights.

Key Takeaways

• Metadata privacy is as crucial as content privacy: While end-to-end encryption secures message content, metadata (who, when, where) can be equally revealing and requires specific protection.
• Pudding solves private user discovery in anonymity networks: It enables users to find each other using familiar email addresses on networks like Lupix/Nym, overcoming a major usability barrier.
• Strong privacy goals are achieved: The protocol ensures unlinkability, security against impersonation, external identity verification, and membership unobservability, setting a high standard for privacy.
• Innovative technical mechanisms are employed: This includes deterministic SERBs, blinded keys, a reflector mechanism for message delivery, and DKIM signature verification for robust identity authentication.
• Byzantine fault tolerance is central to security: Pudding's use of 3f+1 Discovery nodes ensures resilience against a significant number of malicious participants.
• Practical implementation shows viability: The protocol works on the Nym network with acceptable latencies (mean less than 13 seconds for operations), demonstrating its readiness for real-world applications.

About the Speaker(s)

The talk was presented by Ceren Kocaogullar, who is affiliated with the University of Cambridge. Her collaborators on this paper include Daniel Hugenroth, Martin Kleppmann, and Alastair R. Beresford, all also associated with the University of Cambridge. Their collective work focuses on advancing privacy and security in digital communication systems, particularly within the context of anonymity networks.