PriSrv: Privacy-Enhanced and Highly Usable Service Discovery in Wireless Communications

PriSrv: Privacy-Enhanced and Highly Usable Service Discovery in Wireless Communications

Speakers: Yang Yang

Conference: NDSS Symposium

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

Overview

Service discovery protocols are the invisible backbone of modern wireless communications, enabling devices to locate and interact with services seamlessly. From connecting to Wi-Fi networks and sharing files via AirDrop to managing smart devices over Bluetooth Low Energy (BLE), these protocols are fundamental. However, a pervasive and critical flaw in existing service discovery mechanisms is their severe lack of privacy protection for both service providers and clients. These protocols frequently expose sensitive information, including service types, device identities, and even user mobility patterns, creating fertile ground for a range of network-based attacks such as spoofing, man-in-the-middle (MiTM) attacks, persistent tracking, and user identification.

This talk by Yang Yang at the NDSS Symposium introduces PriSrv, a novel service discovery protocol meticulously engineered to be both privacy-enhanced and highly usable. PriSrv directly confronts the vulnerabilities present in current systems by ensuring that wireless access points, service providers, and clients can discover each other and establish secure communication channels only when predefined connection requirements are mutually satisfied. This addresses a pressing need, as studies reveal that a significant majority of users perceive the exposure of device names in wireless services as a substantial privacy risk, highlighting the urgency for more secure and privacy-centric solutions.

The development of PriSrv is particularly significant given the increasing prevalence of wireless devices and the growing sophistication of privacy-invasive attacks. By enabling fine-grained, bilateral policy control and anonymous mutual authentication, PriSrv aims to set a new standard for secure service discovery. Its innovative dual-layer architecture and underlying cryptographic primitives offer a robust defense against tracking and impersonation, making it a pivotal contribution to safeguarding user privacy in an interconnected world.

Background

▶ Watch: Introduction: The critical privacy problem in service discovery (0:00)

The landscape of wireless service discovery is populated by numerous protocols, many of which were designed without comprehensive privacy considerations, leading to significant vulnerabilities. Traditional protocols like DNS-SD, mDNS, SSDP, UPnP, and CBN offer minimal to no privacy protection. DNS-SD, for instance, relies on a centralized DNS server, while CBN requires pre-registration, creating directories that can be easily exploited. These protocols are notoriously susceptible to attacks such as man-in-the-middle, spoofing, and denial-of-service (DoS). Bai et al. (12) demonstrated how mDNS can be spoofed, and UPnP is widely recognized for its DoS vulnerabilities (22). Such weaknesses allow attackers to easily intercept communications, impersonate legitimate services, or flood networks, disrupting functionality and compromising user data.

Even protocols that incorporate some form of authentication, such as Wi-Fi (1) and Bluetooth Low Energy (BLE) (3), fall short on critical privacy requirements. They typically lack private broadcast, bilateral anonymity, flexible policy control, selective attribute disclosure, and multi-show unlinkability. A recurring issue is the public advertisement of private information, such as device names or unique identifiers, which facilitates user identification and tracking. Research indicates that 59% of investigated devices regularly broadcast their owners' real names in Wi-Fi networks (4), presenting a clear privacy hazard. Similarly, BLE devices often advertise unique identifiers in cleartext, making them vulnerable to spoofing attacks (10, 24).

More advanced protocols like Apple AirDrop (2), PrivateDrop (16), and WTSB (5) have attempted to enhance privacy through encryption and authentication. AirDrop uses TLS connections with client and server certificates, and PrivateDrop improves upon this with private mutual authentication via an optimized private set intersection protocol (16). WTSB (5) employs prefix encryption and digital signatures for private broadcast, mutual authentication, and bilateral anonymity. However, these solutions still exhibit significant privacy gaps. AirDrop and PrivateDrop, for example, remain vulnerable to user tracking through UUIDs embedded in TLS certificates (16). WTSB (5) lacks bilateral flexible policy control, meaning service providers can define client types, but clients cannot specify policies for selecting providers. It also suffers from a lack of multi-show unlinkability, making it susceptible to user tracking across sessions.

