Onion Franking: Abuse Reports for Mix-Based Private Messaging

Onion Franking: Abuse Reports for Mix-Based Private Messaging

Speakers: Matthew Gregoire

Conference: NDSS Symposium

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

Overview

In the realm of secure communication, end-to-end encrypted (E2EE) messaging systems have become the gold standard for protecting message content. However, as Matthew Gregoire highlights in his NDSS Symposium talk, "Onion Franking: Abuse Reports for Mix-Based Private Messaging," the privacy challenge extends beyond message content to message metadata—information about who is communicating with whom. This metadata, often overlooked, can be just as sensitive as the message itself, with the former director of the NSA famously stating, "we kill people based on metadata." While techniques like mix nets and DC-nets offer robust metadata hiding, they introduce a significant dilemma: how can platforms moderate abusive content when they are intentionally blind to sender-recipient relationships and message content?

Gregoire's talk introduces Onion Franking, a novel solution designed to bridge this gap. This contribution specifically targets metadata-hiding messaging platforms built upon onion encryption, such as the Tor network or similar mix-net architectures. The core problem Onion Franking addresses is the inability of existing message franking techniques—which enable abuse reporting in standard E2EE systems like Facebook Messenger's "secret conversations"—to function within a metadata-hiding context without compromising user privacy. The talk demonstrates how Onion Franking not only achieves abuse reporting in these highly private environments but does so with strong performance guarantees, significantly outperforming prior work and even matching the efficiency of E2EE message franking.

This research by Matthew Gregoire is crucial because it tackles a fundamental tension in secure communication design: the need for both robust privacy and effective platform moderation. As online abuse continues to be a pervasive issue, systems that prioritize user privacy often face criticism for enabling bad actors. Onion Franking offers a path forward, demonstrating that it is possible to maintain strong metadata hiding properties while providing mechanisms for users to report and platforms to act upon abusive messages. Furthermore, the talk introduces advanced concepts for stronger accountability, ensuring that even the moderation process itself cannot be exploited or subverted by malicious actors, a critical step towards building truly trustworthy and resilient private communication systems.

Background

▶ Watch: Metadata hiding: a critical privacy challenge (0:00)

The landscape of secure messaging has evolved significantly, with end-to-end encryption (E2EE) becoming a foundational component for protecting the confidentiality of communications. E2EE ensures that only the sender and intended recipient can read messages, safeguarding them from eavesdropping by the platform or third parties. However, as Gregoire emphasizes, the protection offered by E2EE is often limited to the message content. Information about who is talking to whom, known as message metadata, frequently remains exposed. For individuals in sensitive situations, such as whistleblowers communicating with journalists, the mere fact of a connection can be highly compromising.

To address this metadata exposure, advanced techniques like mix nets and DC-nets have been developed. These systems, including practical implementations like onion routing used in the Tor network, are designed to obscure the sender-recipient relationship by routing messages through a series of intermediate servers that shuffle, delay, and re-encrypt traffic. While highly effective against network surveillance, these metadata-hiding systems introduce a new challenge: abuse reporting.

In traditional E2EE messaging, if a user receives an abusive message, they can report it to the platform. The platform, possessing a moderator key (or similar mechanism), can then verify the message's authenticity and content to take appropriate action. This capability is often implemented using a technique called message franking, as seen in features like Facebook Messenger's "secret conversations." Message franking works by having the sender compute an encryption of the message (C1) and a commitment to the message plaintext (C2). This information, along with message context (sender/recipient identities, timestamp), is sent to the server, which computes a MAC tag on the relevant franking data. The receiver verifies C1 and C2 and displays the message. If a report is made, the receiver sends the message plaintext and franking information to the server, which can then validate the report and take moderation actions. The key insight here is that "just by adding a little bit of bookkeeping, we can enable abuse reporting on end-to-end encrypted messages," without allowing the reporting mechanism to become a new vector for abuse.

