Scrappy: SeCure Rate Assuring Protocol with PrivacY

Scrappy: SeCure Rate Assuring Protocol with PrivacY

Speakers: Kosei Akama

Conference: NDSS Symposium

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

Overview

The internet’s reliance on online services has brought with it an escalating challenge: how to mitigate abusive activities without compromising user privacy or degrading the user experience. Adversaries routinely exploit online platforms by accessing resources at rates far exceeding intended limits, leading to issues such as manipulation of online polls and product ratings, exorbitant billing from overuse of third-party APIs, exploitation of free trials, relentless dictionary attacks on login systems, and excessive data collection by web crawlers. Traditional defenses like SMS authentication and CAPTCHAs, while widely deployed, suffer from significant drawbacks, including privacy concerns, ease of circumvention by attackers, and diminishing effectiveness against sophisticated machine learning models and CAPTCHA farms.

In response to these pervasive problems, Kosei Akama introduced Scrappy, a novel system designed to provide a robust, privacy-preserving solution for rate assurance. Scrappy stands for "SeCure Rate Assuring Protocol with PrivacY" and represents a significant advancement in the field of online security. It enables clients to generate unforgeable yet unlinkable rate-assuring proofs, offering cryptographic guarantees to servers that a client is adhering to rate limits without revealing their identity or linking their actions across different services or time periods.

A key innovation of Scrappy is its unique approach to hardware security. Unlike prior research that often assumes absolute trust in the underlying hardware, Scrappy's core rate-limiting functionality does not rely on the security of the hardware security device itself. This means that even if an attacker manages to compromise the device and extract its essential secret keys, the system can still effectively block malicious users. This resilience, combined with its hardware agnosticism and demonstrated practicality across various platforms, positions Scrappy as a critical tool for enhancing online service security while upholding user privacy.

Background

▶ Watch: Introducing Scrappy and the problem of abusive rates (0:00)

The landscape of online security has long grappled with the tension between preventing abuse and preserving user privacy. Current ubiquitous solutions, while offering some protection, are increasingly insufficient. SMS authentication is often employed for rate limiting, but it inherently ties user actions to a phone number, creating significant privacy concerns. Furthermore, attackers can easily circumvent this by acquiring multiple burner phone numbers. CAPTCHAs, designed to differentiate humans from automated bots, are facing an uphill battle against advancements in machine learning and the proliferation of human-powered CAPTCHA farms, rendering them less effective and notoriously detrimental to user experience.

Prior research has attempted to develop more sophisticated rate-limiting systems, often leveraging hardware-assisted or cryptographic techniques. CAP, for instance, utilizes FIDO authenticators where a private key, protected by a secure element, signs challenges. While this provides unforgeable signatures, its security is entirely dependent on the secure element, and compromised keys cannot be revoked. CACTI employs client-side Trusted Execution Environments (TEEs) to generate rate-proofs, using group signature schemes to protect user privacy. However, CACTI’s rate-limiting, much like CAP, relies on the TEE’s security, making it vulnerable if secret keys are extracted. The fundamental limitation of both CAP and CACTI is their complete reliance on the client-owned device's security for the integrity of their rate-limiting functionality.

On the cryptographic front, Privacy Pass uses blind signature schemes to allow users to obtain and spend anonymous cryptographic tokens, thereby protecting privacy. Yet, it remains susceptible to timing correlation attacks, which can potentially undermine unlinkability. Opaak introduces a primitive called periodic k-times anonymous authentication (k-TAA) for mobile phone users, aiming to limit the number of private keys a user can acquire. However, Opaak operates under unrealistic assumptions about users' inability to possess multiple phone numbers, encrypts private keys with user-defined passwords (creating a high user burden and exposing keys to untrusted memory), and is vulnerable to side-channel attacks.

Scrappy builds upon the principles of Direct Anonymous Attestation (DAA), a specialized group signature scheme with distinct properties critical for privacy-preserving authentication:

1. Anonymity: Neither a group member nor the Group Manager can link a signer to a specific signature.
2. Unlinkability: It is computationally difficult to determine if two signatures, generated for different verifiers, originated from the same signer.
3. Pseudonymity: Signers can choose whether multiple signatures directed to the same verifier can be linked.