The comprehensive comparison presented in the paper's Table I unequivocally shows that PriSrv stands out as the only protocol that successfully addresses all six privacy enhancement requirements: Private Service Broadcast, Mutual Authentication, Bilateral Anonymity, Bilateral Flexible Policy Control, Selective Attribute Disclosure, and Multi-Show Unlinkability. Furthermore, PriSrv meets high usability criteria by supporting No Pre-registered Pairing and No Third-party Dependency. While it does require a one-time In-advance Identity Issuance, this setup does not impede the real-time discovery process. It is important to acknowledge that achieving this superior level of privacy necessitates a trade-off: PriSrv utilizes computationally intensive operations like exponentiation and bilinear pairing within its core cryptographic primitive, ACME, which can result in higher computational overhead compared to schemes like WTSB that employ more efficient prefix encryption. This computational cost, however, is a necessary investment for the significantly enhanced privacy guarantees PriSrv delivers.

Key Findings

▶ Watch: PriSrv's essential privacy enhancements and usability requirements (2:40)

The work presented in PriSrv introduces several pivotal advancements that collectively redefine privacy-enhanced service discovery in wireless communications.

1. First Comprehensive Privacy Protocol: PriSrv is the first protocol to simultaneously satisfy a full suite of six critical privacy enhancement requirements—Private Service Broadcast, Mutual Authentication, Bilateral Anonymity, Bilateral Flexible Policy Control, Selective Attribute Disclosure, and Multi-Show Unlinkability—alongside high usability criteria (No Pre-registered Pairing, No Third-party Dependency). This comprehensive approach addresses the fragmented privacy protections of prior work.

1. Anonymous Credential-based Matchmaking Encryption (ACME): A novel cryptographic primitive, ACME, is introduced as the cornerstone of PriSrv. ACME is specifically designed to support bilateral fine-grained policies and selective attribute disclosure for private mutual authentication. It represents a significant leap beyond existing matchmaking encryption (ME) schemes, offering superior functionality and efficiency by eliminating the need for heavy cryptographic tools, enabling selective attribute disclosure, and supporting more expressive policy types. ACME itself is a standalone contribution of independent interest to cryptography.

1. Fast Anonymous Credential (FAC) Scheme: As a fundamental building block for ACME, the Fast Anonymous Credential (FAC) scheme was developed. FAC enables anonymous authentication with selective attribute disclosure and multi-show unlinkability, while critically featuring constant and small credential sizes (e.g., 0.544 KB for BN256 curve) and highly efficient show and verification mechanisms. This addresses the practical limitations of prior anonymous credential schemes in resource-constrained and latency-sensitive wireless environments.

1. Demonstrated Interoperability: PriSrv's practical applicability is showcased through concrete integration methods with mainstream service discovery protocols such as EAP (Extensible Authentication Protocol), mDNS, BLE, and Apple AirDrop. This demonstrates its potential to enhance privacy in real-world deployments without necessitating a complete overhaul of existing infrastructure.

1. Formal Security Guarantees: The security and privacy properties of PriSrv, ACME, and FAC are rigorously proven through formal security models. These proofs, conducted under the Decisional Diffie-Hellman (DDH) assumption and assuming an unforgeable MAC and random oracle hash function, capture various attack vectors, including intercepting, tampering, replaying, injecting data packets, and interleaving messages across different sessions.

1. Extensive Performance Validation: Comprehensive evaluation and benchmarking across diverse hardware platforms—ranging from high-end desktops and laptops to mobile phones and resource-constrained Raspberry Pi 4B devices—demonstrate PriSrv's efficiency and practicality. The total time for private service broadcast and anonymous mutual authentication consistently falls within human perception thresholds for immediate response (e.g., less than 0.973 seconds on mobile, under 2.712 seconds on Raspberry Pi), confirming its viability for real-world wireless communication scenarios.

Technical Deep Dive

▶ Watch: Analyzing privacy limitations of existing service discovery protocols (3:10)

PriSrv's sophisticated design is built upon a novel dual-layer architecture and relies on two innovative cryptographic primitives: ACME and FAC. This architecture is meticulously crafted to achieve both robust privacy and high usability.

