[][src]Crate challenge_bypass_ristretto

challenge-bypass-ristretto Build Status

A rust implemention of the privacy pass cryptographic protocol using the Ristretto group.

This library utilizes the wonderful curve25519-dalek which is a pure-Rust implementation of group operations on Ristretto.

It is only an implementation of the cryptographic protocol, it does not provide a service or FFI for use by other languages.

This crate is still a work in progress and is not yet recommended for external use.


This library exposes some functions intended to assist FFI creation but does not implement a FFI itself.

For FFI see challenge-bypass-ristretto-ffi.

Blinded Tokens

As originally implemented in the challenge bypass server and extension repositories, blinded tokens enable internet users can anonymously bypass internet challenges (CAPTCHAs).

In this use case, upon completing a CAPTCHA a user is issued tokens which can be redeemed in place of completing further CAPTCHAs. The issuer can verify that the tokens are valid but cannot determine which user they were issued to.

This method of token creation is generally useful as it allows for authorization in a way that is unlinkable. This library is intended for use in applications where these combined properties may be useful.

A short description of the protocol follows, a more detailed writeup is also available.

The blinded token protocol has two parties and two stages. A client and issuer first perform the signing stage, after which the client is able to derive tokens which can later be used in the redemption phase.


The client prepares random tokens, blinds those tokens such that the issuer cannot determine the original token value, and sends them to the issuer. The issuer signs the tokens using a secret key and returns them to the client. The client then reverses the original blind to yield a signed token.


The client proves the validity of their signed token to the server. The server marks the token as spent so it cannot be used again.


This crate is still a work in progress and is not yet recommended for external use.


By default this crate uses std and the u64_backend of curve25519-dalek. However it is no-std compatible and the other curve25519-dalek backends can be selected.

The optional features include base64 and serde.

  • base64 exposes methods for base64 encoding / decoding of the various structures.
  • serde implements the serde Serialize / Deserialize traits.

merlin is an experimental feature that uses merlin to implement the DLEQ proofs. This diverges from the original protocol specified in the privacy pass paper. It is not yet stable / intended for use and is implemented in src/dleq_merlin.rs.


Install rust.


Run cargo build


Run cargo test

Cryptographic Protocol


We have tried to align notation with that used in the paper Privacy Pass: Bypassing Internet Challenges Anonymously sections 3 and 4.


Let \(\mathbb{G}\) be a group (written multiplicatively) of prime order \(q\) with generator \(X\). In this implementation we are using Ristretto.

Let \(\lambda\) be a security parameter.

The protocol requires three hashing functions, they are assumed to be random oracles:

\(H_1() \rightarrow \mathbb{G}\) which hashes to the group, it must ensure the discrete log with respect to other points is unknown.

In this implementation we are using RistrettoPoint::from_uniform_bytes which uses Elligator2.

\(H_2() \rightarrow \{0,1\}^{\lambda}\) which hashes to bitstrings.

\(H_3() \rightarrow \{0,1\}^{\lambda}\) which hashes to bitstrings.


The server generates a signing keypair, consisting of a secret key, \(k\), which is a random Scalar and a commitment to that secret key in the form of a PublicKey.

\(Y = X^k\)

DLEQ Proof

A DLEQProof seeks to show that for some \(Y = X^{k_1}\) and some \(Q = P^{k_2}\) that \(k_1 = k_2\).

To do so the prover first generates a random Scalar \(t\) and commits to it with respect to \(X\) and \(P\).

\(A = X^t\)

\(B = P^t\)

The prover then computes \(c = H_3(X, Y, P, Q, A, B)\) and \(s = (t - ck) \mod q\).

The DLEQProof \((c, s)\) is then sent to the verifier.

The verifier computes \(A'\), \(B'\), and \(c'\) then verifies \(c'\) equals \(c\).