However, directly applying message franking to metadata-hiding systems is problematic. In such environments, the platform is deliberately designed not to know the sender, the recipient, or even the contents of a message in transit. If the sender computes C1 and C2 and sends it to a metadata-hiding platform, the platform cannot compute any "message context" because it doesn't know the identities involved. Consequently, the platform cannot later be convinced that a specific user sent a reported message, rendering the franking mechanism ineffective or, worse, requiring a compromise of the metadata-hiding properties. This tension between privacy and safety forms the core problem that Onion Franking seeks to resolve.

Key Findings

▶ Watch: Understanding Message Franking for E2EE systems (2:00)

Matthew Gregoire's research on Onion Franking delivers several significant contributions to the field of secure messaging and abuse reporting:

1. Efficient Abuse Reporting for Onion-Encrypted Systems: The primary finding is the development of Onion Franking, a novel scheme that enables robust abuse reporting for metadata-hiding messaging platforms based on onion encryption. This addresses a critical gap where existing message franking techniques either failed or completely compromised the metadata privacy these systems are designed to provide.

1. Strong Performance Guarantees: Onion Franking achieves remarkable performance improvements over prior works attempting to combine metadata hiding with abuse reporting. Gregoire demonstrates that while previous solutions incurred "one to two orders of magnitude of overhead" compared to standard E2EE franking, Onion Franking brings performance "on par with end-to-end encrypted message franking" across various overhead metrics, all while preserving metadata privacy. This efficiency makes it a practical solution for real-world deployments.

1. Necessity of Breaking Abstractions for Enhanced Security: A key insight from the research is that achieving stronger security properties, specifically the ability to perform abuse reporting within a metadata-hiding context, requires a departure from traditional architectural abstractions. The design of Onion Franking necessitates a more integrated approach, where the franking data is carefully managed and transformed by the mix-net servers themselves, rather than being treated as a separate, opaque payload.

1. Introduction of Stronger Accountability Notions: Beyond merely enabling abuse reporting, Onion Franking introduces and addresses a more advanced security concern: moderator collusion. The scheme provides mechanisms to enforce honest moderator behavior at message sending time, verifiable by the message receiver. This prevents scenarios where a malicious moderator could collude with a user to render their messages unreportable.

1. General Applicability of Accountability Enhancements: The techniques developed for stronger accountability—specifically, the use of zero-knowledge proofs (ZKPs) and probabilistic guarantees via trap messages—are not limited to Onion Franking alone. Gregoire highlights that these methods are "applicable to message franking in general," meaning they can be used to enhance the accountability of existing E2EE message franking schemes, providing broader benefits to the secure messaging ecosystem.

In essence, Onion Franking demonstrates that the seemingly contradictory goals of strong metadata privacy and effective abuse reporting can be reconciled efficiently and securely, pushing the boundaries of what is considered achievable in private communication systems.

Technical Deep Dive

▶ Watch: How Onion Encryption works in mixnets (4:40)

The core challenge addressed by Onion Franking is the integration of abuse reporting into onion encryption systems without compromising their fundamental metadata hiding properties. Onion encryption, famously used in systems like Tor, operates by encrypting a message in successive layers, much like an onion. A sender routes a message through a chain of servers (or "hops"). Each server in the chain peels off one layer of encryption, revealing the address of the next server, and forwards the message. The first server only knows the sender, the last server only knows the receiver, and intermediate servers know neither. This layered approach is what provides metadata hiding.

A naive attempt to apply standard end-to-end encrypted (E2EE) message franking to this architecture immediately fails. In E2EE franking, the sender computes a commitment (C2) to the message plaintext and sends it to the platform. The platform, acting as a moderator, computes a MAC tag based on this C2 and message context (sender/receiver identities). If we designate the first server in the onion chain as the "moderator" and have it compute a tag on the C2, this would require the first server to know the sender's identity and the C2. The problem arises when this information, or a derivation of it, needs to be passed along the chain for the receiver to eventually verify. If the C2 and its associated context are passed in a way that reveals the sender to subsequent servers, the metadata hiding is "completely broken" because "all parties along the chain are able to see who the message sender was."