The DAA protocol involves several phases: Setup (GM generates group keys), Join (signer obtains a credential from GM using their public key and an Endorsement Key Certificate), Sign (signer computes a signature using their secret key and credential), Verify (verifier checks signature validity), and Revoke (signer's key added to a revocation list). While DAA provides strong privacy and authentication, it does not inherently offer rate-limiting capabilities. Periodic k-TAA, by contrast, does offer rate-limiting by ensuring a signer cannot create more than one valid signature within a specific time period, leveraging a deterministic part of the signature (σ_α) for detection. However, k-TAA requires specific cryptographic calculations (e.g., special RSA modulus, Zero Knowledge Proofs) that are not typically supported by widely available hardware security devices like Trusted Platform Modules (TPMs). This gap—the need for robust, privacy-preserving rate-limiting that is practical on existing hardware and resilient to hardware compromise—is precisely what Scrappy aims to fill.

Key Findings

▶ Watch: Scrappy's key differentiator: hardware-agnostic rate-limiting (1:15)

Scrappy introduces several pivotal contributions and key findings that significantly advance the state of privacy-preserving rate-limiting:

The primary contribution is the conceptualization and implementation of rate-assuring proofs. This novel security primitive provides a cryptographic mechanism for servers to obtain verifiable assurance that a client is not exceeding predefined access rates, all while meticulously preserving the client's privacy. These proofs are both unforgeable (cannot be created by an unauthorized entity) and unlinkable (cannot be tied back to a specific user across different services or time windows).

Scrappy, as a protocol, is built upon the robust foundation of Direct Anonymous Attestation (DAA), a standard for TPMs and adopted by technologies like FIDO and Intel SGX (EPID). It leverages generic hardware security devices, demonstrating its versatility beyond specific, high-end hardware. The talk highlights three distinct proof-of-concept (PoC) implementations: one utilizing a Trusted Platform Module (TPM), another on a Secure Hardware Token (specifically a Solokey Hacker), and a third on a smartphone (Android Pixel 6a). The TPM implementation is particularly noteworthy as it is open-sourced and immediately deployable in real-world scenarios without requiring hardware modifications.

A critical and differentiating finding of Scrappy is its resilience to hardware compromise. Unlike many prior solutions that collapse if the underlying hardware security device is breached, Scrappy’s rate-limiting capability remains fully intact even if the device's secret keys are leaked. This means that even if an adversary extracts the private key from a user's device, they cannot bypass the rate limits. The system is designed such that the verifier will still only accept one proof per time window from that compromised key, effectively blocking repeated abusive access, regardless of who possesses the key.

Furthermore, comprehensive performance evaluations underscore Scrappy's practicality. It introduces minimal latency, bandwidth, and storage overheads, making it suitable for real-world deployment. For instance, proof generation latency with a TPM is approximately 243.16 ms, and verification latency is around 84.1 ms, competitive with or superior to existing state-of-the-art systems. Storage requirements are also modest, with 1,000 signer-side log entries requiring only 94.2 KB and 100,000 verifier-side entries needing 6.64 MB. These figures demonstrate that Scrappy can be integrated into existing online services without significantly degrading user experience or imposing prohibitive infrastructure costs.

Technical Deep Dive

▶ Watch: Six key contributions of the Scrappy project (1:40)

At its core, Scrappy introduces the concept of rate-assuring proofs, which are cryptographic assertions generated by a client's hardware security device. When a user wishes to access an online service, the server defines a specific time window (t) and a basename (bsn), representing the verifier's domain. The client's hardware then generates a cryptographic signature over these two pieces of data. This proof cryptographically assures the server that the signer has requested access for that particular bsn within that t. The verifier maintains a log of these proofs and, if it receives a similar proof too frequently within the same t, it identifies the signer as misbehaving and rejects the request.

A paramount design goal for Scrappy is user privacy. Rate-assuring proofs generated by a signer for different verifiers must be indistinguishable, preventing any entity from linking them back to the same signer. Similarly, proofs generated for the same verifier but within different time windows must also be unlinkable.

Scrappy addresses several significant design challenges:

1. Limitations in existing cryptographic primitives: While periodic k-TAA offers rate-limiting, its reliance on specific RSA moduli and complex Zero Knowledge Proof calculations makes it incompatible with widely available hardware security devices like TPMs. Scrappy instead leverages Direct Anonymous Attestation (DAA), which is natively supported by TPMs and other secure hardware.
2. Overcoming DAA's lack of direct rate-limiting: DAA inherently provides anonymity and unlinkability but not rate-limiting. Scrappy ingeniously modifies the input to the DAA_Sign function by cryptographically binding the time window t to the pseudonym used to generate the signature. This allows verifiers to link multiple signatures generated by the same signer within the same time window t. However, when t changes, the signature also changes, effectively making it unlinkable to previous signatures and preserving privacy across different time periods.
3. Obtaining t without compromising security and privacy: The hardware security device needs to obtain the current time window t. Relying on an internal clock is problematic due to potential skew and synchronization issues, which could lead to privacy leakage. Obtaining t from an external source (like the signer or verifier) requires careful validation. In Scrappy, the signer obtains t directly from the verifier. To prevent malicious verifiers from tracking signers or malicious signers from cheating, both the signer and verifier must validate t.
4. Managing logs without losing functionality: Verifiers must maintain a log of past interactions. To minimize storage overhead, Scrappy is designed to allow both verifiers and signers to delete old log entries that are no longer useful (i.e., entries created before the current t expires).

System Design and Architecture

Scrappy involves four primary entities: the Group Manager (GM), the Signer, the Verifier, and a Hardware Security Device.

The system operates under a specific threat model:

• Each signer is assumed to own exactly one hardware security device (though acquiring multiple devices would incur higher costs).
• The hardware security device provides a unique attestation key, such as an Endorsement Key (EK), and the GM provisions only one private key to the device.
• All cryptographic primitives are assumed to be correctly implemented, and the random oracle assumption holds.
• Crucially, **all entities except the hardware security device are considered untrusted and potentially malicious**. This includes malicious signers aiming to generate excessive signatures, malicious verifiers attempting to violate signer privacy, and malicious GMs colluding with either.

The hardware security device is central to Scrappy, acting as a source of uniqueness. It is assumed to possess four key properties:

1. Tamper-resistant memory for storing secret data.
2. Capability for remote attestation.
3. Implementation of basic cryptographic primitives (key generation, encryption/decryption, digital signatures).
4. Support for a group signature scheme that provides privacy and pseudonymity.

A defining characteristic of Scrappy's design is that its **rate-limiting functionality *does not rely on the security of the hardware security device itself***. Even if an adversary extracts secret data from the device, Scrappy's rate-limiting capabilities remain intact because the verifier's log tracks the deterministic part of the signature, effectively limiting the compromised key to one use per time window, regardless of who possesses it.

This threat model dictates specific security requirements:

• Rate-limiting: Signers cannot exceed the verifier's request threshold.
• Unforgeability: Signers cannot forge or modify signatures.
• Unlinkability: It must be hard to link signatures generated for different verifiers or at different times to the same signer.

Non-security goals include minimal latency, bandwidth, and storage.

Scrappy Protocol Phases

The Scrappy protocol unfolds in four phases:

1. Initialization Phase:

• The GM generates a group public key (gpk) and a group secret key (gsk).
• The Verifier initializes its log, Log_v, as empty.
• The Signer generates its unique key pair (upk, usk), obtains a credential (cred) from the GM (via the DAA Join process), and initializes its log, Logs_s, as empty.

1. Proof Generation Phase (Signer Side):

• The Signer requests access to a resource. The Verifier responds by requesting a rate-assuring proof over a specific time window t.
• The Signer first checks if t is valid (e.g., covers the current time, from a trusted verifier). If invalid, it aborts.
• It obtains the bsn (basename) from the verifier's certificate and checks its validity. If invalid, it aborts.
• The Signer consults its Logs_s to see if the pair (t, bsn) already exists. If so, a proof for this period and verifier has already been generated, preventing self-denial; it aborts signing.
• It computes a hash h = bsn || t (concatenation).
• The Signer forwards msg (an empty string in the PoC but extensible) and h to its hardware security device to generate the signature σ = (σ_τ, σ_α) using DAA_Sign(msg, h, usk, cred). σ_α is the deterministic part of the signature crucial for rate-limiting.
• The Signer adds the new pair (t, bsn) to its Logs_s.
• Finally, the Signer sends σ and msg to the Verifier.

1. Proof Verification Phase (Verifier Side):

• Upon receiving σ and msg, the Verifier first checks if t is valid. If not, it rejects the proof.
• The Verifier checks its Log_v to see if the pair (t, σ_α) already exists. If it does, the signer has reached the rate limit for this time window, and the request is rejected. This σ_α is the deterministic component that allows linking proofs from the same device within the same t.
• It computes h = bsn || t.
• The Verifier verifies σ using DAA_Verify(σ, msg, h, RL, gpk). If verification fails, the request is rejected.
• The Verifier adds the pair (t, σ_α) to its Log_v.
• If all checks pass, the Verifier returns success and allows access.

1. Cleanup Phase:

• To reduce storage overhead, both the Signer and Verifier periodically clean up their logs. Signers delete (t, bsn) pairs older than the newest t. Verifiers delete entries from Log_v as soon as t expires.

This protocol ensures proofs are unforgeable, rate-limited, and unlinkable across different time windows or verifiers, while maintaining pseudonymity within a single time window for a given verifier.

Demo / Proof of Concept

▶ Watch: Key insight: using deterministic signature component for rate-limiting (4:25)

The Scrappy team developed comprehensive proof-of-concept implementations to validate the protocol's practicality and versatility. The baseline implementation comprises a browser extension, a signer application, a Trusted Platform Module (TPM), and a verifier server. For cryptographic operations, SHA256 is used for hashing and the BN256 pairing curve for DAA, chosen due to its support on the target TPM, although BN638 is generally recommended for higher security. The verifier is configured to allow one access per minute, with t represented as Unix timestamps rounded to the nearest minute. The TPM implementation has been open-sourced on GitHub.

The browser extension, built for Chrome (version 100.0.4896.60), includes a content script and a background script. The content script extracts t and bsn from a special HTML tag (<input period=t value= />) embedded in the verifier's HTML, then sends the generated proof back. The background script acts as a bridge, forwarding data between the content script and the signer application using the Chrome Native Messaging Protocol.

The signer application is implemented in Golang, chosen for its performance and memory safety. It utilizes the AMCL (MIRACL/core) library for cryptographic operations and a modified go-tpm library for interaction with the TPM. An SQLite database is used for logging hash(bsn)_t entries, enabling efficient lookups to prevent the signer from generating multiple proofs for the same t and bsn.

The primary hardware security device for the baseline is the ST33TPHF2ESPI TPM. This choice was strategic because TPMs natively support DAA, requiring no hardware modifications, thus enabling immediate real-world deployment. The signer application leverages standard TPM functions such as TPM2_CreatePrimary, TPM2_NVReadPublic, TPM2_ActivateCredential, TPM2_Create, and TPM2_Commit/TPM2_Sign to manage credentials and generate proofs.

The verifier server is also written in Golang, using the gin web framework. It employs an SQLite database to store its Log_v entries, specifically tracking σ_α_t values, and uses the AMCL library for cryptographic verification.

To showcase Scrappy's adaptability, two additional implementations were developed on different types of devices:

1. Secure Hardware Token: A Solokey Hacker, incorporating an STM32L432KC microprocessor, was used. The team extended its FIDO CTAP API to support FIDO ECDAA functionalities, leveraging the Xaptum ECDAA library. A notable challenge was that no existing hardware tokens support FIDO ECDAA, and the FIDO ECDAA specification does not allow basenames for privacy reasons. The team simulated this by adding ECDAA functionality and deviating from the spec to include basenames, envisioning unique key pairs per device to maintain rate-limiting even if keys were leaked.

1. Smartphone: Scrappy was implemented on an Android Pixel 6a. The signer application is an Android mobile app written in Kotlin, with the ECDAA and other cryptographic schemes implemented in Golang and converted using Gomobile. Android Room and SQLite are used for logging. Challenges included the lack of browser extension support on mobile (overcome by using custom URLs for inter-app communication) and securely storing private keys. The ECDAA private key is encrypted using the Android Keystore API, though it briefly exists in plaintext in memory, making it less secure than the TPM baseline. Integration with Android ID Attestation is slated for future work.

These diverse implementations highlight Scrappy's versatility, demonstrating its ability to operate across various hardware security devices, each with differing levels of private key protection and unique resource identification. For instance, while TPMs and secure hardware tokens store private keys in tamper-resistant memory, the smartphone encrypts them to a file. The unique resource for a TPM is its Endorsement Key (EK), for a hardware token it's a manufacturer-installed private key, and for a smartphone, it's the device's serial number or IMEI/MEID. Critically, Scrappy's rate-limiting mechanism remains independent of the device's inherent security for all these platforms.

Defensive Implications

▶ Watch: Scrappy's core technical approach: rate-assuring proofs (4:30)

Scrappy offers significant advantages for defenders seeking to protect online services from abusive activities without compromising user privacy. Its deployment presents several key defensive implications:

1. Effective Rate Limiting with Privacy: Defenders can adopt Scrappy to implement robust rate-limiting mechanisms that prevent common forms of online abuse, such as poll manipulation, API overuse, free trial exploitation, dictionary attacks, and excessive crawling. Crucially, it achieves this while preserving user privacy, avoiding the pitfalls of privacy-invasive methods like SMS authentication.
2. Resilience to Hardware Compromise: A paramount benefit is Scrappy's unique resilience. Even if an attacker successfully compromises a client's hardware security device and extracts its secret keys, the rate-limiting functionality remains intact. The verifier's log, by tracking the deterministic component of the signature (σ_α) for each time window, ensures that a compromised key can still only be used once per t. This fundamentally shifts the security burden away from the absolute infallibility of client-side hardware, providing a more robust defense than prior solutions.
3. Hardware Agnosticism and Deployability: Scrappy's compatibility with generic hardware security devices, including TPMs, secure tokens, and smartphones, means organizations are not locked into specific, expensive hardware. The open-sourced TPM implementation allows for immediate deployment and integration into existing infrastructure, making it a practical choice for a wide range of services.
4. Reduced User Friction: By offering a transparent, cryptographically-backed solution, Scrappy minimizes the need for disruptive user interactions like CAPTCHAs, which are known to degrade user experience. This can lead to higher user satisfaction and engagement.
5. Log Management and Scalability: Verifiers should implement efficient log management and cleanup strategies, as outlined in the protocol, to ensure minimal storage overhead and consistent performance, even with a large number of signers. The demonstrated storage requirements (e.g., 6.64 MB for 100,000 verifier-side entries) prove its scalability.
6. Strategic Role of the Group Manager: The integrity of the Group Manager (GM) is crucial for issuing credentials. Organizations could consider operating their own GMs or partnering with trusted third-party identity providers or non-profit organizations to act as GMs, ensuring a reliable source of credentials.
7. Future Integration Opportunities: Defenders should explore the potential for integrating Scrappy with Content Delivery Networks (CDNs) and other third-party services. CDNs, for instance, could operate Scrappy verifiers, distributing the load and enhancing global reach. This broadens the applicability and impact of the protocol.
8. Mitigation of Device Farms: While a malicious actor could theoretically purchase multiple devices, the inherent cost associated with this, combined with potential GM policies based on reputation or device cost, can serve as a deterrent. Scrappy provides a framework to manage such scenarios more effectively than existing methods.

By adopting Scrappy, defenders gain a powerful, privacy-preserving tool that fundamentally redefines how online services can enforce rate limits, moving beyond outdated and vulnerable methods to a more secure and user-friendly paradigm.

Key Takeaways

• Scrappy introduces rate-assuring proofs, a novel cryptographic primitive for unforgeable, unlinkable, and privacy-preserving rate-limiting in online services.
• The protocol leverages Direct Anonymous Attestation (DAA) and is compatible with generic hardware security devices like TPMs, secure hardware tokens, and smartphones, demonstrating broad applicability.
• A critical differentiator is that Scrappy's rate-limiting capability remains effective even if the underlying hardware security device is compromised and its secret keys are leaked, a significant improvement over prior work.
• Practicality is demonstrated through three proof-of-concept implementations, with the TPM version being open-sourced and immediately deployable without hardware modifications.
• Extensive performance evaluation confirms minimal overhead in terms of latency (e.g., 243.16 ms for TPM proof generation, 84.1 ms for verification), bandwidth (660 bytes per signature), and storage (6.64 MB for 100,000 verifier log entries), making it suitable for real-world deployment.
• Scrappy offers a robust and privacy-respecting alternative to flawed traditional solutions like SMS authentication and CAPTCHAs for mitigating abusive online activities.

About the Speaker(s)

Kosei Akama is the speaker who presented "Scrappy: SeCure Rate Assuring Protocol with PrivacY" at the NDSS Symposium. The transcript and metadata do not provide further details about his professional title or company affiliation.