\(A' = X^s \cdot Y^c = X^{t-ck} \cdot X^{ck} = X^t\)

\(B' = P^s \cdot Q^c = P^{t-ck} \cdot P^{ck} = P^t\)

\(c' = H_3(X, Y, P, Q, A', B')\)

\(c' \stackrel{?}{=} c\)

Batch Proof

It is possible to construct a BatchDLEQProof over m instantiations of the original DLEQ proof if \(X\) and \(Y\) remain constant.

First the prover calculates \(w\) which is used to seed a PRNG.

\(w \leftarrow H(X, Y, \{ P_i \} _{i \in m} ,\{ Q_i \} _{i \in m })\)

Next, m Scalars are sampled from the seeded PRNG.

\(c_1, \ldots , c_m \leftarrow PRNG(w)\)

The prover generates the composite elements.

\(M = P_1^{c_1} \cdot \ldots \cdot P_m^{c_m}\)

\(Z = Q_1^{c_1} \cdot \ldots \cdot Q_m^{c_m}\)

A normal DLEQProof is then constructed and sent to the user.

\((c, s) \leftarrow DLEQ_k(X, Y, M, Z)\)

The verifier recalculates \(w\), samples m Scalars and re-computes \(M\) and \(Z\).

Finally the verifier checks the DLEQProof as described above.


The user generates N pairs (referred to as Tokens) which each consist of a random value and a random blinding factor.

The random value \(t\) we'll refer to as a TokenPreimage. The random blinding factor \(r\) is a Scalar.

Given the hash function \(H_1\) we can derive a point T.

\(T = H_1(t)\)

The user blinds each Token forming a BlindedToken, point \(P\), by performing a scalar multiplication.

\(P = T^r\)

The user sends the N BlindedTokens to the server.

The server signs each BlindedToken using it's SigningKey, resulting in a SignedToken, point \(Q\).

\(Q = P^k = T^{rk}\)

The server also creates a BatchDLEQProof showing all BlindedTokens were signed by the same SigningKey as described above.

The user receives N SignedTokens from the server as well as the BatchDLEQProof.

The user verifies the proof and uses the original blinding factor \(r\) from the corresponding Token to unblind each SignedToken.

This results in N UnblindedTokens, each consisting of the unblinded signed point \(W\) and the TokenPreimage, \(t\).

\(W = Q^{1/r} = T^k\)


At redemption time, the user takes one UnblindedToken and derives the shared VerificationKey, \(K\).

\(K = H_2(t, W)\)

The user uses the shared VerificationKey to "sign" a message, \(R\) and sends the TokenPreimage and resulting MAC VerificationSignature to the server.


The server re-derives the UnblindedToken from the TokenPreimage and it's SigningKey. Then it derives the shared VerificationKey and checks the included VerificationSignature.

\(T' = H_1(t)\)

\(W' = (T')^k\)

\(K' = H_2(t, W')\)

\(MAC_K(R) \stackrel{?}{=} MAC_{K'}(R)\)

If the verification succeeds then the server checks \(t\), the TokenPreimage, to see if it has been previously spent. If not, the redemption succeeds and it is marked as spent.


pub use self::errors::*;



Errors which may occur when parsing keys and/or tokens to or from wire formats, or verifying proofs.




A BatchDLEQProof is a proof of the equivalence of the discrete logarithm between a common pair of points and one or more other pairs of points.


A BlindedToken is sent to the server for signing.


A DLEQProof is a proof of the equivalence of the discrete logarithm between two pairs of points.


A PublicKey is a committment by the server to a particular SigningKey.


A SignedToken is the result of signing a BlindedToken.


A SigningKey is used to sign a BlindedToken and verify an UnblindedToken.


A Token consists of a randomly chosen preimage and blinding factor.


A TokenPreimage is a slice of bytes which can be hashed to a RistrettoPoint.


An UnblindedToken is the result of unblinding a SignedToken.


The shared VerificationKey for proving / verifying the validity of an UnblindedToken.


A VerificationSignature which can be verified given the VerificationKey and message



The length of a BlindedToken, in bytes.


The length of a DLEQProof, in bytes.


The length of a PublicKey, in bytes.


The length of a SIGNED_TOKEN_LENGTH, in bytes.


The length of a SIGNING_KEY_LENGTH, in bytes.


The length of a Token, in bytes.


The length of a TokenPreimage, in bytes.


The length of a UNBLINDED_TOKEN_LENGTH, in bytes.


The length of a VERIFICATION_SIGNATURE_LENGTH, in bytes.