Open-sourcing Anonymous Credential Service

Meta has open-sourced Anonymous Credential Service (ACS), a highly available multitenant service that allows clients to authenticate in a de-identified manner.
ACS enhances privacy and security while also being compute-conscious.
By open-sourcing and fostering a community for ACS, we believe we can accelerate the pace of innovation in de-identified authentication.

Data minimization — collecting the minimum amount of data required to support our services — is one of our core principles at Meta as we develop new privacy-enhancing technologies to protect user data on our family of products. The goal is to deliver valuable user experiences while collecting and using less data. 

Our approach to logging is one important example of this practice. Logging helps our engineers and developers evaluate performance and reliability, improve product features, and generate reports.

User identities aren’t necessary in most logging use cases and should be excluded from logging data. Removing authentication is one way to remove identifiers. But doing so makes the system vulnerable to various attacks, including data injection

At Meta, we’ve built a better way for clients to authenticate in a de-identified manner: Anonymous Credential Service (ACS). At a high level, ACS supports de-identified authentication by splitting authentication into two phases, token issuance and token redemption. In the token issuance phase, clients contact the server through an authenticated channel to send a token. The server signs the token and sends it back. Then, in the de-identified authentication (or token redemption) phase, clients use a de-identified channel to submit data and authenticate it utilizing a mutated form of the token rather than a user ID.

ACS has played an important role in how we do de-identified authentication at scale. Now we’ve open-sourced it so the larger community can both benefit from ACS and help accelerate innovation in de-identified authentication.

Here’s how we developed ACS, and how you can get started using it.

An overview of the anonymous credential protocol

The anonymous credential protocol is built on top of verifiable oblivious pseudorandom functions (VOPRFs) and blind signatures. 

Taking logging as an example again, we solve the problem of de-identified logging by splitting the workflow into two steps: First, clients use an authenticated connection to the server to obtain an anonymous credential in advance. Then, whenever the clients need to upload logs, they send the anonymous credential along with the logs in an unauthenticated connection to the server. The anonymous credential serves as proof that the client is authentic.

Here’s how the process plays out:

Step 1 (token issuance):

The client generates a token.
The client blinds the token.
The client sends the blinded_token to the server, along with authentication data.
The server signs the blinded_token and then sends the signed_blinded_token back to the client.
The client unblinds the received token, resulting in a signed_unblinded_token.

Step 2 (token redemption):

The client sends the original token, signed_unblinded_token, along with the business data it needs for the use case (e.g., logging events) to the server.
The server validates the request with tokens. If the client is authentic and authorized to access, the server will process the business data.

This protocol is effective because:

The business data and authentication data are separated.

The business data is sent with unblinded tokens, and authentication data is sent with a blinded token. It is noteworthy that the token issuance step and token redemption step do not happen at the same time — the client can store tokens for several hours or even several days. If the client wants to log data but is out of tokens, they can fetch a token and redeem it immediately. But these two steps are put into separate requests to help prevent an identity from being inferred from the data.

The token, together with signed_unblinded_token, serves as the legitimation of the client. The token issuance server uses a secret key to sign tokens, and that secret key cannot be inferred from client-side observations (see: decisional Diffie–Hellman assumption). 

Challenges of the anonymous credential protocol

To make the protocol work in real-life, large-scale systems, there are more challenges to be solved.

Token redemption counting

Ideally, one credential can be redeemed only once. But in practice, it is acceptable to allow a credential to be redeemed multiple times (as defined by the use case) to reduce server load. We utilized a real-time, reliable, and secured counting service to limit the number of token redemption times.

Key rotation

The anonymous credential protocol requires a key pair. The server uses a secret key to sign the token (step 1.4) and validate the redemption request (step 2.2). The client needs a corresponding public key to unblind the token (step 1.5).

Given this, key management — specifically, rotating keys frequently and discarding reports from old keys — plays a crucial role in ensuring that we can mitigate the impact of clients if they are compromised after they’re issued a credential. These key rotations have to be deployed across the fleet in a consistent  and efficient manner. The key management service interacts with the configuration management system to mutate key materials for ACS tenants according to the cipher suites and key rotation schedules specified in their configuration files. 

There are also challenges around distributing new verification keys to clients that would like to verify credentials.

Key transparency and attribute-based VOPRFs

The design of our attribute-based VOPRFs is motivated by our need for an efficient and transparent strategy around key rotation.

Frequent key rotations provide a security measure for ACS. However, a malicious server can identify users by signing each one with a user-specific key that can be tied back to them during credential redemption. 

Key transparency makes it possible for users to know about all the available public keys, preventing the server from assigning user-specific key pairs. Moreover, at Meta we need to manage many keys for each ACS use case, and maintaining naively generated keys is not scalable.

We solved this problem by introducing key derivation functions (KDFs). At a high level, given any attributes (e.g., a group of strings), new secret keys can be derived from public keys, which can further be derived from a single public key. By setting the attributes to refer to the time epoch for which the keys are valid, clients can be verified easily without the need to fetch new public keys.

As a result, we can extend the transparency of the primary public key — which can be shipped with client code or posted to a trusted location — to these derived public keys without any additional effort.

Deploying anonymous credential protocol at scale

With these considerations in mind, a typical ACS deployment looks more like:

Setup (step 0):