The outer layer of PriSrv handles public attributes and public authentication policies. Each party, whether a service provider or a client, is associated with a set of public attributes and a public authentication policy. For instance, a service provider broadcasts a ciphertext encrypted by its policy and public attributes. A client first performs a fast, bilateral policy matching by checking if its public attributes satisfy the service provider's public policy, and vice versa. This initial check occurs without decryption, allowing for efficient filtering of unauthorized parties. Only if this bilateral policy match is successful can the client proceed to decrypt the ciphertext.

The inner layer then manages private attributes, such as a device ID, which are only revealed to authorized peers. Upon successful decryption in the outer layer, the client recovers the service provider's private attributes, enabling mutual authentication. Following this, a secure session key is established, ensuring all subsequent communication is confidential. This dual-layer approach is crucial for PriSrv to deliver privacy-enhanced service discovery with high usability, minimizing information leakage while maintaining efficient discovery.

To achieve its privacy goals, PriSrv adheres to several stringent requirements:

• Private Service Broadcast: Services are advertised in a way that prevents unauthorized parties from learning their existence or characteristics.
• Mutual Authentication: Both the service provider and the client cryptographically verify each other's identities.
• Bilateral Anonymity: Both parties remain anonymous to each other until mutual authentication and policy satisfaction.
• Bilateral Flexible Policy Control: Both the service provider and the client can define fine-grained policies that the other party must satisfy before revealing private information or establishing a connection.
• Selective Attribute Disclosure: Parties can choose which specific attributes to reveal to their peers, rather than exposing all information.
• Multi-Show Unlinkability: It should be impossible to link multiple interactions or discovery attempts by the same device, preventing long-term tracking.

For usability, PriSrv supports No Pre-registered Pairing, eliminating the need for prior setup between devices, and No Third-party Dependency, meaning it doesn't rely on external servers or entities for the discovery process. While In-advance Identity Issuance is required, this is a one-time setup that does not impact the real-time usability of the discovery process.

The core technical approach is centered around Anonymous Credential-based Matchmaking Encryption (ACME). ACME is a novel cryptographic primitive designed to support bilateral fine-grained policies and selective attribute disclosure for private mutual authentication. It significantly advances beyond prior matchmaking encryption schemes by offering superior functionality and efficiency. The design intuition for ACME's dual-layer matching mechanism is to first filter unauthorized parties based on public attributes and then perform mutual authentication using selectively disclosed private attributes.

A fundamental building block for ACME is the Fast Anonymous Credential (FAC) scheme. Existing anonymous credential schemes often suffer from large credential sizes or cumbersome show and verification mechanisms, making them impractical for resource-constrained wireless networks. FAC addresses these limitations by providing constant-size credentials and highly efficient show and verification mechanisms, while still supporting anonymous authentication with selective attribute disclosure and multi-show unlinkability.

To achieve bilateral policy control within ACME, PriSrv leverages techniques from Attribute-Based Encryption (ABE) that support expressive access policies, specifically monotone Boolean formulae, which are equivalent to NC¹ circuits. It integrates an improved Ciphertext-Policy Attribute-Based Encryption (CP-ABE) scheme with Katsumata's Key-Policy Attribute-Based Encryption (KP-ABE) (27) to enable fast decryption with a constant number of pairing operations, facilitating fine-grained bilateral policy control.

ACME's design also incorporates robust impersonation resistance. Both public and private attributes are used as inputs for authentication token generation in the inner layer. This prevents malicious service providers from forging valid authentication tokens, even if they broadcast deceptive messages with public attributes. Similarly, an attacker impersonating a legitimate receiver cannot decrypt the ciphertext without a valid secret key.

The formal security of PriSrv, ACME, and FAC is rigorously proven. Formal security models for private service discovery, bilateral anonymity, and the underlying cryptographic primitives are defined. These proofs demonstrate that PriSrv achieves privacy, authenticity, anonymity, and unlinkability under the Decisional Diffie-Hellman (DDH) assumption, assuming ACME is secure, the Message Authentication Code (MAC) is unforgeable, and the hash function behaves as a random oracle. This comprehensive modeling captures various attack vectors, including intercepting, tampering, replaying, injecting data packets, and interleaving messages across different sessions in realistic settings.