Onion Franking's innovative solution lies in its method to mask the franking data while it is in transit through the mix-net. The scheme involves passing "a little bit of extra data" alongside the encrypted message. This additional data is carefully masked and unmasked at each hop in the onion chain. The goal is to ensure that the receiver can still recover the franking data and verify that it has not been tampered with by any intermediate servers, all without revealing the sender's identity to any server beyond the first, and without revealing the franking data itself to intermediate servers.

While the talk refers to the paper for full implementation details, Gregoire provides a crucial insight into how this masking works:

"Essentially what this is is, like in normal message franking, we pass along this extra information that was the C2 before, which is a commitment to the message plain text. Here we do something similar. But we notice that because we have like an onion encryption scheme, we can actually require that each server... each hop along the chain... the next server will apply some new mask, and the mask is calculated in a way that's dependent on randomness chosen by A. And then this randomness is also sent to B. So B can undo all of the masking that was done along the way."

This implies a coordinated masking scheme where the sender (A) generates randomness that influences the masks applied by each server. This randomness, or a key derived from it, is then securely transmitted to the receiver (B), likely through the onion encryption layers themselves, allowing B to reverse the masking process. This ensures that the franking information remains opaque to intermediate servers but fully recoverable and verifiable by the intended recipient.

The performance gains of Onion Franking are substantial. Prior works attempting similar functionality incurred "one to two orders of magnitude of overhead" when compared to standard E2EE franking. Onion Franking, by leveraging the inherent structure of onion encryption and its tailored masking approach, achieves performance that is "on par with end-to-end encrypted message franking" while still providing robust metadata hiding. This efficiency is critical for practical deployment in high-throughput messaging systems.

Beyond basic abuse reporting, Onion Franking introduces stronger accountability notions. Standard accountability ensures that a malicious sender cannot create a message that the receiver accepts but the moderator rejects for reporting. However, Gregoire poses a more advanced threat: "What if the moderator colludes with a certain user to render all of their messages unreportable?" A colluding moderator could, for instance, receive legitimate franking information from a user but then, instead of behaving honestly, forward "garbage through the system," making the message unreportable even if the moderator later acts honestly at moderation time.

To counter this, Onion Franking offers two techniques to enforce honest moderator behavior at message sending time, verifiable by the receiver:

1. Zero-Knowledge Proofs (ZKPs): This technique allows the moderator to prove to the receiver (and implicitly, to the system) that it processed the franking information honestly, without revealing the sensitive details of the franking process itself or the message content. ZKPs are computationally intensive but provide strong cryptographic guarantees. The talk indicates that efficient methods for implementing ZKPs in this context are discussed in the paper.
2. Probabilistic Guarantees with Trap Messages: A more performant scheme involves sending "trap messages" alongside each actual message. These trap messages are specifically designed to be reportable. By reporting these trap messages, the receiver can probabilistically verify that the moderator is processing messages honestly. If the moderator is colluding, it would likely fail to process the trap messages correctly, thus exposing its dishonest behavior. This provides a balance between performance and accountability.

Importantly, these stronger accountability techniques—ZKPs and trap messages—are not exclusive to Onion Franking. They are "applicable to message franking in general," meaning they can enhance the security and trustworthiness of existing E2EE message franking schemes by mitigating the risk of moderator collusion. This broad applicability highlights the significant impact of Gregoire's research beyond just metadata-hiding systems.

Demo / Proof of Concept

▶ Watch: Naive franking breaks metadata hiding in mixnets (5:40)

The provided transcript does not explicitly detail a live demonstration or a concrete proof of concept implementation of Onion Franking. The speaker primarily focuses on the theoretical framework, the technical challenges, and the performance results of their proposed system. For specific implementation details, the audience is encouraged to refer to the full research paper or engage in further discussion with the speaker.

Defensive Implications

▶ Watch: Significant performance improvements of Onion Franking (7:05)