The client obtains the server’s primary public key and other public parameters.
The server generates a key pair using given attributes (use case name, time epoch, known to clients) and then sends the public key to the client.
The client validates the public key with the primary public key and attributes.

Step 1 (token issuance):

The client generates a token.
The client blinds the token.
The client sends the blinded_token to the server, along with authentication data.
The server checks the token issuance rate for the specific user. It then signs the blinded_token and sends the signed_blinded_token back to the client.
The client unblinds the received token, resulting in a signed_unblinded_token. 

Step 2 (token redemption):

The client sends the original token, signed_unblinded_token, along with the business data it needs for the use case (e.g., logging events) to the server.
The server validates the request and checks the redemption times for the specific token. If the client is authentic and authorized to access, the server will and process the business data. 

Step 0.3 plays an important role in maintaining key transparency. If a malicious server is assigning public keys that correlate to user authentication data, the validation step would fail and the client could refuse to use the public key received.

Read the paper “DIT: De-identified authenticated telemetry at scale” for more mathematical details for the protocol.

The ACS library

The ACS repo provides a portal and extensible C library (in the /lib/ folder), whose main components include:

The VOPRF protocol: This includes client-side token blinding, unblinding, and generating a shared secret for token redemption. For servers, the protocol includes signing the blinded token and generating a server-side shared secret for token redemption. There are two versions of the blinding method provided in the library.
An attribute-based key derivation function: This is a key rotation solution. If the attributes are set to a common known value (e.g., time epoch), clients can verify the authenticity of the server easily. There are multiple KDFs provided in the library. We recommend Strong Diffie–Hellman Inversion (SDHI) or Naor-Reingold for better key transparency.
Discrete log proof: This is used to prove the authenticity of the server. It is used twice in the protocol — first, to verify the public key derived from attributes in the setup step, and second, to verify the signed token in token issuance step
Elliptic curves: The ACS library is modular, and users can choose preferred elliptic curves. Ed25519 and Ristretto are currently provided.     

The library is supposed to be deployed on mobile devices, so we want to minimize external dependencies to keep the binary size small. Currently, libsodium is the only dependency for the ACS library.

In addition to that, we have implemented a SimpleAnonCredService (server + client) in C++ for demonstration purposes. The service is built with Apache Thrift 0.16. (See the /demo/ folder in the repo.)

How to use ACS in a real system

Let’s use an example to demonstrate the workflow. Suppose we are maintaining a service that allows authenticated users to get weather reports. A naive system will look like this:

# client
get_report(authentication_data)
# server
if check_authentication(request.authentication_data):
response.report = report_data

The first step is to split the authentication_data from report_data, which is the main purpose of the ACS project. 

# client – authentication
token = random_string()
blinded_token, blinding_factor = blind(token)
signed_blinded_token = request_token_from_server(authentication_data, blinded_token)
signed_unblinded_token = unblind(signed_blinded_token, blinding_factor)
# client – get data
client_secret = client_finalize(token, signed_unblinded_token)
get_report(token, client_secret)
# token issuance server
if check_authentication(request.authentication_data):
signed_blinded_token = evaluate(blinded_token)
response.signed_blinded_token = signed_blinded_token
# token redemption server
server_secret = server_finalize(request.token)
if server_secret == request.client_secret:
response.report = report_data

After the client is authenticated and requests the data it needs, the client generates a token, blinds the token, and sends the token to the server. After an authentication check, the server signs the token and sends it back to the client. The client then unblinds the signed token, and then verifies it with the public key and proof.

Finally, the client redeems the token. The server validates the secret key and proceeds to business logic if the validation succeeds. If the validation fails, the server rejects the request.

When we introduced key rotation and KDF, it added two more steps in the beginning of the process:

The client downloads the primary public key from the server. This primary public key is for validation of the public key in step 2.
The client gets a public key for provided attributes. The attributes can be any list of strings (e.g., use case names, dates) that are allowed by the server. KDFs allow for key transparency. After this step, the client will be confident that the server is not assigning a public key related to the authentication information. Later, the public key can be used in the verifiable_unblind step to make sure the signed_blinded_token is signed with the private key corresponding to the verified public key.

# client – setup
primary_public_key = request_primary_public_key_from_server()
# client – authentication
public_key, pk_proof = get_public_key_from_server(attribute)
if !dleqproof_verify(public_key, pk_proof, primary_public_key, attribute):
raise Exception(“malicious server!”)
token = random_string()
unblinded_token, blinding_factor = blind(token)
signed_blinded_token, proof = request_token_from_server(authentication_data, blinded_token)
signed_unblinded_token = verifiable_unblind(signed_blinded_token, blinding_factor, proof, public_key)

With all these steps, we’ve prevented a potentially malicious server from using these key rotations to segregate and identify users. This is a good prototype system and ready to use. But in a scalable system, there are more challenges to conquer, including client-side token storage and server-side rate limiting. These solutions are not included in ACS’s open source repo.

Future plans for ACS

Looking at the future, we believe the modular ACS is extensible and has the potential to be beneficial to industries that utilize anonymous credential solutions. We are planning to implement the standard.

A light version without libsodium dependency will be beneficial to use cases where binary size is limited. 

If you’d like to contribute to the project, please visit the ACS GitHub.

The post Open-sourcing Anonymous Credential Service appeared first on Engineering at Meta.

Engineering at Meta

Published
Categorized as Technology