The system design and architecture of PriSrv operate in two main phases:

1. Private Service Broadcast Phase:

• The service provider ('S') initiates a broadcast session with a unique identifier, bid.
• 'S' defines its access policy, fs, specifying client criteria.
• 'S' selects an ephemeral Diffie-Hellman exponent z, computes Z = h^z, and generates a MAC key Kc for the client.
• 'S' constructs the broadcast message MSGB (including bid, Z, service type, parameters, and Kc).
• MSGB is encrypted using ACME: CTB = ACME.Enc(creds, xs, fs, MSGB).
• 'S' announces bid and CTB over the public network.

1. Anonymous Mutual Authentication Phase:

• The client ('C') receives bid and CTB.
• 'C' first checks if its public attributes satisfy fs. If not, 'C' aborts.
• 'C' attempts to decrypt CTB using its attribute and policy decryption keys (DKx, DKfc). If decryption fails, 'C' aborts; otherwise, 'C' recovers MSGB.
• 'C' selects its own ephemeral Diffie-Hellman exponents, x1 and x2, computing X1 = g^x1 and X2 = h^x2.
• 'C' extracts Kc from MSGB, computes an authentication tag σc for a message Mc (including C - S, bid, sid, X1, X2, Z).
• 'C' defines its own connection policy fc for 'S' and selects public/private attributes to disclose.
• 'C' encrypts its message MSGc (containing its Ks and Mc) using ACME: CTC = ACME.Enc(credc, xc, fc, MSGc).
• 'C' sends bid, sid, σc, and CTC to 'S'.
• 'S' receives 'C''s message, recovers MSGc using ACME.Dec(DKx, DKfs, CTC). If decryption fails, 'S' aborts.
• 'S' verifies σc. If valid, 'S' selects its own DH exponent y, computes Y = g^y.
• 'S' sets Ms (including S - C, bid, sid, X1, X2, Y, Z) and generates σs using Ks from MSGc.
• 'S' computes a secret session key SSKc,s = H(X1^y, X2^z) and sends (Ms, σs) to 'C'.
• 'C' receives (Ms, σs), checks σs. If valid, 'C' computes its session key SSKc,s = H(Y^x1, Z^x2). Due to Diffie-Hellman properties, X1^y = Y^x1 and X2^z = Z^x2, ensuring both parties derive the same secret session key, thus establishing a secure communication channel.

PriSrv also includes robust credential management. It leverages FAC for credential issuance, providing unforgeability, anonymity, unlinkability, and selective attribute disclosure. This system can seamlessly integrate with existing Decentralized Identifier (DID) frameworks like W3C's DIDs and Verifiable Credentials. For credential revocation, PriSrv can incorporate techniques such as dynamic accumulators or n-times unlinkable proofs.

Demo / Proof of Concept

▶ Watch: PriSrv is the only protocol meeting all privacy requirements (5:10)

To validate the practical feasibility and performance of PriSrv, a concrete protocol implementation was developed based on the ACME scheme. This implementation integrates FAC, a symmetric encryption scheme (AES-CTR), and a hash function (SHA-256). The ACME construction specifically leverages improved CP-ABE and KP-ABE schemes to achieve efficient bilateral policy control and fast decryption. The implementation, written in C/C++, utilizes the MIRACL library (55) for elliptic curve operations, supporting MNT159 (80-bit security), MNT201 (90-bit security), and BN256 (100-bit security) curves. The source code for this implementation is publicly available on GitHub.

The talk demonstrated PriSrv's interoperability with several existing wireless protocols:

• mDNS and BLE: PriSrv can be integrated at the application layer. The broadcast ciphertext (CTB) for BN256 security is approximately 531,996 bytes. For mDNS, which limits a single TXT record to 65,535 bytes, PriSrv would require about 9 TXT records to transmit the broadcast ciphertext. For BLE, with its stringent payload constraint of 31 bytes, the Attribute Protocol (ATT) and Attribute Protocol Data Unit (PDU) Segmentation techniques would be leveraged to break down and reassemble the ciphertext.