The introduction of Onion Franking carries significant implications for developers, architects, and users of secure messaging platforms, particularly those prioritizing metadata hiding.

1. Enabling Abuse Reporting in Private Systems: For platforms built on mix nets, DC-nets, or onion encryption (like potential future privacy-focused messengers leveraging Tor-like architectures), Onion Franking provides a blueprint for integrating crucial abuse reporting mechanisms without sacrificing the core metadata hiding guarantees. This directly addresses the long-standing tension between user privacy and platform safety, offering a robust solution that can help these platforms combat abuse and comply with legal requirements while maintaining their privacy promises. Developers of such systems should explore adopting the Onion Franking architecture to enhance user safety and platform integrity.

1. Strengthening Accountability of Moderation: The proposed techniques for stronger accountability, specifically the use of zero-knowledge proofs (ZKPs) and trap messages, are vital for any system employing message franking, not just those with metadata hiding. These mechanisms protect against moderator collusion, a critical vulnerability where a malicious moderator could conspire with users to make their abusive messages unreportable. Existing E2EE messaging platforms that use message franking (e.g., Facebook Messenger's secret conversations) should investigate integrating these accountability enhancements. Implementing ZKPs or trap messages can build greater trust in the moderation process, assuring users that reported messages will be handled honestly and that the system itself cannot be subverted for abuse.

1. Architectural Considerations for Privacy-Preserving Features: The work highlights that achieving advanced security properties often requires "breaking previousing abstractions." This serves as a reminder for security architects that a holistic, integrated design approach is often necessary when combining seemingly disparate security goals (like privacy and moderation). Simply layering one security mechanism on top of another may not suffice; deeper integration, as exemplified by the masked franking data within the onion encryption layers, can yield superior results.

1. User Education and Transparency: As systems adopt these advanced techniques, it becomes crucial to educate users about how their privacy is maintained while abuse reporting is enabled. Transparency regarding the moderation process, the role of franking, and the safeguards against moderator collusion can foster greater user trust and understanding. Users should be aware that even in highly private communication channels, mechanisms for reporting abuse can exist without compromising their fundamental privacy.

1. Performance Optimization for Security Features: Onion Franking's achievement of performance "on par with end-to-end encrypted message franking" underscores the importance of efficient cryptographic design. Security features, especially those related to privacy and moderation, must be performant enough to be practical for widespread adoption. Future research and development in this area should continue to prioritize both strong security guarantees and computational efficiency.

Key Takeaways

• Bridging Privacy and Safety: Onion Franking successfully resolves the inherent conflict between strong metadata hiding in mix-net/onion encryption systems and the essential need for abuse reporting and platform moderation.
• Efficient Abuse Reporting for Onion Encryption: The scheme provides an efficient mechanism for abuse reporting in metadata-hiding messaging platforms based on onion encryption, a feature previously difficult to implement without compromising privacy.
• Significant Performance Gains: Onion Franking drastically outperforms prior attempts, achieving performance comparable to standard end-to-end encrypted (E2EE) message franking while maintaining full metadata privacy.
• Innovative Masking Technique: Its core innovation involves carefully masking franking data as it traverses the onion encryption layers, allowing the receiver to verify the data without revealing sensitive information to intermediate servers.
• Enhanced Moderator Accountability: The research introduces novel techniques, including zero-knowledge proofs (ZKPs) and probabilistic trap messages, to enforce honest moderator behavior and prevent collusion, thereby strengthening the integrity of the reporting process.
• Broad Applicability of Accountability Enhancements: The methods for achieving stronger accountability are not limited to Onion Franking but can be applied to message franking schemes in general, offering a significant security upgrade for a wider range of E2EE messaging systems.

About the Speaker(s)

Matthew Gregoire is the presenter of this talk, "Onion Franking: Abuse Reports for Mix-Based Private Messaging," at the NDSS Symposium. The transcript and metadata provided do not include additional details about his specific title or affiliation.