• EAP (Extensible Authentication Protocol): PriSrv was integrated into the Wi-Fi WPA-Enterprise framework, extending RFC 3748. In this setup, an access point (AP) acts as a pass-through agent. The service provider announces the bid and CTB via the AP. The client, after decrypting MSGB, sends its bid, sid, σc, and CTC as a reply. The service provider then sends Ms and σs, establishing a secure session key. All subsequent protocol messages are encapsulated within EAPOL frames and re-encapsulated as RADIUS packets on the back-haul.

• Apple AirDrop: PriSrv offers a significant privacy enhancement for AirDrop by avoiding the transmission of private identifiers during the advertising phase. Instead, certificates from both parties would be encrypted using ACME at the beginning of the TLS handshake. Apple could potentially act as the credential issuer to generate the necessary secret keys and credentials.

The implementation and evaluation were conducted on a diverse range of hardware platforms to assess performance across varying computational capabilities: a desktop, a laptop, a mobile phone, and a Raspberry Pi 4B (representing resource-constrained IoT devices). Each test case was run 20 times, and the average results were reported.

The performance evaluation yielded compelling results:

• Fast Anonymous Credential (FAC) Scheme: Compared to typical anonymous credential schemes, FAC consistently offers a constant and significantly smaller credential size. For the BN256 curve, FAC credentials are only 0.544 KB. The computational costs for cryptographic operations are also highly efficient: Issue takes 39.387 ms, Show takes 28.302 ms, and Verify takes 65.819 ms on BN256, making it one of the fastest schemes supporting multi-show unlinkability.

• ACME Scheme: With parameters n=10, k=2, m=9, and S=9, the system setup time ranges from 20.526 ms to 33.344 ms across different curves. Credential and user key generation are fast, taking less than 118.622 ms and 9.102 ms, respectively. The Issue algorithm is efficient at 39.383 ms. Crucially, the encryption and decryption costs are low, less than 188 ms and 232 ms, respectively, on the BN256 curve.

• Overall PriSrv Protocol Performance:
• Private Service Broadcast Phase: On a desktop, this phase takes 202.822 ms. On a laptop, 287.287 ms. On a mobile phone, 482.725 ms. On a Raspberry Pi 4B, it takes 1188.392 ms (approximately 1.189 seconds). The communication overhead for this phase is about 537.98 KB on the BN256 curve.
• Anonymous Mutual Authentication Phase: On a desktop, this phase takes 673.039 ms. On a laptop, 854.177 ms. On a mobile phone, 972.163 ms. On a Raspberry Pi 4B, it takes 2711.013 ms (approximately 2.712 seconds). The communication overhead is similar, around 538.83 KB.

In summary, PriSrv achieves private discovery and secure connection in less than 0.973 seconds on desktop, laptop, and mobile phone platforms, which is well within the human perception threshold for an immediate response (16, 17). Even on the resource-constrained Raspberry Pi 4B, the total time is less than 2.712 seconds. These results conclusively demonstrate the efficiency and practicality of PriSrv in real-world wireless communication scenarios. Further validation included implementing PriSrv in a wireless environment using two laptops running Ubuntu 20.04 within the Wi-Fi WPA-Enterprise framework, confirming its real-world applicability.

Defensive Implications

▶ Watch: ACME: PriSrv's core cryptographic primitive for matchmaking encryption (6:00)

The introduction of PriSrv offers significant insights and actionable strategies for defenders aiming to bolster privacy and security in wireless communications.

Firstly, the core message for defenders is to prioritize and adopt service discovery protocols that natively incorporate comprehensive privacy protections. The widespread vulnerabilities in existing protocols, from public advertisements of device names to cleartext identifiers, highlight a critical design flaw that needs to be addressed at the architectural level. PriSrv demonstrates that it is possible to achieve robust privacy, including bilateral anonymity, flexible policy control, and multi-show unlinkability, without sacrificing usability.

Secondly, developers and security architects should design protocols with bilateral fine-grained policy control and selective attribute disclosure as fundamental requirements. Instead of monolithic access controls, systems should allow both service providers and clients to define explicit criteria for interaction and to reveal only the minimum necessary information. This shifts the paradigm from broad disclosure to controlled, consent-based information exchange, mitigating risks of over-exposure and tracking.

Thirdly, robust credential management, including anonymous credentials and effective revocation mechanisms, is paramount. PriSrv's FAC scheme, with its constant-size credentials and efficient operations, provides a blueprint for how anonymous authentication can be implemented practically. Defenders should explore integrating such credential systems, potentially leveraging existing frameworks like W3C DIDs and Verifiable Credentials, to enable secure and privacy-preserving identity verification.

Fourthly, while PriSrv effectively protects its own payload, defenders must remain cognizant of lower-layer tracking mechanisms. Even with advanced application-layer privacy, MAC addresses and other network-layer identifiers can still facilitate tracking. While MAC randomization exists in operating systems like Android and iOS, its effectiveness is often limited (e.g., randomization only on new network connections, not per-session). Future defensive strategies must involve exploring and implementing more robust, multi-layer anti-tracking mechanisms to ensure comprehensive unlinkability across the entire communication stack.

Finally, for environments where immediate adoption of a new protocol like PriSrv is not feasible, defenders should consider deploying overlay solutions or extensions that integrate privacy-enhancing features. PriSrv's demonstrated interoperability with EAP for Wi-Fi WPA-Enterprise, mDNS, BLE, and AirDrop illustrates how existing infrastructure can be augmented. This involves encapsulating privacy-sensitive discovery information within the new cryptographic primitives, even if the underlying transport remains the same. Network administrators should lobby vendors (like Apple, as suggested for AirDrop) to integrate such privacy-enhancing solutions directly into their platforms. The large message size of PriSrv's broadcast ciphertext (e.g., ~532KB for BN256) is a practical consideration, particularly for bandwidth-constrained or lossy networks like BLE or mDNS over UDP. Defenders must weigh the privacy benefits against potential performance impacts and explore strategies to optimize message sizes or manage fragmentation effectively in their deployments.

Key Takeaways

• Critical Privacy Gaps: Existing wireless service discovery protocols (e.g., Wi-Fi, BLE, mDNS, AirDrop) suffer from severe privacy deficiencies, leaking sensitive information and enabling tracking, spoofing, and DoS attacks.
• PriSrv's Comprehensive Solution: PriSrv is the first protocol to simultaneously meet a full set of privacy enhancement requirements (Private Service Broadcast, Mutual Authentication, Bilateral Anonymity, Bilateral Flexible Policy Control, Selective Attribute Disclosure, Multi-Show Unlinkability) alongside high usability.
• Innovative Cryptographic Primitives: PriSrv is built upon novel cryptographic primitives: ACME (Anonymous Credential-based Matchmaking Encryption) for bilateral policy control and selective attribute disclosure, and FAC (Fast Anonymous Credential) for efficient, unlinkable anonymous authentication.
• Practicality and Efficiency: Despite its advanced cryptographic features, PriSrv is efficient and practical across diverse hardware, from desktops to Raspberry Pi, completing discovery and secure connections within human-perceptible delays (under 2.712 seconds even on IoT devices).
• Seamless Interoperability: PriSrv demonstrates concrete integration methods with mainstream protocols like EAP (Wi-Fi WPA-Enterprise), mDNS, BLE, and AirDrop, showcasing its real-world applicability without requiring entirely new infrastructure.
• Ongoing Challenges: While a significant advancement, PriSrv faces challenges regarding the large message size of its broadcast ciphertext, especially for resource-constrained networks, and the need for more robust lower-layer (e.g., MAC address) unlinkability mechanisms.

About the Speaker(s)

The talk "PriSrv: Privacy-Enhanced and Highly Usable Service Discovery in Wireless Communications" was presented by Yang Yang at the NDSS Symposium. Based on the provided metadata and transcript, no additional biographical details such as title or company affiliation are available for Yang Yang.